비트코인은 어떻게 양자 컴퓨터에 대비하는가? 세 가지 격자 기반 서명 방식의 장단점 비교

작성: Blockstream Team

번역: Saoirse, Foresight News

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

디지털 서명은 비트코인 거래를 승인하는 핵심 메커니즘으로, 현재 이 기능을 담당하는 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 문제를 따르지 않고, 격자 동형 문제(lattice isomorphism problem)와 one‑more‑SVP 가정에 의존하는데, 이 두 부류의 가정은 연구 역사가 상대적으로 짧다.

보고서가 최종 확정되기 직전, Anthropic의 Straznickas와 Weis는 Hawk 격자 구조에 구조적 결함이 있음을 발견했다. 키 복구를 위해 실제로 풀어야 하는 SVP 문제의 차원이 설계자가 의도한 것의 절반에 불과했던 것이다. 후보 파라미터 집합의 키 복구 보안 비트는 크게 약화되었다. 연구자들은 암호 분석용 챌린지 파라미터인 HAWK‑256을 대상으로 완전한 엔드투엔드 키 복구 공격을 수행했다. 공격을 받더라도 공식 제안된 HAWK‑512, HAWK‑1024는 여전히 현실적으로 공격할 수 없다. Hawk 팀은 공격이 유효함을 확인하고 해당 방식을 NIST 절차에서 철회했다. 팀은 파라미터를 두 배로 늘려 취약점을 고치면 Hawk가 원래 자랑하던 크기 이점이 완전히 사라진다고 밝혔다.

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

각 방식 비교표

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

현실 적용에는 여전히 많은 장애물이 있다

Falcon에는 사용 가능한 키 파생 방식이 부족하다. 현재 공개된 유일한 BIP‑32 스타일 Falcon 파생 방식은 개인키 기반을 재무작위화(re-randomization)하는데, 서명 노름 상한이 급격히 커져 온체인 서명이 약 23.7킬로바이트까지 팽창한다. 게다가 이 방식의 파라미터는 자체 보안 조건을 충족하지 못하며, 이 문제를 고치면 크기는 더욱 급증한다. 현재 실행 가능한 Falcon 공개키 파생 구현은 없으며, 이는 보고서가 제시하는 가장 가치 있는 미해결 문제이기도 하다.

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

Falcon‑WS 변형: 이 변형은 내부 파라미터를 완화하고 거부 샘플링(rejection sampling)으로 보상한다. 1레벨 총 크기는 1114바이트, 5레벨은 2387바이트로 압축되어 원래 Falcon보다 크기가 더 줄어든다. 이 방향은 연구 가치가 있지만 공식 표준에는 포함되지 않을 것이며, 더 많은 암호 분석 검증이 필요하다. 기존 연구에서 그 파생 방식의 강한 위조 불가능성(strong unforgeability) 증명에 결함이 있음이 발견되었다(일반 위조 불가능성은 영향을 받지 않는다).

향후 더 우수한 방식이 등장할 것인가? 위 방식들을 제외하면, Fiat‑Shamir 계열은 2013년 BLISS에서 처음 시작되었으며, CRYPTO 2025에서 Gärtner가 발표한 최신 성과는 성숙한 가정을 기반으로 하면서 서류상 크기는 Falcon에 버금간다. 이 계열이 엔지니어링으로 구현되기 어려운 근본 원인은 구현 보안 문제에 있다. BLISS는 가우시안 샘플링이 비상수 시간(non‑constant time)이라는 이유로 부채널 공격에 뚫린 적이 있다. 이후 방식들도 이 위험을 완전히 해결하지 못했으며, 최신 성과 역시 샘플링 단계의 방어 난도가 더 높다는 점을 시사한다. 이 문제가 해결되기 전까지이러한 방식은 이론적 매력만 있을 뿐 배포에 적합하지 않다.

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

연구 결론

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

현재로서 우리의 견해는 해시 기반 서명 보고서와 일치한다. 단기 보수 노선은 여전히 해시 기반 서명이다. 보안 가정이 가장 성숙하고 위험이 가장 낮아 과도기적 방안으로 적합하다. FN‑DSA가 공식 확정되어 안정된 규격, 감사된 코드베이스, 하드웨어 지갑 지원을 갖추게 되면, Falcon은 순수 해시 서명 대비 현저한 개선을 가져올 것이다. 또한 하이브리드 배포를 채택해 두 서명 체계가 서로 보완하도록 할 수도 있다.