양자컴퓨터가 오면 암호는 정말 다 깨지나 — '전부'와 '나중'이라는 두 개의 오해

왜 이 논쟁인가

미국 국립표준기술연구소(NIST)는 2016년, 양자컴퓨터에도 버틸 새 공개키 암호를 뽑는 표준화 작업을 시작했다 (arXiv:1912.00916, 프리프린트). 2017년 12월 69개 후보로 1라운드가 열렸고, 세 라운드의 평가를 거쳐 네 개의 알고리즘이 표준화 대상으로 뽑혔다. 그리고 키 확립 계열 후보 넷 — BIKE, Classic McEliece, HQC, 그리고 SIKE — 이 추가 분석을 위해 4라운드로 올라갔다 (DOI: 10.6028/nist.ir.8413).

SIKE는 이제 표준이 아니다. 양자컴퓨터에 깨져서가 아니다. 평범한 고전 컴퓨터에 깨졌다.

이 한 문장이 이 글의 목적지다. 양자컴퓨터 이야기에는 늘 같은 문장이 따라붙는다. "양자컴퓨터가 완성되면 지금의 암호는 전부 무용지물이 된다." 절반만 맞는 말이고, 틀린 절반이 훨씬 중요하다. 이 글은 두 가지 오해를 차례로 벗겨낸다. 첫째, '전부'가 아니다. 무너지는 것은 암호 전체가 아니라 그중 한 종류다. 둘째, '나중'이 아니다. 위험은 양자컴퓨터가 완성되는 날 시작되는 것이 아니라 이미 시작됐다. 그리고 세 번째로, 방금 말한 SIKE의 붕괴가 기다린다.

미리 분명히 해 두자. 이 글은 양자컴퓨터를 어떻게 만드는가를 다루지 않는다. 큐비트가 왜 깨지기 쉬운지, 오류정정이 어떻게 작동하는지는 다른 이야기다. 여기서는 "충분히 큰 양자컴퓨터가 언젠가 나온다면"을 조건으로 걸어 두고 그때 암호가 어떻게 되는지만 본다. 그리고 이 분야에 흔한 공포 조장도, 안심시키기도 하지 않는다.

통념: 양자컴퓨터가 완성되면 모든 암호가 무너진다

통념에는 근거가 있다. 1990년대에 알려진 두 양자 알고리즘 때문이다. 하나는 소인수분해와 이산로그를 다항 시간에 푸는 쇼어 알고리즘, 다른 하나는 탐색을 제곱근 수준으로 가속하는 그로버 알고리즘이다. 한 개관 논문의 요약은 이렇다. RSA·디피-헬만·타원곡선 암호(ECC)의 안전성은 소인수분해와 이산로그의 수학적 어려움에 기대는데, 고전 알고리즘으로는 지수 시간이 걸리는 이 문제들을 쇼어 알고리즘은 다항 시간에 푼다. 한편 그로버 알고리즘은 AES·3DES 같은 대칭키 방식의 키 탐색에 제곱근만큼의 시간 이득을 준다 (arXiv:2202.02826, 프리프린트).

"다 깨진다"는 결론까지는 한 걸음이다. 오늘날 인터넷 보안의 뼈대인 공개키 기반구조는 거의 전부 RSA와 ECC 위에 서 있다. 웹사이트 인증서, 메신저의 키 교환, 소프트웨어 서명, 블록체인 지갑까지. 이것이 한꺼번에 무너진다면 "전부"라는 말이 과장으로만 들리지는 않는다. 여기서 첫 번째 오해가 시작된다.

반전 ①: 무너지는 것은 자물쇠가 아니라 '열쇠 배달'이다

암호에는 크게 두 종류가 있다. 대칭키 암호는 잠그는 열쇠와 여는 열쇠가 같다. 파일을 비밀번호로 잠그는 것을 떠올리면 된다. 빠르고 튼튼하지만 상대와 같은 열쇠를 미리 나눠 가져야 한다. 공개키 암호는 그 문제를 푼다. 누구나 볼 수 있는 공개키로 잠그고 본인만 가진 개인키로 연다. 한 번도 만난 적 없는 서버와 안전하게 대화할 수 있는 것은 이 방식 덕분이다.

양자컴퓨터의 위협은 이 둘에 전혀 다른 크기로 작용한다. 양자·AI 시대의 암호 안전성을 검토한 리뷰는 이를 명확히 나눈다. RSA와 타원곡선 암호는 양자컴퓨터에 무력화될 위험에 놓여 있지만, AES-128 같은 대칭 알고리즘은 안전성을 유지한다 — 다만 양자 공격 아래에서 실효 키 길이가 줄어드는 형태로 (arXiv:2603.06969, 프리프린트). 즉 대칭키는 깨지는 게 아니라 약해질 뿐이며, 키를 길게 쓰면 상쇄된다. NIST 표준화 과정을 정리한 검토 논문도 같은 판단이다. 블록 암호와 해시 함수 같은 대칭 원시함수는 "아주 조금만(only slightly) 손상될 것"이라는 것이다 (DOI: 10.30837/rt.2022.3.210.05).

왜 이런 차이가 나는가. 128비트 키를 무차별 대입으로 찾는 데 고전적으로 2^128번의 시도가 필요하다면, 양자적으로는 대략 그 제곱근에 해당하는 노력이 든다. 분명 큰 이득이지만 키 길이를 두 배로 늘리면 원래 자리로 돌아온다. 반면 쇼어 알고리즘이 공개키에 주는 이득은 지수 시간에서 다항 시간으로의 도약이다. 키를 조금 늘려서는 따라잡을 수 없는 질적 차이다.

게다가 그로버 공격은 이론과 실제의 간극이 크다. 실제 하드웨어에서 간헐적인 오라클 실패가 있을 때의 강건성을 정량화한 연구는, 성공 확률이 급격히 무너지는 실용적 신뢰도 문턱이 문제 크기에 따라 지수적으로 낮아진다고 보고한다(문턱이 2^(−n/2)에 비례). n=40일 때조차 오라클이 대략 80만 번의 반복당 한 번 미만으로만 실패해야 양자 이득이 유지되며, 키가 커질수록 요구가 기하급수적으로 가혹해진다. 저자들의 결론은 현실적 하드웨어 제약 아래에서 그로버 기반 공격의 실현 가능성은 흔히 가정되는 것보다 상당히 낮을 수 있다는 것이다 (DOI: 10.20944/preprints202602.0122.v1, 프리프린트).

더 극단적인 계산도 있다. 양자 탐색의 열역학적 한계를 다룬 연구는 831비트 길이의 비밀키는 팽창하는 암흑에너지 지배 우주에서 별의 형성이 멈출 것으로 예상되는 시점까지도 결정론적으로 복원할 수 없다고 계산한다 (arXiv:2603.13654, 프리프린트). 우주론적 가정을 포함한 극한값이지 공학적 예측은 아니다. 하지만 방향은 분명하다. 충분히 긴 대칭키는 양자컴퓨터 앞에서도 사실상 멀쩡하다.

단, "대칭키는 안전하다"를 무조건으로 읽어서는 안 된다. 대칭 암호의 안전성은 무차별 대입 말고도 온갖 공격을 견뎌 온 실적 위에 있고, 그 실적을 양자 세계에서 다시 검증해야 한다. 차분·선형 분석의 양자 버전을 연구한 논문은 고전 세계에서 최선의 공격이 반드시 양자 세계에서도 최선은 아니라는 비직관적 결과를 보고한다 (arXiv:1510.05836, 프리프린트). 더 날카로운 경고도 있다. 공격자가 키가 심어진 함수에 양자 질의를 할 수 있다는 강한 모델에서는, 사이먼 알고리즘으로 3라운드 파이스텔 구조를 구분해 내거나 CBC-MAC에 대한 위조 공격을 성립시킬 수 있다 (DOI: 10.26421/qic17.1-2-4). 특정 구성의 문제이지 대칭 암호 전반의 붕괴는 아니지만, 고전적 안전성 증명을 양자 공격자 앞에서 다시 써야 한다는 뜻이다.

정리하면 이렇다. 무너지는 것은 금고의 자물쇠가 아니라 열쇠를 안전하게 배달하고 신원을 증명하는 방식 — 공개키다. 그리고 인터넷은 바로 그 배달 위에 지어져 있다.

반전 ②: 위험은 미래가 아니라 오늘 시작됐다

두 번째 오해는 시제(時制)에 관한 것이다. "양자컴퓨터가 나오면 그때 바꾸면 되지." 이 말이 성립하지 않는 이유는 하나다. 암호문은 저장할 수 있기 때문이다.

공격자는 지금 오가는 암호화된 통신을 그대로 긁어모아 보관해 둔다. 지금은 못 푼다. 하지만 언젠가 충분한 양자컴퓨터가 생기면 창고를 열어 과거의 통신을 소급 해독한다. 이것을 "수확은 지금, 해독은 나중(harvest now, decrypt later)"이라 부른다.

이 위협의 무서움은 경제학에 있다. TLS·QUIC·SSH에 걸쳐 공격자 비용을 정량화한 연구는 결론이 단호하다. 가로챈 트래픽을 보관하는 비용은 경제적으로 사소하다. 따라서 방어의 질문은 "공격자가 저장할 수 있는가"가 아니라 "해독에 얼마가 드는가"로 옮겨가야 한다. 이 연구는 저장량 부풀리기는 방어자에게도 부담을 지우지만 양자 연산 비용 부풀리기는 공격자만 겨냥하므로, 잦은 키 재협상(rekeying)과 큰 키 파라미터가 가장 강력한 방어 지렛대라고 본다 (arXiv:2603.01091, 프리프린트).

그렇다면 누가 지금 위험한가. 오늘 지켜야 할 비밀의 수명이 긴 쪽. 이 위협을 '시간 의존적 위험'으로 모델링한 연구는 이를 정량화한다. 위성 통신이나 보건의료처럼 데이터 보존 기간이 긴 부문은 전환이 늦어질 경우 수십 년에 이르는 노출 창(exposure window)에 놓인다. 반대로 하이브리드 키 교환과 전방향 비밀성(forward secrecy — 지금 쓰는 키가 나중에 털려도 과거 통신은 못 풀게 하는 성질) 같은 장치를 쓰면 그 위험 지평이 3분의 2 이상 줄어든다는 것이 이 모델의 결과다 (DOI: 10.3390/telecom6040100).

특히 얄궂은 사례가 블록체인이다. Finance and Economics Discussion Series에 실린 한 분석은 비트코인을 예로 든다. 운영 주체들이 양자내성 암호를 도입하면 앞으로의 보안과 무결성은 지킬 수 있지만, 이미 원장에 기록된 과거 거래들의 프라이버시는 여전히 취약하다. 누구든 원장 복제본을 보관해 두었다가 훗날 가려진 정보를 드러낼 수 있기 때문이다. 저자들은 이 격차에 대한 대응책이 부족하다고 지적한다 (DOI: 10.17016/feds.2025.093).

이 위협은 새로운 인식도 아니다. 독일어권의 2022년 논평은 같은 전략을 "훔치는 건 지금, 푸는 건 나중(Steal now, decrypt later)"이라 부르며 전문가들이 그 시점을 10~15년 뒤로 본다고 전했다 (DOI: 10.1007/s00287-022-01474-z). 확정된 예측이 아니라 2022년 시점의 기대치다. 뒤에서 보겠지만, 이런 시점 추정이야말로 가장 흔들리는 부분이다.

반전 ③: 양자컴퓨터가 오기도 전에, 후보가 노트북에 무너졌다

이제 서두로 돌아가자. 가장 극적인 붕괴는 양자컴퓨터가 일으키지 않았다.

SIKE는 아이소제니(isogeny) 기반 암호였다. 초특이 타원곡선 사이의 '좋은 사상(寫像)'을 찾는 문제가 어렵다는 가정 위에 지어졌고, 키가 훨씬 작다는 매력이 있었다. 그런데 4라운드가 진행되던 중, SIKE의 바탕이 되는 SIDH 키 교환에 대한 고전 컴퓨터 공격이 발표됐다. 양자컴퓨터가 아니라, 우리가 쓰는 그 컴퓨터로.

이 글은 원공격 논문 대신, 그 뒤에 나온 후속·분석 문헌이 이 사건을 어떻게 기록하고 있는지로 사건을 재구성한다. 그것만으로도 충분히 선명하다.

먼저 사건의 존재. 아이소제니-자기준동형환 문제를 다룬 2023년 논문은 이 문제가 "SIDH 키 교환을 깨뜨린 최근 공격들의 핵심에 있다"고 명시한다 (arXiv:2305.19897, 프리프린트). 아이소제니 계열 서명의 효율을 평가한 다른 논문은 이를 "SIDH(의 바탕이 되는 수학적 문제)에 대한 파괴적인 공격들"이라 부른다 (DOI: 10.1515/jmc-2023-0023).

무엇이 문제였나. SIDH 계열 프로토콜은 비밀 사상 자체는 감추지만, 그 사상을 곡선의 특정 부분군(비틀림점, torsion point)에 제한한 정보를 함께 공개한다. 이 부가 정보가 공격의 실마리였다. Castryck–Decru 공격을 완화하려는 연구는 이 공격이 드러낸 결함을 "비틀림점의 예측 가능성과 곡선 파라미터의 취약성"으로 요약한다 (DOI: 10.21203/rs.3.rs-4813769/v1, 프리프린트).

경고 신호는 그 전에도 있었다. 2020년의 한 논문은 2017년 Petit의 선행 연구가 "과도하게 늘린(overstretched)" 파라미터의 SIDH는 다항 시간에 깰 수 있음을 보였다고 전하며, 그 기법을 강화해 여러 변종을 실제로 깨뜨렸다. 그러면서도 저자들은 못 박았다 — "우리 결과는 NIST 제출본 SIKE의 안전성을 떨어뜨리거나 어떤 약점을 드러내지 않는다" (arXiv:2005.14681, 프리프린트). 위험 신호는 있었지만 표준 후보 본체는 안전해 보였다. 그 벽이 곧 무너졌다.

붕괴의 규모를 가늠하게 해 주는 가장 직접적인 진술은 후속 알고리즘 연구에서 나온다. 4차원 아이소제니 계산을 다룬 논문은 자신들의 성과를 이렇게 적는다. "시작 곡선의 자기준동형환을 모르는 경우에도, 모든 NIST SIKE 파라미터에 대해 노트북에서 수 초 안에 완전한 키 복구 공격을 수행할 수 있다" (arXiv:2407.15492, 프리프린트). 표준 후보의 모든 보안 수준이, 특수 장비도 아닌 노트북에서, 초 단위로 뚫린다는 뜻이다.

결말은 NIST 문서에 남아 있다. 4라운드 최종 보고서는 BIKE·Classic McEliece·HQC·SIKE 중 "표준화될 키 확립 알고리즘은 HQC뿐"이라고 적었다 (DOI: 10.6028/nist.ir.8545).

여기서 두 가지를 정확히 해 두자. 첫째, 아이소제니 암호 전체가 죽은 것은 아니다. 앞서 인용한 서명 연구는 파괴적 공격에도 자신들의 프로토콜은 다른(그리고 더 표준적인) 아이소제니 문제에 기대고 있어 여전히 안전하다고 밝힌다 (DOI: 10.1515/jmc-2023-0023). 이후 이 분야는 기초를 다시 다졌다. 한 연구는 아이소제니 문제·자기준동형환 문제·최대차수 문제가 일반화 리만 가설 같은 미증명 가정 없이도 서로 동치임을 증명했다 (arXiv:2502.17010, 프리프린트). 무너진 것은 SIDH라는 특정 설계이지 아이소제니라는 수학적 토대 전체가 아니었다.

둘째, 교훈은 "격자든 아이소제니든 다 못 믿는다"가 아니다. 훨씬 구체적이다. 양자내성 후보들의 안전성은 수학적 증명이 아니라 "아직 아무도 깨지 못했다"는 경험적 실적 위에 서 있다. 그리고 그 실적은 하루아침에 뒤집힐 수 있다.

메커니즘: 무엇이 왜 취약하고, 새 후보는 무엇에 기대는가

공개키만 취약한 이유 — 숨은 주기를 찾는다

RSA는 큰 수를 소인수로 쪼개기 어렵다는 데, 디피-헬만과 타원곡선 암호는 이산로그를 계산하기 어렵다는 데 안전성을 건다. 그런데 이 두 문제는 겉보기와 달리 같은 뿌리를 갖는다. 둘 다 어떤 연산을 반복했을 때 나타나는 숨은 주기(period)를 찾는 문제로 바꿔 쓸 수 있고, 주기 찾기는 양자컴퓨터가 특별히 잘하는 일이다 (arXiv:2202.02826, 프리프린트).

흥미로운 비대칭도 있다. 타원곡선 이산로그의 양자 자원을 정밀 추정한 연구는, n비트 소수체 위의 타원곡선이라면 최대 9n + 2⌈log₂n⌉ + 10개의 큐비트로 계산할 수 있다고 보고하면서, 같은 고전 보안 수준을 기준으로 타원곡선을 공격하는 데 필요한 큐비트 수가 RSA를 공격할 때보다 적다는 결론을 내린다 (arXiv:1706.06752, 프리프린트). 더 짧은 키로 같은 보안을 낸다는 ECC의 장점이 양자 세계에서는 오히려 불리하게 작용하는 셈이다.

새 후보들이 딛고 선 땅

무엇으로 대체하는가. NIST 표준화 과정을 체계적으로 검토한 논문은 후보군을 격자·부호·해시·다변수·아이소제니 기반의 다섯 계열로 정리한다. 8년에 걸친 공개 경쟁 끝에 2024년 8월 첫 세 개의 표준이 나왔고, 2025년 3월 네 번째 키 캡슐화 방식이 추가로 선정됐다 (DOI: 10.2139/ssrn.7128678).

격자 기반이 주력이다. 격자란 규칙적으로 배열된 점들의 무한한 격자무늬 같은 구조이고, 그 안에서 원점에 가장 가까운 0 아닌 점을 찾는 문제(최단 벡터 문제, SVP)가 어렵다는 가정에 기댄다. 해시 기반 서명은 해시 함수만 있으면 되므로 가정이 가장 보수적이지만 대가가 있다 — 앞서 인용한 리뷰는 그 서명 크기가 17~50KB에 이른다고 적는다 (arXiv:2603.06969, 프리프린트). 지금 쓰는 서명이 수십~수백 바이트인 것과 비교하면 수백 배다. 부호 기반은 무작위 선형 부호의 복호가 어렵다는 데 기댄다.

중요한 것은, 이 후보들 역시 양자 공격의 사정권 밖에 있는 것이 아니라 사정권 안에서 버티고 있다는 점이다. 격자의 SVP는 그로버 탐색을 응용한 양자 체질(sieving) 알고리즘의 표적이고, 그 지수는 계속 낮아져 왔다 — 한 연구는 기존 최선인 2^(0.2653d)를 2^(0.2570d)로 개선했다(d는 격자 차원) (arXiv:2105.05608, 프리프린트). 부호 기반도 마찬가지로 정보집합 복호의 양자 복잡도가 2^(0.06035n)에서 2^(0.05869n)로 낮아졌다 (arXiv:1703.00263, 프리프린트). 지수의 소수점 셋째 자리를 두고 벌어지는 이 싸움이, 양자내성이라는 말의 실제 내용이다.

옮기는 일이 왜 어려운가

새 알고리즘이 있다고 문제가 끝나지 않는다. 전환 자체가 거대한 공사다.

첫째, 크기. 양자내성 알고리즘은 키와 서명이 크고, 그 크기는 프로토콜의 물리적 제약과 충돌한다. 5G/IoT 환경을 분석한 연구는 372바이트짜리 SIB1 병목과 단편화 지연, 저전력 단말의 에너지 부담을 구체적 마찰 지점으로 든다 (DOI: 10.2139/ssrn.6412508). 모바일 기기에서 실측한 연구는 알고리즘 간 에너지·대역폭·지연 요구가 여러 자릿수에 걸쳐 벌어진다고 보고한다 (arXiv:1912.00916, 프리프린트).

둘째, 하이브리드. 새 알고리즘의 실적이 짧다는 문제를 다루는 현실적 방법은 기존 방식과 겹쳐 쓰는 것이다. 둘 중 하나가 깨져도 다른 하나가 남는다. 고전 키 교환에 격자 기반 키 캡슐화를 중첩한 한 시뮬레이션은 공개키가 약 1.2KB로 커지고 핸드셰이크 지연이 18% 증가하지만 감당할 만하다고 본다 (DOI: 10.15680/ijircce.2026.1406040).

셋째, 구현. 알고리즘이 안전해도 구현이 새면 소용없다. 표준화된 격자 기반 알고리즘들에 대한 부채널·결함주입 공격을 조사한 연구는 광범위한 공격 목록과 그에 맞춘 개별 대응책을 정리한다 (DOI: 10.1145/3603170).

넷째, 긴 꼬리. 무엇을 바꿔야 하는지조차 모르는 조직이 많다. 한 정적 분석 도구 연구는 대부분의 코드베이스가 자신들이 쓰는 고전 암호를 자동으로 목록화할 도구조차 갖추지 못했다고 지적한다 (arXiv:2604.00560, 프리프린트).

그래서 전환 기간 추정은 길다. 기업 규모별 일정을 종합한 연구는 소규모 기업 5~7년, 중견 8~12년, 대기업 12~15년 이상을 제시하며, 이것이 고립된 업그레이드가 아니라 생태계 전체의 동기화 과제라고 강조한다 (DOI: 10.3390/computers15010009). 비용의 구조도 얄궂다. 한 추정은 구글 한 곳의 도입 비용을 11.7억~38.5억 달러 규모로 잡으며, 일찍 도입하면 초기 비용과 인력 부담이 크고, 늦게 도입하면 비용은 싸지지만 소급 해독 위험을 떠안는다는 역설을 지적한다 (DOI: 10.36227/techrxiv.176583452.24018891/v1, 프리프린트). 이 액수는 특정 모델의 산물이므로 금액보다 구조를 읽는 편이 낫다.

논쟁·미해결: Q-day는 언제인가, 그리고 아무도 모른다

자원 추정치는 가정 위에 서 있다

"양자컴퓨터가 RSA를 깨려면 큐비트가 몇 개 필요한가." 이 질문의 답은 하나가 아니다. 가정을 바꾸면 몇 자릿수씩 달라진다.

널리 인용되는 값 하나는 이렇다. 양자 오류정정에 필요한 오버헤드를 감안하면 2048비트 RSA 키를 8시간 안에 인수분해하는 데 약 2천만 개의 (잡음 있는) 물리적 큐비트가 필요하다는 추정이다 (arXiv:2303.04656, 프리프린트). 이 숫자에는 "8시간 안에", "물리적 큐비트", "오류정정 오버헤드 포함"이라는 조건이 붙어 있다.

값을 낮추려는 시도도 활발하다. 타원곡선 공격 자원을 종합한 한 프리프린트는 순수 쇼어 알고리즘으로 NIST P-256 곡선을 깨는 데 2,330개의 논리 큐비트가 필요하다고 보면서, 최근의 공학적 혁신이 미래 요구량을 1.5~2.3배 줄일 수 있다고 전망하고 시나리오를 셋으로 나눈다 — 보수적(2033~2035), 현실적(2031~2033), 낙관적(2029~2031) (DOI: 10.20944/preprints202509.2429.v2). 다만 이 문헌은 동료심사를 거치지 않은 프리프린트이고, 시점 예측의 근거가 기업·정부 로드맵의 수렴이라는 점을 저자들 스스로 밝힌다. 로드맵은 계획이지 실적이 아니다. 같은 논문도 양자 메모리와 논리 연산 사이의 격차를 "주요 기술적 불확실성"으로 명시한다.

알고리즘 쪽에도 변수가 있다. 2023년 Regev가 제시한 다차원 인수분해 알고리즘은 게이트 수를 줄였지만 큐비트 요구량이 늘고, 증명되지 않은 정수론적 가정에 의존한다 (DOI: 10.54254/2755-2721/110/2024melb0122). 반대로 양자 자원을 획기적으로 줄였다고 주장한 어떤 제안은 검토 결과 고전 부분에 대한 복잡도 분석이 빠져 있었다 (arXiv:2303.04656, 프리프린트). 자원 추정은 아직 논쟁 중인 주제다.

"이미 인수분해했다"는 시연들의 함정

뉴스에서 "양자컴퓨터가 어떤 수를 인수분해했다"는 소식을 볼 때 주의할 지점이 있다. 여러 인수분해 실험의 회로를 뜯어본 연구는 뼈아픈 지적을 남긴다. 일부 실험의 회로는 목표 수의 위수(order)를 미리 알고 있다는 조건에서 구성됐다. 그런데 실제 알고리즘에서는 그 위수를 모르는 것이 문제의 전부다. 그런 회로는 쇼어 알고리즘의 설계로는 부적절하며, 나머지 실험들도 대상 합성수에 상당히 의존해 구성돼 있다는 것이다 (DOI: 10.1007/978-981-15-5191-8_7).

최근 연구자들도 같은 문제를 인정한다. 실제 하드웨어에서 쇼어 알고리즘을 실행한 한 연구는 기존 실험들이 "무거운 회로 컴파일에 의존해 의도치 않게 정답에 대한 사전 지식을 회로에 심어 넣고, 양자 산술이라는 핵심 난제를 우회한다"고 지적하며 투명한 기준선을 제시했는데, 그렇게 해서 다룬 수는 51, 85, 255, 771이었다 (DOI: 10.21203/rs.3.rs-9793578/v1, 프리프린트). 2048비트 RSA와의 거리는 여전히 아득하다.

새 표준도 언제 깨질지 모른다

반전 ③이 남긴 질문이 여기서 되돌아온다. 격자는 안전한가?

정직한 답은 "지금까지는 그렇다"이다. 양자 공격의 실효성에 관해서는 오히려 회의적인 방향의 근거가 있다. 격자 체질 알고리즘의 자원을 정밀 분석한 연구는, 회로 수준 잡음 10^-5 같은 매우 낙관적인 가정을 넣어도 차원 400(현재 제안된 최소 보안 수준에 대략 해당)의 SVP를 풀려면 약 10^13개의 물리적 큐비트와 약 10^31년이 필요하다고 계산했다. 저자들은 6GHz 단일 코어 고전 컴퓨터도 같은 문제에 거의 같은 시간이 걸린다며, 암호학적으로 유의미한 차원에서는 현재로선 양자 가속이 거의 없다고 결론짓는다 (arXiv:2410.13759, 프리프린트).

그러나 위협은 양자컴퓨터에서만 오지 않는다. SIKE가 그랬듯 고전적 돌파구가 더 빠를 수 있다. 최근에는 트랜스포머 모델로 격자 기반 암호의 근간인 LWE 문제를 공격하는 시도까지 나왔다 (DOI: 10.36227/techrxiv.174910091.18242062/v1, 프리프린트). 아직 실제 파라미터를 위협하는 수준은 아니지만, 공격 도구 자체가 계속 새로 생긴다는 사실만은 분명하다.

표준화 과정 안에도 미해결이 남아 있다. 앞서 인용한 체계적 검토는 일차 문헌들이 결론짓지 못한 긴장 지점 네 가지를 명시한다 — 왜 NIST는 키가 더 작은 BIKE 대신 HQC를 골랐는가, 왜 Falcon 계열 서명 표준은 형제 표준들이 확정된 뒤 2년 가까이 초안에 머물러 있는가, 표준화 이후에도 ML-KEM에 남은 구조적 한계는 무엇인가, 현재 표준화된 난제 가정들 중 무엇이 앞으로의 암호해독 발전을 견뎌 낼 가능성이 가장 높은가 (DOI: 10.2139/ssrn.7128678).

그럼에도 왜 지금 옮겨야 하는가

Q-day가 언제인지 모른다면 왜 지금 비용을 치러야 하는가. 논리는 단순하다. 지켜야 할 비밀의 수명 + 전환에 걸리는 시간 < 양자컴퓨터가 오기까지의 시간. 앞의 두 항이 각각 수십 년, 십수 년 규모라면, 세 번째 항이 아무리 불확실해도 여유는 이미 없다.

이것이 최근 문헌들이 시점 예측 대신 위험 관리로 옮겨가는 이유다. 어떤 연구는 조직이 무슨 암호를 어디서 쓰는지 목록화하는 암호 자재명세서(CBOM)부터 만들고 하이브리드 배치와 인증서 수명주기 자동화를 병행할 것을 권한다 (DOI: 10.37745/ejcsit.2013/vol13n523552). 목표는 하나다 — 암호 민첩성(crypto-agility), 즉 알고리즘을 언제든 갈아 끼울 수 있는 능력. 앞서 인용한 리뷰의 표현을 빌리면, 조직은 암호 보안을 고정된 배치가 아니라 지속되는 과정으로 다뤄야 한다 (arXiv:2603.06969, 프리프린트).

다만 여기에도 과장을 경계할 지점이 있다. 통계 모델로 양자 해독 가능성을 예측한 연구는 그 확률이 2029년까지 무시할 만하다가 2033년에 78.6%로 치솟는다는 수치를 내놓는다 (DOI: 10.9734/acri/2025/v25i31098). 이런 소수점 한 자리까지의 확률은 ARIMA·몬테카를로 같은 예측 모델과 그 입력 가정의 산물이지 물리학이 보증하는 값이 아니다.

의의: 암호의 안전은 증명이 아니라 시간을 견딘 실적이다

이 논쟁의 진짜 의미는 큐비트 개수에 있지 않다. 우리가 '안전하다'고 말할 때 그것이 무슨 뜻인지에 있다.

우리는 흔히 암호가 수학적으로 증명된 안전을 준다고 믿는다. 그러나 RSA도, 타원곡선도, 격자도, 아이소제니도, 그 안전성은 "이 문제는 어렵다"는 가정 위에 있다. 그 가정이 참이라는 증거는 대부분 "오랫동안 많은 똑똑한 사람들이 시도했지만 아직 못 깼다"는 실적이다. 실적은 증명이 아니다. 하루아침에 뒤집힐 수 있고, SIKE의 경우 실제로 그랬다.

이 관점에서 세 개의 반전은 하나의 이야기가 된다. 첫째, 위협은 균일하지 않다. 대칭키는 키를 늘리면 버티고, 무너지는 것은 공개키다. 둘째, 시간축이 통념과 반대다. 데이터의 수명이 긴 곳에서는 미래의 기계가 오늘의 통신을 이미 위협한다. 셋째, 위험의 원천은 양자컴퓨터만이 아니다. 표준 후보 하나는 노트북에 무너졌고, 그 사실은 새 표준들에도 똑같이 적용된다.

그래서 올바른 대응은 "언제 오는지 맞히기"가 아니라 "무엇이 오든 갈아 끼울 수 있게 만들기"다. 다음에 "양자컴퓨터가 오면 암호가 다 깨진다"는 문장을 보면 두 가지를 함께 떠올려도 좋겠다. 다 깨지지는 않는다. 그리고 기다릴 여유는 없다. 이 두 문장은 모순되지 않는다. 오히려 그 둘을 동시에 붙들 때에만, 공포도 안심도 아닌 자리에 설 수 있다.

---

근거 논문

• "Status report on the third round of the NIST PQC Standardization process" (2022) — DOI: 10.6028/nist.ir.8413 — 1라운드 69개 후보, 3라운드 선정 결과, BIKE·McEliece·HQC·SIKE의 4라운드 진출.
• "Status report on the fourth round of the NIST PQC standardization" (2025) — DOI: 10.6028/nist.ir.8545 — 4라운드에서 표준화되는 키 확립 알고리즘은 HQC뿐.
• "Post Quantum Cryptography: Techniques, Challenges, Standardization" (2022) — arXiv:2202.02826 (프리프린트) — 그로버는 대칭키에 제곱근 이득, 쇼어는 인수분해·이산로그를 다항 시간에 해결.
• "Securing Cryptography in the Age of Quantum Computing and AI" (2026) — arXiv:2603.06969 (프리프린트) — RSA·ECC는 위험, AES-128은 실효 키 길이 감소로 그침. 해시 기반 서명 17~50KB. 암호 보안은 지속 과정.
• "Status report on the third round of the NIST PQC standardization" (2022) — DOI: 10.30837/rt.2022.3.210.05 — 대칭 원시함수는 "아주 조금만" 손상될 것.
• "Practical Reliability Constraints on Grover-Based Attacks" (2026) — DOI: 10.20944/preprints202602.0122.v1 (프리프린트) — 신뢰도 문턱이 2^(−n/2)로 지수 감소, 그로버 공격 실현성은 통념보다 낮을 수 있음.
• "Thermodynamic Limits of Quantum Search" (2026) — arXiv:2603.13654 (프리프린트) — 831비트 키는 별 형성이 멈출 시점까지도 결정론적 복원 불가(우주론적 가정 포함).
• "Quantum Differential and Linear Cryptanalysis" (2015) — arXiv:1510.05836 (프리프린트) — 양자 가속이 모든 변종에 오지는 않으며, 최선의 고전 공격이 최선의 양자 공격은 아님.
• "Using Simon's algorithm to attack symmetric-key cryptographic primitives" (2017) — DOI: 10.26421/qic17.1-2-4 — 양자 오라클 모델에서 3라운드 파이스텔 구분자와 CBC-MAC 위조.
• "On the Practical Feasibility of Harvest-Now, Decrypt-Later Attacks" (2026) — arXiv:2603.01091 (프리프린트) — 저장 비용은 사소, 키 재협상과 키 크기가 가장 강한 방어 지렛대.
• "Harvest-Now, Decrypt-Later: A Temporal Cybersecurity Risk" (2025) — DOI: 10.3390/telecom6040100 — 고보존 부문 노출 창은 수십 년, 하이브리드·전방향 비밀성이 위험 지평 3분의 2 이상 축소.
• "'Harvest Now Decrypt Later': Data Privacy Risks for Distributed Ledgers" (2025) — DOI: 10.17016/feds.2025.093 — 전환해도 원장의 과거 거래 프라이버시는 취약하게 남음.
• "„Steal Now, Decrypt Later“" (2022) — DOI: 10.1007/s00287-022-01474-z — 전문가들은 당시 시점을 10~15년 뒤로 기대.
• "Hidden Stabilizers, ... the Cryptanalysis of pSIDH" (2023) — arXiv:2305.19897 (프리프린트) — "SIDH 키 교환을 깨뜨린 최근 공격들의 핵심"이라 명시.
• "Efficiency of SIDH-based signatures (yes, SIDH)" (2024) — DOI: 10.1515/jmc-2023-0023 — "SIDH에 대한 파괴적 공격"에도 다른 아이소제니 문제에 기댄 프로토콜은 안전하게 남음.
• "Strengthening SIDH Protocol Security: Mitigating the Castryck-Decru Attack" (2024) — DOI: 10.21203/rs.3.rs-4813769/v1 (프리프린트) — 결함은 비틀림점의 예측 가능성과 곡선 파라미터.
• "Improved torsion point attacks on SIDH variants" (2020) — arXiv:2005.14681 (프리프린트) — 비틀림점 정보가 탐색 난이도를 낮춤. 당시엔 "SIKE 안전성은 훼손하지 않음"이라 명시.
• "Fast computation of 2-isogenies in dimension 4" (2024) — arXiv:2407.15492 (프리프린트) — 모든 NIST SIKE 파라미터에 대해 노트북에서 수 초 내 완전한 키 복구 공격.
• "Unconditional foundations for supersingular isogeny-based cryptography" (2025) — arXiv:2502.17010 (프리프린트) — 아이소제니 난제들의 무조건적 동치성.
• "Quantum resource estimates for computing elliptic curve discrete logarithms" (2017) — arXiv:1706.06752 (프리프린트) — ECDLP 큐비트 상한, ECC가 RSA보다 쉬운 표적.
• "Post-Quantum Cryptography: A Systematic Review" (2026) — DOI: 10.2139/ssrn.7128678 — 다섯 계열 분류, 2024년 8월 첫 세 표준·2025년 3월 네 번째 KEM, 미해결 긴장 4가지.
• "Lattice sieving via quantum random walks" (2021) — arXiv:2105.05608 (프리프린트) — SVP 양자 체질 복잡도를 2^(0.2653d)에서 2^(0.2570d)로 개선.
• "Quantum Information Set Decoding Algorithms" (2017) — arXiv:1703.00263 (프리프린트) — 무작위 선형 부호 복호의 어려움, 양자 복잡도 2^(0.06035n)→2^(0.05869n).
• "From Harvest-Now-Decrypt-Later to Quantum-Safe 5G/IoT" (2026) — DOI: 10.2139/ssrn.6412508 — 372바이트 SIB1 병목, 단편화 지연, 저전력 단말 에너지 부담.
• "Mobile Energy Requirements of the Upcoming NIST PQC Standards" (2019) — arXiv:1912.00916 (프리프린트) — NIST 표준화 2016년 개시, 후보 간 에너지·대역폭·지연이 여러 자릿수 차이.
• "Architecting for Longevity: A Hybrid Cryptographic Framework" (2026) — DOI: 10.15680/ijircce.2026.1406040 — 하이브리드 시 공개키 약 1.2KB, 핸드셰이크 지연 18% 증가.
• "Side-channel and Fault-injection attacks over Kyber, Dilithium" (2024) — DOI: 10.1145/3603170 — 구현에 대한 공격 목록과 맞춤 대응책.
• "Quantum-Safe Code Auditing" (2026) — arXiv:2604.00560 (프리프린트) — 대부분의 코드베이스가 고전 암호 사용 목록화 도구조차 없음.
• "Enterprise Migration to PQC: Timeline Analysis" (2025) — DOI: 10.3390/computers15010009 — 소기업 5~7년, 중견 8~12년, 대기업 12~15년 이상.
• "Feasibility of Post-Quantum Cryptography Adoption" (2025) — DOI: 10.36227/techrxiv.176583452.24018891/v1 (프리프린트) — 구글 도입 비용 11.7억~38.5억 달러 추정, 조기 도입 vs 지연의 역설.
• "Pitfalls of the sublinear QAOA-based factorization algorithm" (2023) — arXiv:2303.04656 (프리프린트) — 2048비트 RSA 8시간 인수분해에 약 2천만 물리 큐비트 추정, sublinear 주장의 분석 누락.
• "Quantum Resource Requirements for Breaking Elliptic Curve Cryptography" (2025) — DOI: 10.20944/preprints202509.2429.v2 (프리프린트) — P-256에 논리 큐비트 2,330개, 시나리오별 2029~2035년(로드맵 기반).
• "An Overview of Regev's Quantum Factoring Algorithm" (2024) — DOI: 10.54254/2755-2721/110/2024melb0122 — 게이트 수는 줄지만 큐비트 요구 증가, 미증명 정수론 가정 의존.
• "Quantum Factoring Algorithm: Resource Estimation and Survey" (2020) — DOI: 10.1007/978-981-15-5191-8_7 — 일부 실험 회로가 위수를 미리 아는 조건에서 구성됨.
• "Factoring Some Integers Using Shor's Algorithm on Real Quantum Hardware" (2026) — DOI: 10.21203/rs.3.rs-9793578/v1 (프리프린트) — 컴파일이 정답 사전 지식을 심는다는 지적, N ∈ {51, 85, 255, 771}.
• "On the practicality of quantum sieving algorithms for the shortest vector problem" (2024) — arXiv:2410.13759 (프리프린트) — 차원 400 SVP에 10^13 물리 큐비트·10^31년, 양자 가속 거의 없음.
• "Red Team Cryptanalysis of Lattice-Based PQC Using Transformers" (2025) — DOI: 10.36227/techrxiv.174910091.18242062/v1 (프리프린트) — LWE에 대한 트랜스포머 공격의 실증 평가.
• "The Quantum Security Deadline: Building Crypto-Agility" (2025) — DOI: 10.37745/ejcsit.2013/vol13n523552 — CBOM·하이브리드 배치·인증서 수명주기 자동화 중심의 암호 민첩성 로드맵.
• "Future-Proofing Data" (2025) — DOI: 10.9734/acri/2025/v25i31098 — ARIMA·몬테카를로 기반 양자 해독 확률 예측(2029년까지 무시 가능, 2033년 78.6%).