⚛️ quantum physics

How Not to Build Microcrypt

원저자: Aditya Gulati (UCSB), Dakshita Khurana (UIUC,NTT Research), Kabir Tomer (UIUC)

게시일 2026-09-25

📖 5 분 읽기🧠 심층 분석

원저자: Aditya Gulati (UCSB), Dakshita Khurana (UIUC,NTT Research), Kabir Tomer (UIUC)

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

양자 암호학이라는 조용하고도 이해관계가 첨예한 세계에서, 과학자들은 양자 역학의 기묘한 법칙을 사용하는 컴퓨터조차도 풀 수 없는 자물쇠를 만들기 위해 노력하고 있습니다. 수십 년 동안 모든 보안 통신의 기초는 '일방향 함수(one-way function)'였습니다. 이는 잠그기는 쉽지만 특정 키 없이는 푸는 것이 매우 어려운 수학적 자물쇠입니다. 그러나 '마이크로크립트(Microcrypt)'라 불리는 새로운 영역이 등장했습니다. 이곳은 전통적인 일방향 자물쇠가 존재하지 않더라도 연구자들이 보안 양자 시스템을 구축할 수 있기를 희망하는 이론적 영역입니다. 목표는 더 약한 가설을 찾아내어, 그럼에도 불구하고 비밀을 보호할 수 있을 만큼 충분히 강력한 기반을 만드는 것입니다. 이를 위해 그들은 '의사 난수 상태(pseudorandom states)'와 '의사 난수 유니터리(pseudorandom unitaries)' 같은 새로운 유형의 디지털 객체들을 제안했습니다. 이들은 비밀 키를 가진 사람에게는 무작위 노이즈처럼 보이도록 설계되었지만, 실제로는 특정한 숨겨진 과정에 의해 생성된 것들입니다. 큰 의문은 이 새로운 객체들이 기존의 더 강력한 자물쇠에 의존하지 않고도 진정으로 존재할 수 있는지, 아니면 은밀하게 그것들에 의존하고 있는가 하는 점이었습니다.

캘리포니아 대학교 산타바버라, 일리노이 대학교, 그리고 NTT 리서치의 연구팀은 이제 많은 주요 후보군에 대해 결정적인 "아니오"라는 답을 내놓았습니다. 그들은 이러한 양자 객체들을 분석하는 새로운 방법을 개발했으며, 전통적인 일방형 함수 없이도 안전할 것이라고 믿어졌던 여러 인기 있는 설계들이 특정 유형의 강력한 공격자 앞에서 실제로 실패한다는 것을 증명했습니다. 그들의 연구는 만약 당신이 특정 흔한 건축 설계도를 사용하여 이러한 양자 자물쇠를 만들려고 시도한다면, 의도치 않게 전통적인 일방향 함수를 만들어내게 된다는 것을 보여줍니다. 이는 일방향 함수보다 약한 토대 위에 양자 암호학을 구축하려는 약속이 예상보다 훨씬 더 어렵다는 것을 의미하며, 현재 가장 유력한 설계 중 상당수가 해결책이 될 수 없음을 뜻합니다.

연구진의 돌파구는 '섀도 토모그래피(shadow tomography)'라고 부르는 기술에서 나왔습니다. 이는 양자 상태를 가져와서 그것의 압축된 고전적 기록을 만드는 방법입니다. 복잡하고 보이지 않는 물체의 형상을 이해하기 위해 다양한 각도에서 빛을 비추고 그 그림자를 기록한다고 상상해 보십시오. 양자 세계에서 이 과정은 양자 상태의 복사본들을 측정하여 그 구조에 대한 정보를 수집하는 것을 포함합니다. 연구팀은 이러한 제안된 양자 상태들의 대다수에 대해, 그림자로부터 수집된 정보가 매우 구조화되어 있어서, 특정 유형의 논리적 조력자인 'NP 오라클(NP oracle)'에 접근할 수 있는 컴퓨터가 이를 이용해 비밀 키를 역설계할 수 있다는 사실을 깨달았습니다. NP 오라클은 특정 유형의 복잡한 탐색 문제를 즉각적으로 해결할 수 있는 이론적 도구로, 모든 가능성을 하나씩 일일이 시도하지 않고도 솔루션이 존재하는지 확인할 수 있는 초지능적 조수 역할을 합니다.

연구진은 제안된 많은 양자 상태에 대해, 비밀 키를 찾는 과정이 이 조수의 단순한 탐색 작업이 된다는 것을 입증했습니다. 그들은 만약 양자 상태가 '계산 가능하다(computable)', 즉 내부 숫자들이 표준 컴퓨터에 의해 계산될 수 있다면, 특정 유형의 조력을 가진 공격자가 효율적으로 키를 알아낼 수 있음을 보여주었습니다. 이는 시스템의 보안을 효과적으로 무너뜨립니다. 연구팀은 이 방법을 널리 안전한 빌딩 블록으로 믿겨왔던 '해밀토니안 페이즈 상태(Hamiltonian Phase States)'라는 저명한 후보군에 적용했습니다. 그들의 분석은 이러한 상태들이 안전하지 않음을 증명했습니다. 만약 이 상태들이 존재한다면, 그것은 전통적인 일방향 함수의 존재를 함의합니다. 이 결과는 이 특정 설계가 일방향 함수의 필요성을 우회할 수 있다는 희망을 산산조각 냈습니다.

조사는 상태(states)에서 멈추지 않았습니다. 연구진은 시선을 '의사 난수 유니터리(pseudorandom unitaries)'로 돌렸습니다. 이것들은 데이터를 무작위처럼 보이게 변환하는 더 복잡한 양자 연산입니다. 이들은 마이크로크립트 도구 상자에서 가장 강력한 도구로 간주됩니다. 연구팀은 가장 유망한 설계들에서 공통적으로 발견되는 건축 패턴을 식별했습니다. 그것은 간단하고 예측 가능한 층이 두 개의 '클리포드(Clifford)' 연산(특정한 유형의 양자 게이트) 사이에 샌드위치처럼 끼어 있는 구조입니다. 그들은 CMC 구조라고 알려진 이 특정 배치가 뚜렷한 지문을 남긴다는 것을 발견했습니다. 얽힌 입자 쌍을 이용한 특수한 측정 방식을 통해, 중간 층에 숨겨진 치환(permutation)에 대한 고전적 단서를 추출할 수 있었습니다. 이 조력자의 도움을 받으면, 관찰된 모든 단서를 설명하는 키를 검색할 수 있습니다. 만약 유니터리가 진정으로 무작위였다면, 단 하나의 키도 모든 단서를 설명할 수 없을 것입니다. 하지만 만약 그것이 이 특정 아키텍처를 사용하여 만들어졌다면, 올바른 키는 항상 단서들과 완벽하게 들어맞을 것입니다.

이 발견은 최근의 수많은 보안 양자 유니터리 제안들, 즉 일방향 함수를 피하도록 명시적으로 설계된 것들까지도 광범위하게 취약하다는 것을 의미합니다. 연구진은 이러한 설계들이 진정한 무작위성과 구별될 수 있으며 그 비밀 키가 복구될 수 있음을 보여주었습니다. 그들은 'PFC(Permutation-Function-Clifford)' 구조 및 다양한 'LRFC(Luby-Rackoff-Function-Clifford)' 설계와 같이 잘 알려진 여러 구성 모델들을 대상으로 이 방법을 테스트했습니다. 중간 층이 단순한 치환이나 페이즈 시프트(phase shift)인 모든 경우에 공격은 성공했습니다. 연구팀은 이러한 아키텍처들이 마이크로크립트의 토대가 될 수 없음을 증명했는데, 왜냐하면 그것들은 필연적으로 일방향 함수로 다시 돌아가게 되어, 약한 가설 위에 암호학을 구축하려는 목적 자체를 무색하게 만들기 때문입니다.

하지만 이 논문이 마이크로크립트의 문을 완전히 닫는 것은 아닙니다. 연구진은 어떤 설계가 공격에서 살아남았고 어떤 설계가 그렇지 못했는지를 정밀하게 지도화했습니다. 그들은 여러 겹으로 겹쳐진 혼합 층을 포함하거나 끝단에 비밀스러운 비-클리포드(non-Clifford) 연산을 사용하는 구성들이 여전히 안전할 수 있음을 발견했습니다. 이러한 생존 후보들이 향후 연구의 초점이 될 것입니다. 이 연구는 분야를 위한 중요한 가이드, 즉 '가드레일' 역할을 합니다. 이는 과학자들에게 무엇을 만들지 말아야 할지를 알려주어, 근본적으로 결함이 있는 청사진에 시간을 낭비하는 것을 방지합니다. 이러한 흔한 접근 방식들을 배제함으로써, 연구진은 커뮤니티가 의도치 않게 일방향 함수를 만들어내는 것이 아닌, 근본적으로 다른 아키텍처를 찾도록 강제했습니다.

이 연구의 함의는 미래의 양자 보안에 있어 매우 심오합니다. 이는 일방향 함수 없이 양자 암호학을 구축하는 길이 이전에 생각했던 것보다 훨씬 더 좁고 험난하다는 것을 명확히 해줍니다. 연구진은 새로운 제안들을 테스트할 수 있는 엄격한 방법을 제공하여, 미래의 설계들이 단순히 이론적으로 흥미로운 것에 그치지 않고 실제로 가장 강력한 알려진 공격들에 대해 안전하도록 보장합니다. 그들의 발견은 만약 마이크로크립트가 실현되기를 원한다면, 지금까지의 분야를 지배해 온 익숙한 패턴에서 벗어나 양자 연산에 대한 완전히 새로운 사고방식이 필요할 것임을 시사합니다. 이 연구는 체계적인 분석의 힘을 보여주는 증거이며, 무엇이 작동하지 않는지를 증명하는 것이 무엇이 작동하는지를 발견하는 것만큼이나 중요하다는 것을 보여줍니다.

기술 요약: 마이크로크립트(Microcrypt)를 구축하지 않는 방법

1. 문제 정의

양자 암호학 분야는 최근 "마이크로크립트(Microcrypt)"에 초점을 맞추어 왔습니다. 마이크로크립트란 고전적인 일방향 함수(One-Way Function, OWF)보다 더 약한 가설에 기반하여 암호학적 프리미티브(예: 의사 난수 상태(PRS), 의사 난수 유니터리(PRU), 일방향 상태 생성기(OWSG))를 구축하는 것을 의미합니다. 구체적으로, 연구자들은 NP 오라클을 갖춘 공격자에게도 안전하게 유지되는 프리미티브를 찾고자 합니다.

여러 후보 구조(예: 해밀토니안 위상 상태, IQP 군 작용, 다양한 클리포드-모노미얼-클리포드 아키텍처)가 제안되었으나, NP 보조 공격자에 대한 체계적인 암호 해독 분석은 부족한 실정이었습니다. 핵심적인 과제는 이러한 구조들이 의도치 않게 고전적 일방향 함수의 존재를 함의하게 되어 마이크로크립트에 부적합해지는지 여부를 결정하는 것입니다. 본 논문은 다음과 같은 질문을 다룹니다: 어떤 자연스러운 PRS 및 PRU 구축 레시피가 일방향 함수나 NP-난해성을 함의하기 때문에 실패하는가?

2. 방법론

저자들은 후보 구조들을 분석하고 깨뜨리기 위해 두 가지 주요 기술적 프레임워크를 개발했습니다.

A. 계산 가능한 상태에 대한 NP 보조 섀도 토모그래피(Shadow Tomography)

저자들은 NP 오라클을 사용하여 양자 상태를 학습하는 효율적인 알고리즘을 도입합니다.

계산 가능한 상태(Computable States): 키 $k$ 가 주어졌을 때, 임의의 계산 기저 항의 진폭과 위상을 고전적으로 효율적으로 계산할 수 있다면 상태 집합 $\{|\psi_k\rangle\}$ 를 계산 가능하다고 정의합니다.
공격 전략: 알고리즘은 두 단계로 진행됩니다.
1. 기저 분포 매칭(Basis Distribution Matching): 미지의 상태를 계산 기저에서 측정하여 고전적 트랜스크립트를 얻습니다. NP 오라클을 사용하여, 관찰된 트랜스크립트의 가능도(likelihood)를 최대화하는 예측 측정 분포를 가진 후보 키 $k_0$ 를 탐색합니다. 이를 통해 미지의 상태의 크기 분포를 근사하는 키를 복구합니다.
2. 간섭을 통한 위상 추출(Phase Extraction via Interference): 기저 측정에서 소실되는 위상 정보를 복구하기 위해, 저자들은 "참조 상태(reference state)" $|\psi_{k_0}^+\rangle$ (후보 키의 양의 진폭 상태)를 구성합니다. 그 후, 미지의 상태와 이 참조 상태 사이의 제어-SWAP 간섭 실험을 수행합니다. 이를 통해 상대적 위상 정보를 추출할 수 있습니다.
3. 최종 키 복구: 간섭 분포로부터 샘플을 수집하고, 두 번째 NP 쿼리를 사용하여 이러한 위상 민감 샘플들의 가능도를 최대화하는 키 $h$ 를 찾습니다.
결과: 계산 가능한 상태를 가진 모든 OWSG 패밀리에 대해, NP 오라클을 가진 공격자는 다항 시간 내에 생성기를 역산(키를 찾아냄)할 수 있습니다.

B. 유니터리 학습에 대한 NP 보조 공격 (CMC 공격)

저자들은 $U_k = C_{2,k} M_k C_{1,k}$ 형태의 유니터리 패밀리( $C$ 는 클리포드 유니터리, $M$ 은 모노미얼 레이어(치환과 위상))에 대한 특정 공격을 개발했습니다.

전략: 이 공격은 벨 상태 측정을 활용합니다. 벨 상태 $|\beta_{a,c}\rangle$ 를 준비하고, 두 레지스터에 미지의 유니터리 $U$ 를 적용한 뒤 벨 기저로 측정함으로써, 공격자는 "변위(displacement)" 제약 조건을 얻습니다.
클리포드 교정(Clifford Correction): 외곽 레이어들이 클리포드이므로, 공격자는 이 레이어들이 벨 기저의 라벨을 어떻게 치환하는지 고전적으로 계산할 수 있습니다. 이 클리포드 레이어들을 고전적으로 "되돌림(undoing)"으로써, 문제는 관찰된 변위가 중간의 모노미얼 레이어 $M_k$ 와 일치하는지 확인하는 문제로 축소됩니다.
NP 쿼리: 공격자는 NP 오라클에 다음과 같이 질문합니다: "관찰된 모든 변위 제약 조건을 설명할 수 있는 단일 키 $h$ 와 증거 문자열 세트가 존재하는가?"
결과: 어떤 CMC 구조에 대해서도, NP 오라클은 다항 개의 쿼리를 사용하여 해당 유니터리를 하르 무작위(Haar-random) 유니터리와 높은 확률로 구별할 수 있습니다. 또한, 탐색-결정 환원(search-to-decision reduction)을 통해 공격자는 키를 학습할 수 있습니다.

3. 주요 기여 및 결과

A. 계산 가능한 OWSG의 역산

본 논문은 모든 계산 가능한 상태를 가진 OWSG 패밀리는 BQPNP(NP 오라클에 접근 가능한 양자 다항 시간) 내에서 역산 가능함을 증명합니다.

일방향 함수에 대한 함의: 만약 OWSG가 계산 가능할 뿐만 아니라 *샘플링 가능(samplable)*하다면(즉, 주어진 키에 대해 상태의 측정 분포로부터 고전적으로 효율적으로 샘플링할 수 있다면), 그러한 OWSG의 존재는 고전적 일방향 함수의 존재를 함의합니다.
구체적인 파괴 사례: 이 결과는 다음의 보안성을 무너뜨립니다:
- 해밀토니안 위상 상태(HPS): 기존에는 OWF보다 약한 가설에 의존한다고 추측되었으나, 저자들은 이것이 OWF를 함의함을 보여줍니다.
- IQP 군-작용 상태: Morimae와 Xagawa가 제안한 어려움 가설이 OWF를 함의함을 보여줍니다.

B. 의사 난수 유니터리(PRU)의 파괴

본 논문은 많은 저명한 PRU 아키텍처가 NP 보조 공격자에 취약함을 입증합니다:

PFC 및 C2PFC1: 클리포드 사이에 치환/위상 레이어가 샌드위치된 구조(예: $C_2 P F C_1$ )는 하르 무작위와 구별될 수 있으며 학습될 수 있습니다.
LRFC 및 블록형 변형: 클리포드 엔드포인트를 가진 다양한 Luby-Rackoff 함수 구조들이 파괴됩니다.
일반화: 이 공격은 "중간" 레이어가 모노미얼이고 엔드포인트가 효율적으로 기술 가능한 클리포드인 모든 유니터리 패밀리에 적용됩니다.

C. 생존 후보 식별

저자들은 현재의 기술로 공격을 제공하지 않는 구조들을 명시적으로 나열하며, 이들이 마이크로크립트의 타당한(비록 증명되지는 않았지만) 경로로 남아 있음을 언급합니다. 여기에는 다음이 포함됩니다:

많은 혼합 라운드를 가진 전체 PRSS(의사 난수 상태 스크램블러) 워크.
긴 Kac 워크.
모노미얼 레이어 사이에 겹치는 블록이나 중간 클리포드가 있는 구조(예: 세 번째 블록형 LRFC 형태).
숨겨진 기저(hidden-basis) 해밀토니안 역학.

4. 의의 및 주장

저자들은 이 연구를 마이크로크립트 분야의 "가드레일(guardrails)"을 설정하는 작업으로 규정합니다. 주요 주장은 다음과 같습니다:

체계적인 암호 해독: 이들은 단순한 임시방편적 공격을 넘어, 후보 양자 암호 구조를 평가하기 위한 일반적인 방법론(NP 보조 섀도 토모그래피 및 CMC 분석)을 제공합니다.
불가능성 결과(No-Go Results): "자연스러운" 구조들, 특히 계산 가능한 진폭이나 클리포드-모노미얼-클리포드 아키텍처에 의존하는 구조들은 의도치 않게 고전적 일방형 함수를 함의하거나 NP 오라클에 의해 파괴되므로, 마이크로크립트를 실현할 수 없음을 입증합니다.
향후 연구 방향 제시: 어떤 아키텍처가 실패하는지를 식별함으로써, 이 논문은 실행 가능한 마이크로크립트 프리미티브에 대한 탐색 범위를 좁혀줍니다. 이는 향후 구조가 아마도 NP 복잡도 클래스 밖에 있는 가설에 의존해야 하며, 저자들이 취약하다고 밝힌 특정 구조적 패턴(계산 가능한 진폭, 단순한 클리포드-모노미얼-클리포드 형태)을 피해야 함을 시사합니다.

결론적으로, 마이크로크립트의 지형은 여전히 열려 있으나, 계산 가능하고 샘플링 가능한 상태 구조 및 표준적인 CMC 유니터리 아키텍처와 같은 "따기 쉬운 열매(low-hanging fruit)"들은 일방향 함수 없이 마이크로크립트를 구현할 수 없는 것으로 판명되었습니다.