💻 computer science

Quantum Cryptanalysis on IBM Quantum Hardware: Extending Even--Mansour Period Recovery from $N=4$ to $N=10$

이 논문은 이븐-맨스어(Even-Mansour) 및 피스텔(Feistel) 암호 구조의 숨겨진 주기를 복구하기 위해 사이먼(Simon) 알고리즘을 사용하는 교과서적으로 충실한 양자 암호 해독을 기록적인 크기(N=10)까지의 실제 IBM 양자 하드웨어에서 컴파일되지 않은 상태로 구현한 진정한 시연을 제시하며, 동시에 그 범위, 오류 완화 의존성 및 전체 규모의 현대 암호에 대한 위협 부재에 관한 명시적인 주의 사항과 함께 네 가지 대칭 암호 패러다임에 걸친 다섯 가지 공격에 대한 포괄적인 벤치마크를 제공한다.

원저자: Taebong Kim, Youngsik Hong, Minsik Kim, Sunyoung Choi, Jaewon Jang, Junghoon Shin, Minseo Kim

게시일 2026-07-22

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Taebong Kim, Youngsik Hong, Minsik Kim, Sunyoung Choi, Jaewon Jang, Junghoon Shin, Minseo Kim

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

비밀 코드가 단순히 금고 안에 잠겨 있는 것이 아니라, 오직 유령만이 통과할 수 있는 미로 속에 숨겨져 있는 세상을 상상해 보십시오. 이것이 바로 양자 암호 해독(quantum cryptanalysis)의 영역입니다. 이는 연구자들이 디지털 자물쇠가 실제로 얼마나 강력한지 테스트하기 위해 양자 물리학의 기묘하고도 신비로운 규칙들을 사용하는 과학의 한 분야입니다. 이를 이해하려면 세 가지 간단한 사실을 알아야 합니다. 첫째, "대칭 암호(symmetric ciphers)"는 보물 상자를 잠그고 여는 단 하나의 열쇠와 같습니다. 열쇠가 있으면 열 수 있지만, 없으면 꼼짝도 할 수 없습니다. 둘째, "양자 컴퓨터(quantum computers)"는 일반 컴퓨터가 하나의 경로를 시도하고, 그다음 경로를 시도하고, 또 그다음 경로를 시도해야 하는 것과 달리, 미로의 많은 경로를 동시에 시도할 수 있는 특별한 기계입니다. 마지막으로, "사이먼 알고리즘(Simon's algorithm)"이라는 유명한 기술은 혼란스러운 무리 속에서 숨겨진 패턴을 일반 탐정보다 훨씬 빠르게 찾아내는 매우 똑똑한 탐정과 같습니다. 단, 그 무리가 매우 특정한 반복 구조를 가지고 있을 때만 가능합니다.

왜 사람들이 이것에 관심을 가질까요? 양자 컴퓨터가 이러한 패턴을 쉽게 찾아낼 수 있다면, 우리 은행 계좌, 메시지, 그리고 국가 기밀을 보호하는 비밀 키들이 깨질 수 있기 때문입니다. 하지만 여기에는 함정이 있습니다. 실제로 이 일을 수행할 만큼 크고 조용한 양자 컴퓨터를 만드는 것은 매우 어렵습니다. 현재의 양자 컴퓨터는 마치 록 콘서트장에서 속삭임을 들으려는 것처럼 매우 소란스럽습니다(noisy). 이 논문은 실제 세계에서 가능한 한계를 밀어붙이며, 실제의 소란스러운 양자 컴퓨터에게 비밀 코드 속의 숨겨진 패턴을 찾는 법을 가르치려 노력한 연구팀에 관한 이야기입니다.

논문: 소란스러운 무대 위의 양자 탐정

IBM의 실제 양자 컴퓨터(구체적으로 "ibm_kingston" 칩)를 사용하여 "숨겨진 패턴 찾기" 게임을 하기로 결정한 연구진은 **이븐-맨소어 암호(Even-Mansour cipher)**라고 불리는 특정 유형의 비밀 코드 구조에 집중했습니다. 이 암호를 하나의 기계라고 상상해 보십시오. 이 기계는 비밀 숫자(키)를 입력받아 메시지를 뒤섞습니다. 공격의 목표는 이 기계가 데이터를 뒤섞는 방식에 담긴 "주기(period)"—즉, 숨겨진 반복 리듬—를 찾아내는 것입니다. 만약 그 리듬을 찾는다면, 비밀 키를 알아낼 수 있습니다.

과거에 과학자들은 아주 작고 단순한 버전의 코드(비밀 숫자가 단 4비트인 경우)에 대해서만 실제 하드웨어에서 이를 수행하는 데 성공했습니다. 이 팀은 실제 기계가 어디까지 갈 수 있는지 확인하고 싶었습니다. 그들은 비밀 숫자가 10비트인 버전에서도 숨겨진 리듬을 성공적으로 찾아냈습니다. 여러분에게는 그리 많아 보이지 않을 수도 있지만, 양자 하드웨어의 세계에서 4에서 10으로 점프하는 것은 엄청난 도약입니다. 그것은 마치 외발로 서 있는 것에서 줄타기 위에서 마라톤을 하는 것으로 넘어가는 것과 같습니다.

그들은 여기서 멈추지 않았습니다. 그들은 또한 다른 유형의 코드 구조에 대해서도 탐정 기술을 테스트했습니다:

3라운드 페이스텔(3-Round Feistel): 유명한 DES와 같은 오래된 코드에서 사용되는 구조입니다. 그들은 블록 크기가 6과 8인 경우에도 숨겨진 리듬을 성공적으로 찾아냈습니다.
번스타인-바지라니(Bernstein-Vazirani): 더 단순한 선형 퍼즐입니다. 그들은 단 **한 번의 질문(query)**만으로 16비트의 비밀을 찾아냈으며, 이는 수학적 예측과 정확히 일치했습니다.
그로버 알고리즘 검색(Grover's Search): 구조화되지 않은 키를 찾는 방법을 테스트하여, 일반 컴퓨터는 256단계가 필요한 상황에서 양자 컴퓨터가 약 13단계 만에 키를 찾을 수 있음을 보여주었습니다.

현실적인 점검: 결과는 어떠했는가?

이 부분이 이야기에서 가장 중요한 부분이며, 저자들이 매우 솔직하게 밝히는 부분입니다. 비록 그들이 패턴을 찾아내기는 했지만, 오늘 당장 여러분의 은행 계좌를 털 수 있을 정도로 코드를 깨뜨린 것은 아닙니다.

더 큰 퍼즐(비밀이 6비트 이상인 경우)의 경우, 양자 컴퓨터는 다소 "소란스러워지고(noisy)" 혼란을 겪었습니다. 즉, 즉시 단 하나의 정답을 가리키지 못했습니다. 대신, 상위 후보 목록을 제시했습니다. 연구진은 이 양자 목록에서 상위 16, 32, 64 또는 128개의 후보를 일반 컴퓨터를 사용하여 검사했습니다. 실제 비밀 키는 대개 그 목록의 상단(종종 상위 63위 이내)에서 발견되었습니다. 이는 무작위로 추측하는 것보다 훨씬 나은 결과입니다.

저자들은 매우 명확하게 밝힙니다: 이것은 아직 "양자 우위(quantum advantage)"가 아닙니다.

마법의 탄환은 없다: 그들은 AES나 RSA와 같은 유명한 코드의 완전한 실전 버전을 깨뜨리지 못했습니다. 그들은 단지 구조의 단순화되고 축소된 버전만을 깨뜨렸을 뿐입니다.
초고속은 아니다: 더 큰 퍼즐의 경우, 양자 컴퓨터가 혼자서 모든 것을 해결하지 못했습니다. 양자 컴퓨터는 용의자 목록을 좁혀주었지만, 최종 작업은 여전히 일반 컴퓨터가 수행해야 했습니다. 그들이 본 속도 향상은 전체 시간을 단축한 것이 아니라, 질문을 던지는 횟수에서의 속도 향상이었습니다.
소음 대 완벽함: 그들은 "오류 수정(error correction, 오류를 완벽하게 고치는 것)" 대신 "오류 완화(error mitigation, 소란스러운 데이터를 정화하는 것)"를 사용했습니다. 이는 그들의 결과가 현재의 기술 수준에서는 인상적이지만, 최종적이고 완벽한 해결책은 아님을 의미합니다.

큰 그림

연구팀은 이 작업이 완벽하고 소음이 없는 기계가 있다면 어디까지 갈 수 있는지 확인하기 위해 슈퍼컴퓨터에서 대규모 시뮬레이션을 실행했습니다. 그들은 양자 컴퓨터가 이론적으로 이러한 퍼즐을 쉽게 처리할 수 있는 반면, 일반 컴퓨터는 단 25 큐비트(양자 정보의 기본 단위)의 양자 컴퓨터를 시뮬레이션하려고 하면 메모리가 부족해질 것이라는 점을 발견했습니다. 약간 더 큰 퍼즐은 4.5 페타바이트의 메모리를 필요로 하는데, 이는 대부분의 데이터 센터가 보유한 양보다 많습니다!

그렇다면 결론은 무엇일까요? 이 논문은 실제의 소란스러운 양자 컴퓨터가 성공적으로 분석할 수 있는 비밀 코드 구조의 크기에 대한 "세계 기록"입니다. 이는 하드웨어가 여전히 다소 불안정할지라도, 수학적 원리가 실제 하드웨어에서도 작동함을 증명합니다. 이는 "우리는 이 일을 할 수 있지만, 실제 세상의 비밀을 정말로 깨뜨리기 위해서는 더 좋고 조용한 기계가 필요하다"는 것을 보여주는 개념 증명(proof of concept)입니다. 저자들은 누구나 자신들의 작업을 확인할 수 있도록 코드와 데이터를 공개하였으며, 이를 통해 이것이 단순한 주장이 아니라 양자 컴퓨터와 비밀 코드 사이의 경쟁에서 재현 가능한 진전임을 보장했습니다.

기술 요약: IBM 양자 하드웨어에서의 양자 암호 해독 (Quantum Cryptanalysis)

문제 정의

이론적 연구는 Even–Mansour 암호 및 3라운드 Feistel 네트워크와 같은 특정 대칭 암호 구조가 Simon의 알고리즘으로 해결 가능한 숨겨진 주기 문제(hidden-period problems)로 환원될 수 있음을 오랫동안 입증해 왔습니다. 그러나 이러한 이론적 환원과 노이즈가 있는 중규모 양자(NISQ) 장치에서의 실제 실행 사이에는 상당한 격차가 존재합니다. 본 연구 이전의 실물 하드웨어 기반 키 복구 시연은 장치의 노이즈와 결함 허용 오류 정정(fault-tolerant error correction)의 부재로 인해 매우 작은 보안 파라미터(구체적으로 $N=4$ )에 국한되어 있었습니다. 핵심 과제는 트랜스파일링(transpilation)을 통한 지름길을 사용하여 탐색을 사소하게 만드는 것이 아니라, 실제 키 매핑을 구현하는 "진정한(genuine)" 알고리즘 무결성을 유지하면서 더 큰 구조 크기( $N > 4$ )로 공격을 확장하는 것입니다.

방법론

저자들은 Qiskit 프레임워크를 사용하여 IBM ibm_kingston 프로세서(Herreon 세대)에서 "진정한 미컴파일, 교과서적 충실성(genuine-un-compiled, textbook-faithful)"을 갖춘 양자 암호 해독을 수행했습니다. 이 방법론은 다음 구성 요소들로 특징지어집니다:

알고리즘 범위: 본 연구는 네 가지 대칭 암호 설계 패러다임을 대상으로 합니다:
1. 선형 구조: Bernstein–Vazirani 알고리즘 (단일 쿼리).
2. 비구조적 탐색: 축소된 SPN (Substitution-Permutation Network) 키 탐색에 적용된 Grover 알고리즘.
3. 숨겨진 주기 문제: 다음 알고리즘에 적용된 Simon의 알고리즘:
  - Even–Mansour 암호.
  - CBC-MAC 위조.
  - 3-라운드 Feistel (DES 계열) 구조.
실행 전략:
- 실제 하드웨어: 실험에는 결함 허용 오류 정정 대신 포괄적인 판독 오류 완화 스택(교정, 동적 디커플링, 트월링 포함)이 활용되었습니다.
- $N > 5$ 를 위한 하이브리드 접근법: 노이즈로 인해 "rank-1" 복구가 불가능한 Even–Mansour 인스턴스의 경우, 저자들은 양자 압축(quantum-narrowing) + 클래식 검증 하이브리드 방식을 채택했습니다. 양자 회로는 상위 순위 후보군(예: 상위 16개 또는 128개)을 생성하며, 이후 클래식 방식으로 검증됩니다.
- 검증: 복구된 주기가 특정 키 선택의 결과물이 아님을 보장하기 위해 모든 하드웨어 결과는 독립적인 제어 키(control keys)와 교차 검증되었습니다.
- 시뮬레이션: 미컴파일된 회로를 검증하기 위해 NVIDIA B200 하드웨어를 사용한 진정한 상태 벡터 시뮬레이션(genuine statevector simulation)을 통해 폭 우선 벤치마크를 수행했습니다 (최대 25 큐비트까지).

주요 결과

1. 실제 하드웨어 경계의 확장

본 논문은 실제 하드웨어에서 보안 파라미터 $N = 10$ 까지의 Even–Mansour 숨겨진 주기를 복구했음을 보고합니다.

$N = 5$ : 클린한 rank-1 복구(differential Simon)를 달성하여 실제 키가 최상위 후보로 나타났습니다.
$N = 6$ ~ $N = 10$ : 하이브리드 접근법을 통해 달성되었습니다. 노이즈로 인해 실제 키가 항상 단일 최상위 출력은 아니었으나, 그 순위는 생일 경계(birthday bound)( $2^{n/2}$ )를 추적하며 무작위 기대치( $2^{n-1}$ )보다 수 자릿수 낮은 수준을 유지했습니다.
비교: 이는 이전에 보고된 가장 큰 실제 하드웨어 크기인 $N = 4$ 를 초과하는 수치입니다.

2. Feistel 및 선형 구조 복구

3-라운드 Feistel: 실제 하드웨어에서 블록 크기 6 및 8에 대해 주기를 클린하게 복구했습니다 (rank-1, 정확함). 21-큐비트 블록-10 인스턴스는 시뮬레이션에서 검증된 후 하드웨어로 제출되었습니다.
Bernstein–Vazirani: 실제 하드웨어에서 단일 쿼리로 16비트 선형 비밀을 성공적으로 추출했습니다.

3. 복잡도 분리

본 연구는 이론적인 쿼리 복잡도 분리를 입증합니다:

Simon 기반 공격: 지수적 클래식 쿼리 복잡도( $2^{n/2}$ ) 대비 다항식 양자 쿼리 복잡도( $\Theta(n)$ ).
Grover 기반 공격: 이차적 가속 (예: 8비트 키를 256회의 클래식 평가 대신 약 13회의 반복으로 복구).

의의 및 주장

저자들은 "양자 우위(quantum advantage)"를 과장하지 않고 정직성과 재현성에 초점을 맞추어 기여를 명시적으로 프레임화했습니다.

실제 하드웨어 시연: 주요 기여는 기록적인 구조 크기( $N=10$ for Even–Mansour)에 대해 실제 하드웨어에서 진정한 양자 암호 해독을 시연함으로써, 이론적 환원과 물리적 실행 사이의 간극을 메운 것입니다.
포괄적 범위: 본 연구는 네 가지 서로 다른 암호학적 패러다임(선형, 비구조적, 숨겨진 주기)과 다섯 가지 특정 공격에 걸친 포괄적인 벤치마크를 제공하며, 이들은 모두 클래식 시뮬레이션 한계까지 검증되었습니다.
엔드 투 엔드 양자 우위 부재: 논문은 이러한 공격들이 엔드 투 엔드 비용 측면에서 클래식 방법론에 대한 양자 우위를 구성하지 않는다고 명시적으로 밝힙니다. 공격은 점근적으로 생일 경계를 따르므로, 클래식 충돌 탐색이 유사한 스케일링을 달 Erkennt 합니다. 분리는 전체 계산 비용이 아닌 쿼리 복잡도에서의 구분입니다.
범위 제한:
- 공격은 현대적인 풀 스케일 AES, RSA 또는 16-라운드 DES가 아닌 축소되거나 구조화된 구성(Even–Mansour, 3-라운드 Feistel, 축소된 SPN)을 대상으로 합니다.
- 결과는 결함 허용 오류 정정이 아닌 **오류 완화(error mitigation)**에 의존합니다.
- Q2 (양자 쿼리) 오라클 모델이 가정되었으나, 저자들은 이것의 실제적 한계를 인정하며 오프라인-Simon 환원을 통해 Q1으로 완화할 수 있음을 언급했습니다.

요약하자면, 본 논문은 NISQ 하드웨어에서 진정한 양자 알고리즘의 엄격하고 재현 가능한 벤치마크 역할을 하며, 현재의 장치가 현대의 전체 규모 암호를 깨지는 못하더라도, 이전에 실제 하드웨어에서 도달할 수 없었던 크기의 구조화된 프리미티브에 대해 복잡한 암호 해독 환원을 성공적으로 실행할 수 있음을 입증합니다.