양자 내성 암호와 AI 내성 암호

통념의 질문

2026년 10월 8일 아침, 비탈리크 부테린이 X에 글을 올렸다. 요지는 두 문장이다. 오늘 자금을 새 지갑으로 옮기라고 권하지 않는다. 다만 양자에 약한 암호뿐 아니라 AI에 약할 수 있는 암호에 대한 노출도 줄여야 한다. 그가 지목한 새 위험은 ML-DSA, 완전 동형 암호, 격자다.

독자가 먼저 묻는 질문은 이렇다. 양자 컴퓨터가 오면 지갑이 털리는가. 그 질문은 답할 수 없는 형태다. "오면"의 시점이 없고, "지갑"이 서명 알고리즘인지 시드 문구인지 서명 버튼을 누르는 사람인지 정해져 있지 않다.

질문을 바꾼다. 2026년 10월에 코인을 잃는 경로는 몇 개인가. 그 경로 가운데 양자 컴퓨터가 여는 것은 몇 개인가. AI가 수학을 빨리 푼다는 가설이 여는 것은 몇 개인가.

답은 이렇다. 경로는 셋이다. 서명을 위조하는 경로, 키를 훔치는 경로, 서명자를 설득하는 경로. 양자는 첫째 경로의 일부만 연다. AI가 수학을 빨리 푼다는 가설도 첫째 경로에만 걸린다. 2025년에 실제로 돈이 나간 곳은 둘째와 셋째다.

양자가 여는 문, 열지 않는 문

1994년 피터 쇼어는 인수분해와 이산로그를 양자 컴퓨터에서 다항 시간에 푸는 알고리즘을 발표했다. 타원곡선 이산로그도 그 이산로그에 들어간다. 비트코인과 이더리움의 서명 ECDSA, 그리고 RSA는 이 문에 서 있다.

1996년 로브 그로버는 정렬되지 않은 검색을 제곱근으로 줄이는 알고리즘을 발표했다. 2ⁿ번 시도할 일을 2^n/2번으로 줄인다. 제곱근이지, 다항 시간이 아니다. AES-256은 AES-128의 자리로 내려앉고, 256비트 해시의 프리이미지 저항은 128비트로 내려앉는다. 키가 두 배면 그로버는 상쇄된다.

해시에는 그로버보다 강한 양자 공격이 논문으로 하나 더 있다. 1997년 브라사르, 회위에르, 타프는 충돌을 2^n/3번 평가에 찾는 알고리즘을 냈다. 그 횟수만 보면 256비트 해시의 충돌 저항은 128비트에서 약 85비트로 준다. NIST는 그 횟수를 비용으로 받지 않았다. 2024년 11월 초안 IR 8547의 표 1은 SHA-256 충돌 탐색을 보안 범주 2로 둔다. 128비트 블록암호 키 탐색이 범주 1이니, 표준 기관의 표에서 256비트 해시는 양자 뒤에도 한 등급 위에 있다. 다니엘 번스타인은 2009년에 이 알고리즘의 가격 대 성능이 고전 충돌 회로보다 나쁘다고 논했다. 비탈리크가 해시의 바이트 길이를 늘릴 이유가 아직 없다고 한 것은 이 표와 같은 방향이다.

열리지 않는 문도 있다. 키가 두 배인 대칭키 암호, 출력 길이를 늘린 해시, 정보 이론적으로 안전한 일회용 암호. NIST가 2024년 11월에 낸 전환 초안 IR 8547은 양자 때문에 걷어낼 대상으로 공개키를 적는다. 대칭키와 해시는 그 목록에 없다.

표준이 고른 것

2024년 8월 13일 NIST는 표준 셋을 냈다.

같은 보안 범주에서 격자 서명은 2.4킬로바이트, 해시 서명은 7.9킬로바이트다. 큰 쪽 SLH-DSA-SHAKE-256f의 서명은 49,856바이트다. ECDSA secp256k1 서명이 64바이트인 체인에서 이 차이는 장식 수치가 아니다. 검증 가스와 콜데이터 비용이 그 바이트를 그대로 받는다.

NIST의 문장은 조심스럽다. FIPS 204는 ML-DSA가 대규모 양자 컴퓨터를 가진 공격자에게도 안전하다고 "믿어진다"고 적는다. 증명했다고 적지 않는다. 표준은 알려진 공격에 대해 파라미터를 고른 결과다. 아직 없는 공격에 대한 보증이 아니다.

연방 시스템의 일정은 초안에 있다. NIST IR 8547 초안(2024-11)은 112비트 강도의 ECDSA와 RSA를 2030년 이후 사용 자제, 2035년 이후 사용 금지로 적는다. 128비트 이상도 2035년 이후 금지다. 미국 국가안보 각서 10호가 2035년을 연방 시스템의 전환 목표로 적는다는 문장도 그 초안이 인용한다. 초안이다. 확정 표준이 아니다.

AI 내성 암호는 없다

"AI 내성 암호"를 표준명이나 정리명으로 검색하면 정의가 나오지 않는다. 2026년 10월 8일 기준으로 그 낱말을 정의하는 NIST 표준도, IACR 정리도 없다. 검색에 걸리는 가장 가까운 논문은 2023년 9월의 「Cryptography: Against AI and QAI Odds」다. 저자 해리스, 하디, 주카이브는 AI가 평문 공간을 예측하니 키를 키우고 패턴을 없애자는 설계 스케치를 낸다. 안전성 정리도, 공격 하한도 없다. 그 논문이 "AI 내성 암호"라는 말을 정의하지도 않는다.

있는 것은 반대 방향의 문장이다. 비탈리크는 "AI에 약할 수 있는 암호"라고 썼다. 가능성은 적었고, 성질은 적지 않았다.

그의 위협 모델은 인수분해의 역사다. 인수분해는 순진하게 하면 2^n/2이다. 수체 체(number field sieve)가 그 지수를 n^1/3 근처로 내렸고, 그래서 RSA 키가 64바이트가 아니라 400바이트 근처가 됐다. 타원곡선과 격자에도 그런 개선이 있는데 사람이 못 찾고 있을 뿐이며, 앞으로 2년의 AI 수학이 찾을 수 있다는 것이다. 그는 이 세계를 "전혀 극단적이지 않은 예측"이라고 불렀다.

유비는 절반만 맞다. 수체 체는 사람이 수십 년에 걸쳐 낸 알고리즘이고, 그 복잡도는 논문으로 박혀 있다. AI가 격자에서 그와 같은 개선, 곧 지수의 모양이 바뀌는 개선을 냈다는 논문은 2026년 10월에 없다.

있는 것은 차원이 줄어든 공격 하나다. 2026년 스트라즈니카스와 바이스는 NIST 추가 서명 후보 HAWK의 키 복호를 차원이 절반인 최단 벡터 문제로 환원했다. 게이트 수 모델에서 HAWK-512의 비용은 2¹⁵⁰에서 2¹⁰⁸로 내려갔고, HAWK-256 비밀키는 서버 한 대에서 몇 시간 안에 복호됐다. 저자들은 이 논문의 수학적 발견 대부분이 AI의 도움을 받았다고 적는다. 같은 문단에서 그 구성은 Falcon으로 옮기지 않는다고 적는다. ML-DSA와 ML-KEM은 다른 문제, Module-LWE와 Module-SIS 위에 있어서 이 환원의 대상이 아니다.

2026년에 나온 나머지 격자 공격의 개선은 사람이 낸 것이다. 허우와 장의 2026년 8월 논문은 FHE용 희소 Ring-LWE 파라미터 16개 가운데 12개를 목표 128비트 아래로 내렸다고 보고한다. 개선 폭은 최대 13비트다. 그 논문은 NIST의 ML-KEM과 ML-DSA를 깨뜨렸다고 말하지 않는다.

그래서 "AI가 격자를 2년 안에 크게 약화시킨다"는 2026년 10월의 예측으로 남겨 둔다. HAWK는 그 예측의 증거가 아니라, 예측이 가리키는 방향에서 이미 한 번 일어난 작은 사건이다.

해시로 못 만드는 것

비탈리크의 글에서 수학적으로 가장 단단한 문장은 이것이다. 공개키 암호를 해시만으로 만들 수 없다는 오래된 정리가 있다.

그 정리는 임팔리아초와 루디치의 1989년 결과로 읽는 것이 맞다. 그들은 일방향 순열만 있는 세계에서도 키 합의가 안전하지 않은 오라클을 구성했다. 블랙박스로 쓰는 일방향 함수에서 초다항 안전성의 키 합의가 나오지 않는다. 바라크와 마흐무디는 2009년에 그 한계를 조였다. 정직한 질의 n번으로 만드는 랜덤 오라클 키 합의는 O(n²)번 질의에 깨진다.

정리가 금지하지 않는 것이 둘 있다. 제곱 갭은 허용된다. 머클 퍼즐은 해시만으로 키 합의를 만들고, 안전성이 질의 수의 제곱근에 머문다. 또 블랙박스가 아닌 구성은 이 정리의 밖이다. 비탈리크의 문장 "해시만으로는 불가능하다"는 초다항 안전성에 한정하면 맞고, 모든 구성에 대해 말하면 과하다.

서명은 처음부터 이 정리의 대상이 아니었다. 1979년 머클은 해시만으로 서명을 만들었다. 그 계보가 Winternitz 일회용 서명, XMSS, SPHINCS+이고, SPHINCS+가 FIPS 205의 SLH-DSA다.

이 구분이 글 전체의 하중이다. 서명과 증명은 해시로 갈 수 있다. 키 합의와 공개키 암호화는 구조가 있는 함정문(trapdoor)이 필요하다. 비탈리크가 적은 후보가 그 구조다. 군, 아이소제니, 격자, 부호, 그리고 그가 "로컬 믹싱"이라고 부른 아직 없는 것.

구조가 있는 후보는 이미 한 번 통째로 무너진 적이 있다. 2022년 7월 카스트릭과 데크뤼는 SIDH의 키를 복호하는 공격을 냈고, NIST 4라운드 후보였던 SIKE가 그 공격으로 떨어졌다. 공격은 프로토콜이 공개하는 보조 점(torsion point image)을 쓴다. 구조가 하나 더 있었다는 뜻이다. 비탈리크가 말한 "옷장 속의 해골"의 실물은 AI가 찾기 4년 전에 사람이 찾았고, 찾은 곳은 격자가 아니라 아이소제니였다.

이더리움이 간 방향, 아직 도착하지 않은 곳

2025년 7월 31일 저스틴 드레이크는 「Lean Ethereum」에서 해시 기반 암호가 lean Ethereum의 토대로 떠오르고 있다고 썼다. 같은 글은 스스로를 한 사람의 견해라고 밝힌다. 배포 공지가 아니다. 그 글은 ML-DSA와 Falcon을 이름으로 배제하지 않는다.

배제 문장은 비탈리크의 2026년 10월 글에 있다. "격자 없음, ML-DSA 없음, Falcon 없음, 영지식 증명 안의 격자 커밋 없음. lean Ethereum의 서명은 전부 해시 기반이며 WOTS 또는 SPHINCS-다." 재단의 문서 전체가 그 문장을 따르지는 않는다. 초안 EIP-8051은 ML-DSA 검증 프리컴파일을, EIP-8052는 Falcon 지원을 제안한다. 해시 서명은 합의 계층의 선택으로 문서화돼 있고, 격자는 배제 목록에 올라 있지 않다.

2026년 6월 12일 이더리움 리서치에 올라온 SPHINCS- 제안은 그 방향의 실물이다. EVM의 KECCAK256으로 검증하는 상태 없는 해시 서명이고, 변형 C13의 검증 비용을 127,000가스로 적는다. 표준 SLH-DSA가 아니다. 케착을 쓰면 FIPS 205를 벗어나고, 서명 횟수 상한이 2⁶⁴이 아니라 2¹⁴에서 2²⁰이다. 집계는 미래의 일로 남아 있다.

메인넷의 서명 규칙은 2026년 10월에도 ECDSA다. 해시 서명은 연구 제안이다. 두 문장을 붙이면 안 된다.

상태 있는 해시 서명에는 표준이 이미 있다. NIST SP 800-208의 LMS와 XMSS다. IR 8547은 이 계열의 안전성이 서명자가 일회용 키를 두 번 쓰지 않는 데 달려 있으며, 그 때문에 일반 용도로 intended 되지 않는다고 적는다. 카운터를 하나 잃으면 그 키로 위조가 된다. 지갑이 이 계열을 고르면 암호 문제가 저장 문제가 된다.

지갑에서 깨지는 것

코인 주소는 공개키가 아니다. 공개키의 해시다. 한 번도 보내지 않은 주소에는 공개키가 체인 위에 없다. 쇼어의 알고리즘은 공개키에서 비밀키를 복호하지, 해시에서 공개키를 복호하지 않는다. 그로버로 그 해시를 뒤집는 일은 제곱근 가속이지 다항 시간이 아니다. 비탈리크의 "아직 거래를 만들지 않은 주소에 두라"는 이 비대칭을 쓴다.

그 조언이 막는 실패는 하나다. 나중에 양자 컴퓨터가 생겼을 때, 체인에 공개된 공개키로 과거 서명을 위조하는 실패. 막지 못하는 실패가 나머지다. 시드 문구를 피싱 페이지에 넣는 실패, 악성 승인을 서명하는 실패, 서명 권한을 가진 기기가 탈취되는 실패.

2025년의 숫자는 그 나머지가 본류라는 쪽이다. 체인애널리시스는 2025년 1월부터 12월 초까지 도난을 34억 달러 이상으로 집계했고, 2월의 Bybit 사건 하나가 15억 달러였다. 개인 지갑 피해는 158,000건, 80,000명, 7억 1,300만 달러였다. Bybit 항목에서 체인애널리시스가 적은 수법은 서명자를 속여 악의적 거래에 권한을 주게 한 것이다. 이산로그를 푼 사건이 아니다.

그래서 이사 비용의 비교가 성립한다. 비탈리크는 자신이 해킹으로 잃은 돈보다 잘못된 이사로 잃은 돈이 많다고 적었다. 이 문장은 개인 경험이다. 통계가 아니다. 다만 방향은 집계와 같다. 2025년에 측정된 손실은 서명 알고리즘 밖에서 났고, 이사는 그 자리에서 새 실패를 만든다. 주소를 잘못 적거나, 미끼 컨트랙트에 승인하거나, 새 지갑의 시드를 사진으로 찍는 실패.

장치가 막는 실패, 장치가 못 막는 실패

ERC-4337은 2023년 3월 1일 메인넷에 엔트리포인트 계약이 배포되며 시작됐다. 검증 로직을 계약으로 옮긴 것이지 곡선을 바꾼 것이 아니다. 계약이 secp256k1 서명을 검사하면 쇼어의 입력은 그 자리에 남는다.

패스키는 그 곡선을 바꾼다. 바뀐 도착지가 P-256이고, P-256도 타원곡선이다. 쇼어의 알고리즘은 곡선이 달라도 같은 이산로그를 푼다. 패스키가 줄이는 것은 피싱에 시드를 타이핑하는 실패다. 양자 노출이 아니다.

비탈리크의 멀티시그 문장은 배포된 계약에서 거짓이다. 확인을 오프체인에서 모아도 Safe의 execTransaction은 소유자 서명 전부를 호출 데이터로 받아 ecrecover에 넣는다. 서명은 체인에 남고, 공개키는 그 자리에서 복원된다. 오프체인이 공개키를 숨기려면 서명이 호출 데이터에 들어가면 안 된다. 그 구성은 2026년 10월에 표준 지갑의 기본값이 아니다.

반론

격자는 이미 여유를 두고 파라미터를 골랐다

FIPS 203은 ML-KEM-768을 기본값으로 권한다. 성능 비용이 감당되는 선에서 보안 여유가 크다는 이유다. 표준의 보안 범주는 2024년까지의 격자 공격, 곧 BKZ와 시빙과 듀얼 공격을 기준으로 잡혔다. "여유를 뒀으니 안전하다"는 문장은 알려진 공격 족에 대해서만 참이다. 수체 체 급의 새 공격이 나오면 그 여유는 다시 계산해야 한다. 다만 그 새 공격은 2026년 10월에 존재하지 않는다. 여유를 10배로 곱하라는 비탈리크의 문장은 그 부재 위에 놓인 예측이다. 격자의 안전성이 차원에 어떻게 스케일하는지는 그 10배라는 수가 말해주지 않는다.

해시 서명은 교체 부품이 아니다

SLH-DSA-SHA2-128s의 서명 7,856바이트는 ECDSA 서명의 122배다. 상태 있는 계열은 더 작지만 일회용 키의 상태를 잃으면 위조가 된다. 집계 서명은 BLS에서 공짜로 나오던 것이 해시 계열에는 없고, SPHINCS- 제안도 집계를 미래 작업으로 남긴다. 비탈리크가 "해시 기반이 가능한 곳에서"라고 한정한 이유가 이것이다. 그 한정을 지우고 읽으면 글이 틀린다.

공개키가 숨는 시간은 유한하다

미사용 주소 조언은 보내기 직전까지만 참이다. 출금 트랜잭션은 공개키를 드러내고, 쇼어의 알고리즘이 실물이 된 세계에서는 그 트랜잭션이 블록에 들어가기 전에 위조 경쟁이 시작된다. 한 번도 쓰지 않은 주소는 그 경쟁을 출금 시점으로 미룰 뿐 없애지 않는다. 받는 주소로 계속 재사용하면 첫 출금에서 공개키가 노출된 뒤의 입금은 전부 그 공개키 아래에 있다.

예측이 틀리는 조건

이 글의 결론이 무너지는 경우를 세 개 적는다.

1. 격자에서 수체 체 급의 개선이 논문으로 나온다. 복잡도 지수가 실제로 내려가고, ML-KEM-768의 보안 범주가 그 논문의 숫자로 카테고리 1 아래로 떨어진다. 그러면 비탈리크의 2년 예측은 관측이 되고, 이 글이 예측과 관측을 나눈 구분은 틀린다.
2. 암호학적으로 유의미한 양자 컴퓨터가 쇼어의 알고리즘으로 256비트 타원곡선 키를 복호한 시연이 나온다. 그러면 "양자는 첫째 경로의 일부"라는 문장에서 "일부"가 "지금"으로 바뀐다. 미사용 주소 조언의 우선순위가 피싱보다 위로 올라간다.
3. 2026년의 도난 집계에서 서명 위조가 최대 항목이 된다. 그러면 이 글이 2025년 숫자로 받은 "본류는 키 탈취와 설득"이라는 문장을 다음 해에 수정해야 한다.

셋 다 2026년 10월 8일에는 일어나지 않았다.

다음에 할 일

개인이 오늘 할 일은 작다. 큰 금액을 한 번도 나가지 않은 주소에 둔다. 이사는 서두르지 않는다. 출금 주소와 승인 대상은 하드웨어 지갑 화면에서 읽는다.

프로토콜이 할 일은 둘로 갈라져 있다. 서명은 해시로 가는 길이 있고, 그 길의 비용은 바이트와 가스로 이미 숫자다. 키 합의는 해시로 가는 길이 없다. 격자를 쓰되 파라미터를 어느 여유까지 잡을지는 표준이 이미 한 번 답했다. ML-KEM-768이 그 답이다. 10배라는 수는 그 답을 대체하는 계산이 아니다.

출처

1. Vitalik Buterin, X, 2026-10-08. status/2107976296320106851. 이 글이 인용한 그의 문장은 모두 이 글에서 왔다.
2. Peter Shor, “Algorithms for quantum computation: discrete logarithms and factoring”, FOCS 1994. IEEE.
3. Lov Grover, “A fast quantum mechanical algorithm for database search”, STOC 1996. ACM.
4. Gilles Brassard, Peter Høyer, Alain Tapp, “Quantum Algorithm for the Collision Problem”, 1997-05-01. arXiv:quant-ph/9705002. 평가 횟수 2^n/3. NIST는 이 횟수를 비용으로 채택하지 않았다. IR 8547 표 1.
5. NIST, FIPS 203 ML-KEM, 2024-08-13. doi 10.6028/NIST.FIPS.203. 표 3의 크기, ML-KEM-768 기본값 권고.
6. NIST, FIPS 204 ML-DSA, 2024-08-13. doi 10.6028/NIST.FIPS.204. 표 2의 크기.
7. NIST, FIPS 205 SLH-DSA, 2024-08-13. doi 10.6028/NIST.FIPS.205. 표 2의 크기. 상태 없음.
8. NIST IR 8547 초안, Transition to Post-Quantum Cryptography Standards, 2024-11. doi 10.6028/NIST.IR.8547.ipd. 2030 사용 자제, 2035 사용 금지. 상태 있는 해시 서명의 일반 용도 제한.
9. Daniel J. Bernstein, “Cost analysis of hash collisions”, 2009-08-23. cr.yp.to. 양자 충돌 알고리즘의 가격 대 성능이 고전 회로보다 나쁘다는 논증.
10. Russell Impagliazzo, Steven Rudich, “Limits on the provable consequences of one-way permutations”, STOC 1989. ACM.
11. Boaz Barak, Mohammad Mahmoody, “Merkle’s Key Agreement Protocol is Optimal”, 2009. boazbarak.org. 랜덤 오라클 키 합의의 O(n²) 공격.
12. Zygimantas Straznickas, Stephen A. Weis, “HAWK-n Key Recovery Reduces to SVP in Dimension n/2+1”, 2026. anthropic.com. HAWK-512 비용 2¹⁵⁰에서 2¹⁰⁸. Falcon으로 이전되지 않음.
13. Ralph Merkle, “A Certified Digital Signature”, CRYPTO 1989. Springer.
14. Wouter Castryck, Thomas Decru, “An efficient key recovery attack on SIDH”, 2022. ePrint 2022/975.
15. Jianhua Hou, Haodong Jiang, “Careful with the Ring”, 2026-08-30. ePrint 2026/366. FHE 파라미터 대상. NIST ML-KEM 파손은 주장하지 않음.
16. Justin Drake, “Lean Ethereum”, Ethereum Foundation 블로그, 2025-07-31. blog.ethereum.org.
17. nicocsgy, “SPHINCS minus”, Ethereum Research, 2026-06-12. ethresear.ch.
18. EIP-8051, ML-DSA 서명 검증 프리컴파일 초안, 2025-10-15. eips.ethereum.org/EIPS/eip-8051. EIP-8052, Falcon 지원 초안, 2025-10-17. eips.ethereum.org/EIPS/eip-8052. 둘 다 Draft.
19. Sheetal Harris, Hassan Jalil Hadi, Umer Zukaib, “Cryptography: Against AI and QAI Odds”, 2023-09. arXiv:2309.07022.
20. Chainalysis, “North Korea Drives Record $2 Billion Crypto Theft Year”, 2025-12-18. chainalysis.com. 2025년 1월–12월 초 집계.
21. Safe 스마트 계정, execTransaction과 checkNSignatures. Safe.sol. 소유자 서명이 호출 데이터로 들어가 ecrecover를 탄다.
22. ERC-4337. eips.ethereum.org/EIPS/eip-4337. 엔트리포인트 v0.6 메인넷 배포 2023-03-01, 주소 0x5FF137D4b0FDCD49DcA30c7CF57E578a026d2789.