비트코인은 양자컴퓨터를 어떻게 방어할까? 3대 격자 기반 서명 방식 비교

원문 저자: Blockstream Team

원문 번역: Saoirse, Foresight News

Blockstream Research가 비트코인 격자 기반 서명에 관한 전체 연구 보고서를 발표했습니다. 이 글은 연구 내용, 핵심 발견 및 관련 권고 사항을 요약한 것입니다.전체 보고서는 여기에서 확인할 수 있습니다.

디지털 서명은 비트코인 거래를 승인하는 핵심 메커니즘으로, 현재 이 역할을 담당하는 Schnorr 및 ECDSA 서명은 비용이 매우 낮습니다. 1994년 Shor는 충분히 강력한 양자컴퓨터가 이 두 서명 방식을 모두 해독할 수 있음을 증명했습니다. 이러한 기계가 언제 등장할지에 대해서는 여전히 논쟁이 있지만, 문제가 실제로 발생하기 전에 실행 가능한 양자 내성 서명 배포 계획을 마련해야 합니다.

격자 기반 서명 방식은 기존 서명을 대체할 유력한 후보입니다. 격자 암호는 100년 이상 연구되어 왔으며, 암호학적 응용은 약 30년 동안 발전해 왔습니다. 양자 내성 암호 체계에서 격자 기반 서명은 여러 장점을 제공합니다. 공개 키와 서명의 총 크기는 최소 1.6KB 미만일 수 있으며, 대수적 구조 덕분에 향후 다중 서명, 임계값 서명, 간결한 증명을 지원할 가능성이 있습니다.

이 보고서는 Dilithium, Falcon, Hawk 세 가지 방식을 연구합니다. 격자 암호에 익숙하지 않은 독자를 위해 각 방식의 설계 아이디어를 설명하고, 알고리즘 절차를 완전히 소개하며, 보안성, 성능, 실제 배포(예: 지갑 키 파생) 측면에서 분석합니다. 이 세 가지 중 어떤 방식이 실제로 비트코인 체인에 배포될 수 있을까요?

평가 기준

비트코인은 서명 방식 선택에 고유한 제약이 있으며, 이번 평가는 네 가지 핵심 기준을 중심으로 진행됩니다.

• 온체인 비용: 가장 중요한 지표 중 하나는 공개 키와 서명의 총 크기입니다. 출력이 사용될 때 공개 키와 서명이 모두 체인에 기록되며, 전체 노드는 모든 바이트를 다운로드하고 저장해야 합니다. 검증 비용도 중요합니다. 모든 서명은 네트워크 전체 노드에서 검증되어야 하므로 검증 속도가 느리면 전체 네트워크에 부담이 됩니다.
• 구현 복잡성: 방식을 안전하게 구현할 수 있는지가 중요합니다. 설계에 부동 소수점 연산이나 정밀한 가우시안 샘플링이 필요한 경우, 구현 오류나 타이밍 분석과 같은 부채널 공격에 노출되면 키가 유출될 수 있습니다. 원활한 전환을 위해서는 구현 복잡성을 무시할 수 없습니다.
• 배포 위험: 비트코인에 실제 통합할 때 다양한 현실적 장애물이 발생합니다. 합의 계층의 해시 함수 선택(대부분의 후보는 SHAKE를 사용하지만 비트코인은 SHA-256 사용), 플랫폼 간 서명 결과의 재현성, 서명 프로그램이 하드웨어 지갑의 메모리 제한에 적합한지 여부 등이 있습니다.
• 발전 잠재력: 대부분의 비트코인 지갑은 BIP-32 계층적 결정적 메커니즘을 사용합니다. 단일 마스터 공개 키로 개인 키에 접근하지 않고도 무한한 수의 하위 공개 키를 파생할 수 있습니다. 현재 표준화된 양자 내성 서명 방식은 이 기능을 기본적으로 지원하지 않으므로, 이 기능을 추가하는 데 드는 비용을 연구합니다. 또한 다양한 비표준 방식 변형을 조사하여 더 많은 이점을 제공할 수 있는지 확인합니다.

어떤 보안 수준을 선택해야 할까?

크기를 비교하기 전에 목표 보안 수준을 결정해야 하며, 이 선택은 생각보다 간단하지 않습니다. NIST는 보안 수준을 1~5단계로 분류합니다. 수준이 높을수록 보안성은 강화되지만 해당 키와 서명 크기도 커집니다.

우리는 비트코인이 최소한 3단계 보안 표준을 채택해야 한다고 생각합니다. 비트코인 출력은 수십 년 동안 사용되지 않을 수 있으며, 암호 분석 기술이 발전하여 방식의 실제 보안 수준이 낮아지면 자산이 약화된 키로 잠겨 장기적으로 위험에 노출됩니다. 격자 암호 가정은 거의 30년간 공개 암호 분석을 견뎌왔으며, 이는 비트코인이 타원 곡선을 채택할 당시의 연구 축적보다 더 깁니다. 그러나 격자 암호의 복잡한 대수적 구조에는 향후 공격에 악용될 수 있는 여지가 여전히 많으므로, 먼 미래의 보안을 모두 여기에 걸어서는 안 됩니다.

주요 제품들도 같은 판단을 내렸습니다. Apple의 iMessage PQ3 프로토콜은 1단계 격자 암호 매개변수를 포기하고 3단계와 5단계 매개변수만 사용합니다. Cloudflare는 양자 내성 TLS 배포에서 ML-KEM-768(3단계)을 사용하며, 1단계가 현재는 안전해 보이지만 향후 수십 년간의 암호 분석을 위한 보안 여유를 확보해야 한다고 밝혔습니다. 비트코인의 보안 시간 범위는 이 둘보다 훨씬 깁니다.

보안 수준을 높이려면 대가가 따릅니다. 예를 들어 Dilithium을 2단계에서 3단계로 올리면 총 크기가 약 1.5KB 증가합니다. 보고서는 모든 보안 수준의 매개변수 집합을 비교하므로 독자가 직접 장단점을 평가할 수 있습니다. Hawk의 사례는 보수적인 보안 고려가 결코 이론에 그치지 않음을 증명합니다.

후보 방식 상세 분석

Dilithium: 설계가 단순한 방식

Dilithium은 NIST에 의해 FIPS 204 표준의 ML-DSA로 표준화되었으며, Schnorr 서명의 커밋-챌린지-응답 패러다임을 모듈 격자 산술로 이전합니다.

가장 큰 특징은 단순성입니다. Dilithium의 모든 연산은 정수 연산입니다. 링 연산, 행렬-벡터 곱셈, 해시, 반올림 등이 있으며 부동 소수점 연산이나 이산 가우시안 샘플링이 필요하지 않습니다. 안전하고 상수 시간 구현을 작성하기가 더 쉽습니다. 또한 가장 널리 배포된 후보로, OpenSSL, BoringSSL, AWS-LC, Apple CryptoKit에 통합되어 있습니다.

단점은 크기가 크다는 것입니다. 3단계 보안의 ML-DSA-65는 공개 키 1952바이트, 서명 3309바이트, 총 5261바이트로, 비트코인 네이티브 공개/개인 키 + 서명 총 크기의 약 55배이며, 동일한 보안 수준의 세 가지 방식 중 가장 큽니다.

비트코인에 있어 Dilithium의 가장 가치 있는 점은 세 가지 중 BIP-32 스타일 키 파생에 가장 근접한 유일한 방식이라는 것입니다. 재무작위화 키 구성인 DilithiumRK는 공개 정보만으로 부모 키에서 자식 키를 생성할 수 있습니다. 보고서는 세 가지 변형을 분석하며, 여기에는 우리가 제안한 DilithiumRKS가 포함됩니다. 파생 로직은 완전히 지갑 소프트웨어 내부에 있으며, 체인에서는 표준 검증기만 일반 ML-DSA 서명을 처리하면 됩니다. 그러나 세 가지 모두 아직 출시 기준에 도달하지 못했습니다. 두 가지 변형은 검증기 수정이 필요하고, DilithiumRKS 자체는 완전한 위조 불가능성 증명이 부족합니다. 모든 방식은 네트워크 전체가 공유하는 행렬에 의존하는데, Module-LWE 가정 하에서는 형식적으로 안전하지만 모든 키의 보안을 동일한 인스턴스에 묶게 됩니다. 우리는 현재 단계에서 Dilithium 기반 공개 키 파생은 개념 증명에 불과하며 실제 배포에는 적합하지 않다고 생각합니다.

Falcon: 크기가 컴팩트한 방식

Falcon은 NIST에 선정되었으며 표준화 명칭은 FN-DSA입니다. 세 가지 중 가장 간결합니다. 1단계 보안의 Falcon-512는 공개 키와 서명을 합쳐 1563바이트이고, 5단계 보안의 Falcon-1024는 총 3073바이트입니다. 보안 여유가 더 큰 Falcon-1024는 3단계 Dilithium보다 크기가 작습니다.

Falcon은 Dilithium과 다른 접근 방식을 사용합니다. NTRU 격자 기반의 해시-서명 패턴입니다. 서명자의 개인 키는 격자의 짧은 기저 집합입니다. 메시지는 공간의 한 지점으로 해시되며, 서명자는 짧은 기저를 사용하여 해당 지점에 가까운 격자 벡터를 찾습니다. 지점과 인접 벡터가 함께 서명을 구성합니다. 검증은 벡터가 격자에 속하고 거리가 충분히 가까운지만 확인합니다. 구현의 어려움은 기저 정보를 누출하지 않고 벡터를 찾는 데 있습니다. 초기 방식인 GGH, NTRUSign은 가장 가까운 격자점을 직접 선택하여 서명할 때마다 기하학적 정보가 일부 누출되었습니다. Falcon은 GPV 프레임워크를 사용하여 가우시안 분포에서 인접 벡터를 샘플링하며, 샘플링 출력이 기저와 독립적임을 증명할 수 있어 누출 위험을 제거하지만 샘플러 구현 난이도가 크게 증가합니다.

샘플러는 Falcon의 엔지니어링 측면에서 약점입니다. 복소 푸리에 영역에서 연산하며 부동 소수점 계산이 필요합니다. 프로세서, 컴파일러, 컴파일 최적화 옵션에 따라 부동 소수점 출력 결과가 달라질 수 있습니다. 이는 호환성 문제일 뿐만 아니라 보안 위험이기도 합니다. GPV 보안 증명은 동일한 다이제스트에 대해 서명자가 두 개의 서로 다른 짧은 벡터를 출력하지 않아야 한다고 요구합니다. 서명이 결정적 서명이 되면 플랫폼 간 부동 소수점 반올림 차이로 인해 이 조건이 깨질 수 있습니다. 실행 가능한 해결책이 있습니다. 결정적 Falcon은 하드웨어 부동 소수점 대신 정수 시뮬레이션을 사용하여 모든 플랫폼에서 완전히 동일한 서명을 출력할 수 있습니다. 단점은 서명 속도가 약 15배, 키 생성 속도가 약 2배 느려진다는 것입니다.

중요한 점은 검증 단계는 영향을 받지 않는다는 것입니다. Falcon 검증은 전적으로 정수 연산이며 결과가 결정적이고, 후보 방식 중 검증 속도가 가장 빠릅니다. 이러한 비대칭 특성은 비트코인에 매우 유리합니다. 서명은 지갑이 거래를 사용할 때 한 번만 수행되지만, 모든 서명은 네트워크의 모든 전체 노드에서 검증되어야 합니다. 서명 속도가 15배 느린 것은 빈도가 낮은 비용이며, 플랫폼 간 재현성과 정수 연산을 얻는 대가로 합리적인 절충이라고 생각합니다. 따라서 부동 소수점 문제는 치명적인 결함이 아니라 엔지니어링으로 해결할 수 있는 장애물입니다.

두 가지 주의 사항이 있습니다. 구조적 제약으로 인해 Falcon에는 3단계 매개변수가 없으며 1단계 또는 5단계만 선택할 수 있습니다. 보안 여유를 고려하여 Falcon-1024를 권장합니다. 둘째, 서명에 많은 메모리가 소모됩니다. 1024 매개변수 집합의 샘플러는 사전 계산된 트리에 의존하며 약 90KB의 메모리를 차지합니다. 하드웨어 지갑은 분기별로 트리를 동적으로 재구성하여 메모리 사용량을 16KB로 줄일 수 있지만 서명 시간이 두 배로 늘어납니다. 하드웨어 장치의 서명 속도 저하는 실제 비용이지만 수용 가능한 수준입니다.

Hawk: 실패로 판명된 방식

Hawk의 목표는 다른 두 방식의 장점을 결합하는 것입니다. Hawk-512 서명은 555바이트에 불과하여 Falcon보다 작습니다. 서명 측은 전적으로 정수 연산이며 최소 메모리 사용량은 6KB에 불과합니다. 또한 NIST 추가 서명 경쟁 3라운드에서 유일하게 남은 격자 기반 후보였으며, 보고서에서 상당한 분량을 할애하여 소개합니다.

단점은 보안 가정에 있습니다. 수십 년간 암호 분석으로 검증된 NTRU, SIS 문제를 사용하지 않고 격자 동형 문제와 one-more-SVP 가정에 의존하는데, 이 두 가정은 연구 역사가 상대적으로 짧습니다.

보고서가 마무리되기 직전, Anthropic의 Straznickas와 Weis는 Hawk 격자 구성에 구조적 결함이 있음을 발견했습니다. 키 복구에 실제로 필요한 SVP 문제의 차원이 설계자가 의도한 것의 절반에 불과했습니다. 후보 매개변수 집합의 키 복구 보안 비트가 크게 약화되었습니다. 연구자들은 암호 분석용 챌린지 매개변수인 HAWK-256에 대해 완전한 엔드투엔드 키 복구 공격을 수행했습니다. 공격을 받았음에도 공식 제안된 HAWK-512, HAWK-1024는 여전히 현실적으로 공격할 수 없습니다. Hawk 팀은 공격의 유효성을 확인하고 NIST 프로세스에서 방식을 철회했습니다. 팀은 매개변수를 두 배로 늘려 취약점을 수정하면 Hawk의 자랑이었던 크기 이점이 완전히 사라질 것이라고 밝혔습니다.

보고서는 Hawk 관련 장을 유지합니다. 이 공격은 특정 수체의 대수적 특성을 겨냥한 것이며 설계 패러다임 전체를 부정하는 것은 아니기 때문입니다. 재설계로 취약점을 피할 수 있을지는 아직 결론이 나지 않았습니다. Hawk 사건은 우리가 보수적인 보안 여유를 고집하는 이유를 직관적으로 보여줍니다. 크기가 우수하고 속도가 괜찮으며 표준화의 여러 라운드를 통과한 방식이라도 논문 한 편으로 예상 보안 수준이 크게 떨어질 수 있습니다.

방식 비교표

위 표의 모든 방식(SPHINCS+ 포함)은 무상태 서명입니다. 서명자는 과거 서명을 기록할 필요가 없습니다. XMSS와 같은 상태 기반 해시 서명은 서명 크기를 더 작게 만들 수 있지만 서명 상태를 유지해야 합니다. 비교 내용은해시 기반 서명 특별 보고서에서 확인할 수 있습니다.

배포에는 여전히 많은 장애물이 존재

Falcon에는 사용 가능한 키 파생 방식이 부족합니다. 현재 공개된 유일한 BIP-32 스타일 Falcon 파생 방식은 개인 키 기저를 재무작위화하며, 서명 노름 상한이 급격히 증가하여 온체인 서명이 약 23.7KB로 팽창합니다. 또한 이 방식의 매개변수는 자체 보안 조건을 충족하지 못하며, 이 문제를 수정하면 크기가 더욱 커집니다. 현재 실행 가능한 Falcon 공개 키 파생 구현이 없으며, 이는 보고서가 제시하는 가장 가치 있는 미해결 문제입니다.

Falcon 표준이 아직 확정되지 않았습니다. NIST가 Falcon을 선정했지만 FN-DSA 초안은 아직 공식 발표되지 않았습니다. 표준화가 완료되어야 감사된 구현, 테스트 벡터, 하드웨어 수준 지원이 제공될 것입니다. 광범위한 채택은 비트코인 합의 계층 통합의 위험과 난이도를 낮출 수 있습니다. FN-DSA가 공식 발표될 때까지 기다릴 것을 권장하며, 그 전까지 Falcon은 여전히 변동 상태에 있습니다.

Falcon-WS 변형: 이 변형은 내부 매개변수를 완화하고 거부 샘플링으로 보상하여 1단계 총 크기를 1114바이트, 5단계를 2387바이트로 압축하여 원래 Falcon보다 크기를 더 줄입니다. 이 방향은 연구 가치가 있지만 공식 표준에는 포함되지 않으며 더 많은 암호 분석 검증이 필요합니다. 기존 연구에서 파생 방식의 강한 위조 불가능성 증명에 취약점이 있음이 발견되었습니다(일반 위조 불가능성은 영향을 받지 않음).

향후 더 나은 방식이 등장할까? 위 방식 외에도 Fiat-Shamir 계열은 2013년 BLISS에서 시작되었으며, CRYPTO 2025 컨퍼런스에서 Gärtner가 발표한 최신 결과는 성숙한 가정을 기반으로 하며 서류상 크기가 Falcon과 비슷할 수 있습니다. 이 계열이 엔지니어링적으로 구현되기 어려운 근본 원인은 구현 보안 문제입니다. BLISS는 가우시안 샘플링이 상수 시간이 아니어서 부채널 공격으로 해독된 적이 있습니다. 후속 방식 모두 이 위험을 완전히 해결하지 못했으며, 최신 결과도 샘플링 단계 보호가 더 어렵다는 것을 시사합니다. 문제가 해결되기 전까지 이러한 방식은 이론적 매력만 있을 뿐 배포에 적합하지 않습니다.

격자 기반 서명과 해시 서명은 상호 보완적일 수 있습니다. 격자 기반 서명은 하이브리드 방식의 구성 요소로 사용될 수 있습니다. 예를 들어 SHRINCS에서 무상태 복구 경로는 현재 수 KB 크기의 SPHINCS+ 서명을 사용합니다. 이를 Falcon(또는 Falcon-WS) 서명으로 대체하면 크기가 작아지고 검증 속도가 빨라져 빈도가 낮은 복구 경로의 오버헤드가 크게 줄어들고 일상적인 사용 경로에는 영향을 미치지 않습니다.

연구 결론

격자 기반 후보 방식의 우선순위는 매우 명확합니다. Hawk는 Anthropic 팀의 공격 이후 경쟁에서 탈락했습니다. Dilithium은 구현 난이도가 가장 낮고 키 파생 관련 연구 기반을 가진 유일한 방식이지만 크기가 비트코인 온체인 비용에 적합하지 않습니다. Falcon은 컴팩트한 크기, 빠른 검증, 성숙한 보안 가정을 모두 갖추고 있습니다. 가장 큰 단점인 서명 측 부동 소수점 연산은 이미 실행 가능한 엔지니어링 솔루션이 존재합니다. 지금 당장 비트코인을 위한 격자 기반 서명 방식을 선택해야 한다면 Falcon-1024를 선택할 것입니다.

현재로서 우리의 견해는 해시 기반 서명 보고서와 일치합니다. 단기적으로 보수적인 경로는 여전히 해시 기반 서명이며, 보안 가정이 가장 성숙하고 위험이 가장 낮아 과도기적 방안으로 적합합니다. FN-DSA가 공식 확정되어 안정적인 사양, 감사된 코드베이스, 하드웨어 지갑 지원이 마련된 후에는 Falcon이 순수 해시 서명보다 상당한 개선을 제공할 것입니다. 하이브리드 배포를 통해 두 서명 체계가 서로 보완하도록 할 수도 있습니다.