A Post-Quantum Interactive Hashing Theorem

기술 요약: 포스트 퀀텀 대화형 해싱 정리

문제 정의
Ostrovsky, Venkatesan, 그리고 Yung [OVY93]에 의해 처음 도입된 대화형 해싱(Interactive hashing)은 두 당사자가 한 당사자의 개인 입력(private input)을 포함하는 작은 문자열 집합을 선택할 수 있게 하되, 그 당사자가 다른 출력들을 제어하는 능력을 제한하는 근본적인 암호학적 프리미티브이다. 이의 다중 출력 일반화(multi-output generalization)는 Nguyen, Ong, 그리고 Vadhan [NOV06]에 의해 제안되었으며, $\mathsf{NP}$에 대한 통계적 영지식 증명(statistical zero-knowledge arguments) 및 임의의 일방향 함수로부터의 통계적으로 숨겨진 약속(statistically hiding commitments)을 위한 핵심 구성 요소 역할을 한다.

이 프로토콜들의 고전적 보안은 잘 확립되어 있으나, 양자 공격자에 대한 보안은 미해결 과제로 남아 있었다. Morimae와 Yamakawa [MY23]는 원격 상태 준비(remote state preparation)를 위해 기초가 되는 NOVY 프로토콜의 결맞는 실행(coherent execution)을 활용하였으나, 이 구성의 양자 공격자에 대한 보안 문제는 명시적으로 해결하지 않은 채 남겨두었다. 또한, 최근의 병렬 연구들(예: Dupuis 등 [DLM+26], Chen 등 [CWX26])의 포스트 퀀텀 분석은 비트 약속(bit-commitment) 스킴이나 효율적으로 검증 가능한 관계(efficiently verifiable relations)에 주로 집중하였다. 본 논문이 다루는 구체적인 과제는 임의의 관계(arbitrary relations)를 가진 다중 출력 대화형 해싱 프로토콜에 대한 포스트 퀀텀 보안 증명을 제공하는 것이며, 이는 일방향 함수에 기반한 더 넓은 구성들을 포스트 퀀텀 환경으로 확장하기 위해 필수적이다.

방법론 및 기술적 접근
저자들은 다중 출력 대화형 해싱 프로토콜의 "이중 개방 바인딩(two-opening binding)" 특성에 대한 포스트 퀀텀 보안 증명을 제공한다. 증명의 핵심은 두 개의 서로 다른 유효한 개방(openings)을 생성할 확률이 무시할 수 없는 수준인 악의적인 양자 송신자로부터 증거(witness)를 추출하기 위해 설계된 새로운 양자 리와인딩(quantum rewinding) 기법이다. 이 방법론은 네 가지 핵심 기술적 요소에 의존한다:

1. 코인 정규화 양자 리와인딩 (Coin-Regularized Quantum Rewinding):
   단일 벡터 변환(QSVT)에 기반한 표준 양자 리와인딩 프레임워크(예: Lombardi, Ma, and Spooner [LMS22])는 송신자의 호환성 연산자(compatibility operator)가 임의로 작거나 0인 고윳값을 가질 때 스펙트럼 장애(spectral obstruction)에 직면한다. 이를 극복하기 위해, 저자들은 중첩 상태 $\sqrt{1-\eta}|0\rangle + \sqrt{\eta}|1\rangle$로 준비된 보조 "코인(coin)" 레지스터를 도입한다. 이 코인 정규화는 결과적인 호환성 연산자가 하한이 있는 특이값(최소 $\sqrt{\eta}$)을 갖도록 보장하여, 송신자의 전략과 관계없이 폴라 아이소메트리(polar isometry)가 잘 정의되고 QSVT를 통해 효율적으로 구현될 수 있게 한다.

2. 정규화 오류에서 기록으로 (From Normalization Errors to Recording):
   리와인딩 과정은 송신자의 잔여 양자 상태를 변화시키고 실제 실행과 비교하여 정규화 오류를 발생시킨다. 저자들은 이러한 오류들을 개별적으로 바운드하는 것(이는 불충분하다) 대신, 연산자 푸리에 논증(operator Fourier argument)을 사용하여 이들의 집합적 거동을 분석한다. 저자들은 모든 가능한 타겟에 대한 제곱 편향 연산자의 합이 항등원과 같음을 보여주는 기술적 보조정리(Lemma 4.4)를 증명한다. 이를 통해 정규화 오류 연산자들을 효율적인 **기록 맵(recording map, $\mathsf{Record}$)**의 성공적인 브랜치 연산자로 해석할 수 있다. 이 맵은 오류 크기에 비례하는 확률로 타겟 라벨 $y$를 결맞게 "기록"할 수 있다.

3. 타겟 스위칭 및 오류 분해 (Target Switching and Error Decomposition):
   추출기(extractor)는 하이브리드 전략을 사용한다. 추출기는 "정상 전략"(고정된 외부 챌린지 $Y$를 향한 리와인딩)과 "타겟 스위칭 전략" 사이에서 무작위로 선택한다. 타겟 스위칭 전략에서 추출기는 접두(prefix) 라운드 동안 $Y$를 향해 리와인딩하고, 기록 맵을 적용하여 기록된 라벨 $Z$를 얻은 다음, 나머지 접두 라운드 동안 $Z$를 향해 리와인딩한다.
   저자들은 스케일링된 실제 실행 연산자를 다음의 합으로 표현하는 정확한 오류 분해(error decomposition) 항등식(Equation 2)을 확립한다:

   • 정상 항 (normal term): 정상 전략에 대응함.
   • 단일 오류 항 (single-error terms): 타겟 스위칭 전략에 대응함.
   • 이중 오류 나머지 (double-error remainder): 두 번의 기록 이벤트가 포함됨.

4. 나머지 바운드 (Bounding the Remainder):
   이중 오류 나머지는 정직한 테일(honest tail) 단계 이전에 두 개의 서로 다른 라벨이 기록되는 실험에 해당한다. 저자들은 만약 두 개의 서로 다른 문자열이 정직한 테일 이전에 고정된다면, $\beta$ 라운드 후에 이들이 트랜스크립트(transcript)와 동시에 호환될 확률이 지수적으로 작음($2^{-\beta}$)을 증로한다. 적절한 길이의 정직한 테일 $\beta$를 선택함으로써, 이중 오류 나머지의 노름(norm)을 전체 확률의 무시할 수 있는 분율로 억제하여, 정상 항과 단일 오류 항이 추출 성공 확률을 집합적으로 운반하도록 보장한다.

주요 기여 및 결과
본 논문은 다음과 같은 주요 정리를 확립한다:

• 정리 4.1: [$\text{NOV06}$]의 다중 출력 대화형 해싱 프로토콜은 **임의의 관계에 대해 포스트 퀀텀 계산적 이중 개방 바인딩(post-quantum computational two-opening binding)**을 만족한다. 구체적으로, 양자 송신자가 확률 $\varepsilon$으로 두 개의 서로 다른 유효한 개방을 생성할 수 있다면, 무작위 챌린지 $Y$가 주어졌을 때 $\Omega(\varepsilon^2 / (2^k q^2))$의 확률로 $Y$에 대한 유효한 증거를 출력하는 효율적인 추출기가 존재한다.

이 결과는 두 가지 즉각적인 따름정리를 도출한다:

1. 양자 계산의 고전적 검증 (CVQC): [$\text{MY23}$]의 결맞는 대화형 해싱 구성과 [$\text{BK25}$]의 프레임워크를 결합함으로써, 저자들은 포스트 퀀텀 보안 전영역 트랩도어 치환(full-domain trapdoor permutations)의 존재를 가정할 때 모든 $\mathsf{BQP}$ 언어에 대한 CVQC 프로토콜을 유도한다. 이는 Morimae와 Yamakawa가 제기했던 그들의 구성에 대한 양자 공격자 대상의 보안 문제를 해결한다.
2. 포스트 퀀텀 완전 은닉 약속 (Post-Quantum Perfect Hiding Commitments): 이 결과는 원래의 NOVY 약속 구성을 포스트 퀀텀 환경에서 복구하여, 포스트 퀀텀 일방향 치환에 기반한 포스트 퀀텀 보안 완전 은닉 약속 스킴의 존재를 증명한다.

의의 및 주장
저자들은 자신들의 작업이 임의의 관계에 대해 포스트 퀀텀 환경으로 대화형 해싱의 보안을 확장했다는 점에서 중요하다고 주장하며, 이는 [$\text{NOV06}$] 및 [$\text{HR07}$]에서 발견된 일반적인 일방향 함수에 기반한 구성들의 보안 증명에 필요한 요구사항이다. 동시대의 연구들이 비트 약속 케이스나 효율적으로 검증 가능한 관계를 다룬 반면, 본 논문은 더 광범위한 암호학적 응용을 위해 필요한 더 일반적인 경우를 다룬다.

본 논문은 초기 접근 방식의 결합, 검토, 파라미터 선택을 위해 AI(ChatGPT-5.6 및 ChatGPT-6)의 도움을 받아 논문을 개발했음을 명시적으로 밝히고 있다. 그러나 저자들은 모든 수학적 주장이 자신들에 의해 독립적으로 검증되었음을 강조하며, 내용에 대한 모든 책임을 진다고 밝혔다. 본 작업은 IACR 정책에 따라 "상당한 AI 기여(Substantial AI contribution)"가 있다고 선언되었다.

저자들은 [$\text{NOV06}$] 및 [$\text{HR07}$]의 특정 구성(이 정리에 의존함)에 대한 완전한 포스트 퀀텀 분석은 향후 과제로 남겨두었으나, 이 정리가 그러한 확장에 필수적일 것으로 기대한다고 겸손하게 언급하였다.