比特币如何抵御量子计算机？三大格基签名方案对比

Foresight News

特邀专栏作者

2026-08-27 12:00

이 기사는 약 5115자로, 전체를 읽는 데 약 8분이 소요됩니다

基于 Blockstream 最新研究：Falcon、Dilithium 与 Hawk 的安全、性能与链上落地评估。

AI 요약

펼치기

核心观点：Blockstream研究院评估了三种后量子格基签名方案（Dilithium、Falcon、Hawk）在比特币上的部署可行性，结论是：Hawk因安全缺陷退出竞争，Dilithium实现简单但体积过大，Falcon在安全性、体积和验证速度上最为均衡，若当前需部署则优先推荐Falcon-1024，但短期仍应沿用哈希基签名作为过渡。
关键要素：
1. 评估标准：链上成本（公钥+签名大小）、实现复杂度（是否需浮点运算）、部署风险（哈希函数兼容性、硬件钱包内存）、发展潜力（BIP-32密钥派生支持）。比特币建议采用NIST 3级安全标准，因资产可能长期锁定且密码分析技术持续进步。
2. Dilithium亮点：全整数运算，实现难度最低，已集成于主流密码库；ML-DSA-65总大小5261字节（约为比特币原生签名的55倍），是三者中唯一有密钥派生研究基础（DilithiumRK），但相关变体均未达到可部署标准。
3. Falcon优势：体积最小（Falcon-1024总3073字节），验证速度最快且为确定性整数运算；短板是签名端需浮点采样，可通过整数模拟解决（代价为签名慢15倍），且标准（FN-DSA）尚未定稿，暂无可行BIP-32派生方案。
4. Hawk失败：曾以555字节最小签名和全整数运算为亮点，定稿前夕遭Anthropic团队发现结构性缺陷（SVP维度减半），密钥恢复安全位大幅削弱，已撤回NIST流程，反映保守安全级别选择的必要性。
5. 混合方案潜力：格基签名（如Falcon）可与哈希签名互补，用于SHRINCS等无状态恢复路径，可显著缩小体积并加快验证，不影响日常操作路径。

원문 저자: Blockstream Team

원문 편집: Saoirse, Foresight News

Blockstream Research는 비트코인 격자 기반 서명에 대한 완전한 연구 보고서를 발표했습니다. 본 문서는 연구 내용, 핵심 발견 및 관련 제안을 요약합니다. 전체 보고서는 여기에서 확인할 수 있습니다.

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

격자 기반 서명 방식은 기존 서명을 대체할 유력한 후보입니다. 격자 암호는 한 세기 이상의 연구 역사를 가지고 있으며, 암호학적 응용은 약 30년 동안 발전해 왔습니다. 양자 후 암호 체계에서 격자 기반 서명은 여러 장점을 제공합니다: 공개 키와 서명의 총 크기가 최소 1.6 킬로바이트 미만으로 줄어들 수 있으며, 그 대수적 구조는 향후 다중 서명, 임계 서명 및 간결한 증명을 지원할 가능성이 있습니다.

본 보고서는 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.5킬로바이트 증가합니다. 보고서는 모든 보안 수준의 매개변수 세트를 비교하므로 독자가 직접权衡取舍할 수 있습니다. 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 매개변수 세트의 샘플러는 미리 계산된 트리에 의존하며 약 90킬로바이트 메모리를 차지합니다. 하드웨어 지갑은 트리를 분기별로 동적으로 재구성하여 메모리 사용량을 16킬로바이트로 줄일 수 있지만 서명 시간은 두 배가 됩니다. 하드웨어 장치의 서명 속도 저하는 실제 비용이지만 감당할 수 있는 수준입니다.

Hawk: 실패로 선언된 방식

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

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

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

보고서는 여전히 Hawk 관련 장을 유지하는데, 그 이유는 이 공격이 특정 수체의 대수적 특성을 겨냥한 것이지 전체 설계 패러다임을 부정하는 것은 아니기 때문입니다. 재설계가 취약점을 피할 수 있을지는 아직 불확실합니다. Hawk 사건은 또한 우리가 보수적인 보안 여유를 고집하는 이유를 직관적으로 입증합니다: 크기가 우수하고 속도가 빠르며 표준화 과정의 여러 라운드를 통과한 방식이라도 한 편의 논문으로 예상 보안 수준이 크게 하락할 수 있습니다.