⚛️ quantum physics

On Removing Interaction from Quantum Proofs

이 논문은 일반적인 피아트-샤미르(Fiat-Shamir) 유사 컴파일러가 양자 대화형 증명(구체적으로 QMA를 위한 $\Xi$ -프로토콜)을 양자 무작위 오라클 모델에서의 비대화형 영지식 인자(non-interactive zero-knowledge arguments)로 변환할 수 없다는 공식적인 증거를 제공하며, 만약 그러한 컴파일러가 존재한다면 이는 QMA가 BQP로 붕괴됨을 의미한다.

원저자: Nicholas Spooner, Max Tromanhauser

게시일 2026-10-01

📖 3 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Nicholas Spooner, Max Tromanhauser

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

암호학의 세계에는 비대화형(non-interactive)이면서도 공개적으로 검증 가능한(publicly verifiable) 증명 체계를 만들고자 하는 오래된 열망이 존재합니다. 컴퓨터가 어려운 퍼즐을 풀었다는 사실을 낯선 이에게 설득해야 하지만, 단 하나의 메시지만을 보낼 수 있는 시나리오를 상상해 보십시오. 이 낯선 이, 즉 검증자(verifier)는 별도의 비밀 키나 사전 설정 없이도 답을 확인할 수 있어야 하며, 그 증명은 해결책에 대한 어떠한 정보도 드러내서는 안 됩니다. 고전적인 문제들의 경우, 수학자들은 증명자가 검증자의 질문을 받기 전에 자신의 답을 확정하도록 만드는 디지털 자물쇠와 같은 기법을 사용하여, 대화형 과정을 이러한 단발성 증명으로 전환하는 방법을 찾아냈습니다. 그러나 문제가 양자 역학(정보가 취약하고 중첩된 상태로 존재하는 영역)과 관련될 때, 이 표준적인 방법은 벽에 부딪힙니다. 핵심적인 어려움은 양자 정보가 복제되거나 측정될 때 잠재적으로 파괴될 수 있다는 점이며, 이로 인해 상호작용을 제거하기 위해 사용되는 통상적인 기술들을 적용하는 것이 불가능해 보인다는 것입니다.

이러한 불확실성은 양자 보안에 대한 우리의 이해에 큰 공백을 남겼습니다. 연구자들은 양자 증명자(prover)가 해결책을 검증자에게 설득할 수 있는 대화형 프로토콜을 개발해 왔지만, 이 프로토콜들은 앞뒤로 주고받는 통신을 필요로 합니다. 큰 의문은, 고전적인 방식처럼 이러한 상호작용을 제거하여 단 한 번의 메시지로 이루어진 증명을 만들어낼 수 있는 일반적인 방법이 존재하는가 하는 점이었습니다. 만약 그러한 방법이 존재한다면, 이는 양자 계산의 검증 방식을 혁신적으로 바꿀 것입니다. 만약 존재하지 않는다면, 이는 양자 정보를 압축하고 검증하는 데 있어 근본적인 한계가 있음을 시사할 것입니다.

코넬 대학교의 연구진은 이제 이러한 일반적인 방법이 존재하지 않는다는 강력한 증거를 제시했습니다. 그들은 단순히 추측하거나 시뮬레이션을 통해 실패를 보여준 것이 아니라, 만약 상호작용을 제거하기 위한 컴파일러(compiler)가 가능하다면 두 가지 주요 계산 문제 클래스 사이의 구분을 무너뜨리는 논리적 모순이 발생한다는 것을 보여주는 공식적인 증명을 구축했습니다. 구체적으로, 그들은 "직선형(straight-line)" 컴파일러—즉, 단 한 번의 통신 과정만으로 대화형 양자 프로토콜을 비대화형 프로토콜로 변환하는 것—가 높은 신뢰도로 작동할 수 있다면, 양자 컴퓨터에게 어렵다고 알려진 문제 클래스가 갑자기 쉬운 문제로 변하게 된다는 것을 입증했습니다. 이는 양자 컴퓨터가 현재 믿어지는 것보다 훨씬 더 강력하다는 것을 의미하며, 대부분의 전문가들이 매우 희박하다고 여기는 시나리오입니다.

이 결론에 도달하기 위해 저자들은 정교한 반례를 설계했습니다. 그들은 증명자의 첫 번째 메시지가 특수한 양자 자물쇠로 암호화된 양자 증명 프로토콜 군을 상상했습니다. 일반적인 상호작용에서는 검증자가 이 메시지를 해독하여 확인합니다. 그러나 연구진은 이 대화형 과정을 단일 메시지로 변환하려는 모든 시도가 암호화된 양자 상태를 측정하도록 강제한다는 것을 보여주었습니다. 양자 상태를 측정하면 상태가 교란되기 때문에, 컴파일러는 증명의 유효성을 깨뜨리거나 혹은 부정행위자가 증명을 위조할 수 있게 만듭니다. 연구진은 만약 컴파일러가 이러한 교란을 우회하면서도 여전히 유효한 단일 메시지 증명을 생성할 수 있다면, 그것은 본질적으로 컴파일러가 감지되지 않고 비밀 해결책을 엿볼 수 있는 방법을 찾아낸 것과 같음을 증명했습니다.

그들 논증의 핵심은 양자 암호화에서의 "소급적 보안성(retrospective security)"이라는 속성에 기반합니다. 이 개념은 공격자가 암호화의 최종 결과물을 보더라도, 그 메시지가 실제 메시지였는지 아니면 사후에 만들어진 시뮬레이션된 자리 표시자(placeholder)였는지 구분할 수 없음을 보장합니다. 연구진은 성공적인 비대화형 증명에서 컴파일러가 챌린지(challenge)가 발행되기 전에 메시지를 이미 알고 있었던 것처럼 행동해야 함을 보여주었으나, 양자 역학의 법칙은 이를 파괴 없이 수행하는 것을 허용하지 않습니다. 이러한 개념들을 엮어냄으로써, 그들은 논리적 함정을 만들었습니다. 즉, 만약 컴파일러가 작동한다면, 그것은 실제 메시지와 시뮬레이션된 메시지를 구분할 수 있어야 하며, 이는 암호화의 보안을 깨뜨리는 결과를 초래한다는 것입니다. 이 보안의 파괴는 다시 컴파일러가 어려운 문제를 효율적으로 해결할 수 있게 합니다.

이 연구가 모든 가능한 비대화형 증명 생성 방식을 배제하는 것은 아닙니다. 연구는 특히 오늘날 사용되는 고전적 방법들의 가장 직접적인 유사체인 "직선형" 컴파일러를 겨냥하고 있습니다. 이는 더 복잡한 다단계 전략이 작동할 가능성이나, 모든 문제가 아닌 특정 하위 집합의 문제들에 대해서는 증명이 가능할 가능성을 열어둡니다. 그러나 고전 컴퓨터에서 매우 잘 작동했던 광범적이고 일반적인 접근 방식에 대해서는, 이 논문이 명확한 중단을 시사합니다. 이 연구 결과는 양자 정보의 독특한 성질—그 취약성과 복제의 불가능성—이 고전적 데이터에서와 같이 상호작용을 제거하는 데 있어 근본적인 장벽을 만든다는 점을 시사합니다. 이 결과는 양자 암호학의 지형을 명확히 하며, 공개적으로 검증 가능한 양자 증명으로 가는 길이 단순히 기존의 것을 적용하는 것이 아니라 완전히 새로운 아이디어를 필요로 할 것임을 말해줍니다.

기술 요약: 양자 증명에서 상호작용 제거에 관하여

1. 문제 정의

QMA(Quantum Merlin-Arthur) 복잡도 클래스에 대한 공개 검증 가능한 비대화형 영지식(NIZK) 증명을 구축하는 것은 양자 암호학의 중요한 미해결 과제로 남아 있다. 고전적으로 NP에 대한 NIZK는 대개 인터랙티브한 공적 코인(public-coin) 프로토콜(특히 $\Sigma$ -프로토콜)에 피아트-샤미르(Fiat–Shamir, FS) 변환을 적용하여 구축된다. 이 변환은 인터랙티브 프로토콜을 비대화형 프로토콜로 컴파일하며, 이 과정에서 검증자의 무작위 챌린지를 암호학적 해시 함수(Random Oracle으로 모델링됨)의 출력값으로 대체한다.

Broadbent와 Grilo가 프로버의 첫 번째 메시지가 양자인 $\Sigma$ -프로토콜의 양자 아날로그( $\Xi$ -프로토콜)를 도입했지만, 이를 FS 변환에 어떻게 적용할지는 불분명하다. 핵심적인 어려움은 FS 변환과 양자 메시지 사이의 부적합성에 있다:

완전성(Completeness): 양자 메시지에 대해 코히어런트하게(coherently) 해시를 계산하고 출력을 측정하는 행위는 양자 상태를 교란시켜, 검증자가 유효한 증명을 거부하게 만들 수 있다.
건전성(Soundness): 만약 검증자가 특정 기저(예: Z-기저)에서 해시를 확인한다면, 공격자는 해시 체크는 유지하면서도 근본적인 양자 상태를 변경하는 연산을 수행하여 건전성을 깨뜨릴 수 있다.

본 연구는 이러한 어려움이 양자 프로토콜에서 상호작용을 제거하기 위한 모든 일반적인(generic) 기법에 대한 근본적인 장벽인지 조사한다. 즉, 본 논문은 다음과 같은 질문을 던진다: 양자 통신을 포함하는 프로토콜에서 상호작용을 제거하기 위한 일반적인 방법이 존재하는가?

2. 방법론 및 형식적 프레임워크

2.1 양자 비대화형 컴파일러 (QNIC)

이 질문을 일반적인 관점에서 다루기 위해, 저자들은 **양자 비대화형 컴파일러(QNIC)**를 정의한다. QNIC는 인터랙티브한 $\Xi$ -프로토콜(양자 통신을 포함하는)을 공개 검증 가능한 비대화형 양자 아규먼트(quantum argument)로 변환하는 블랙박스 컴파일러이다.

구조: QNIC는 두 개의 알고리즘, $T_P$ (프로버 시뮬레이터)와 $T_V$ (검증자 시뮬레이터)로 구성된다.
직선형 제한(Straightline Restriction): 저자들은 프로버 및 검증자 오라클에 대해 단 한 번의 블랙박스 쿼리만을 수행하는 직선형 QNIC에 초점을 맞춘다. 이는 증명을 생성하기 위해 단일 패스를 요구하는 클래식 피아트-샤미르 변환과 유사한 전략을 포착한다.
보편성(Universality): 컴파일러는 모든 보안 $\Xi$ -프로토콜에 대해 작동하는 "보편적"인 것으로 가정된다.

2.2 반례 구축 (Counterexample Construction)

저자들은 이러한 컴파일러의 존재 여부를 테스트하기 위해 일련의 반례 $\Xi$ -프로토콜을 구축한다. 이 구축은 **양자 암호문 인증(Quantum Ciphertext Authentication, QCA)**에 기반한다:

첫 번째 메시지의 암호화: $\Xi$ -프로토콜에서의 프로버의 초기 메시지는 비밀 키 $k$ (당사자 간 공유되지 않는, 공적 프로토콜 기술의 일부)에 의해 암호화된다.
검증: 검증자는 $k$ 를 사용하여 첫 번째 메시지를 복호화하려고 시도한다. 복호화에 실패하면 증명은 거부되며, 성공하면 트랜스크립트(transcript)가 검증된다.
보안 속성: 암호화 스킴은 QCA-보안을 갖도록 선택된다. 이는 키 $k$ 없이 메시지를 수정하거나 위조하려는 어떤 공격자(QNIC 알고리즘 $T_P, T_V$ 포함)도 탐지될 것임을 보장한다. 결정적으로, QCA 보안은 공격자가 "실제" 암호문과 메시지가 복호화 시점까지 유예된 "시뮬레이션된" 암호문을 구별할 수 없음을 의미한다.

2.3 공격 전략

이 불가능성 증명의 핵심은 가상의 QNIC를 사용하여 QMA-완전 언어 $L$ 에 대한 결정 알고리즘을 구축하는 것이다. 공격은 다음과 같이 진행된다:

유예(Deferral): QCA의 특성을 이용하여, 공격은 $\Xi$ -프로토콜의 첫 번째 메시지 선택을 "유예"한다. 즉, 즉시 $x$ 에 기반한 메시지를 생성하는 대신, 최대 얽힘 상태( $\Phi^+$ )의 절반을 암호화하는 암호문을 준비한다.
시뮬레이션: QNIC가 챌린지 $c$ 를 생성한 후, 공격은 해당 챌린지 $c$ 에 대한 유효한 응답을 생성하기 위해 기저 $\Xi$ -프로토콜의 **영지식 시뮬레이터(Zero-Knowledge Simulator, Sim)**를 사용한다.
재암호화: 공격은 유예된 암호문을 시뮬레이션된 메시지를 암호화한 것으로 교체한다.
역계산(Uncomputation): 공격은 검증 단계를 역계산하여 위조된 증명 $\pi'$ 를 생성한다.

만약 QNIC가 완전하고 건전하다면, 이 위조된 증명 $\pi'$ 는 $x \in L$ 인 경우 높은 확률로 수락되고, $x \notin L$ 인 경우 높은 확률로 거부될 것이다. 이는 결과적으로 QMA-완전 언어를 결정하는 효율적인 양자 알고리즘(BQP)을 생성하게 된다.

2.4 기술적 혁신

이 공격을 엄밀하게 만들기 위해 저자들은 두 가지 핵심 기술적 개념을 도입한다:

회고적 보안(Retrospective Security): QCA 보안의 강화된 형태이다. 이는 성공적인 복호화 이후에 암호화 키 $k$ 와 무작위성 $r$ 이 드러나더라도, 공격자가 실제 채널과 시뮬레이션된 채널을 구별할 수 없음을 보장한다. 이는 공격자가 위조를 검증하기 위해 키를 드러내야 하기 때문에 필수적이다.
무작위성 보존(Randomness Preservation): QCA-보안 스킴에서 "실제" 채널에 사용된 암호화 무작위성이 재암호화된 경우에도 "유예된" 채널의 무작위성과 구별 불가능함을 증명하는 르마(lemma)이다. 이는 평문(plaintext)을 출력하는 표준 QCA 정의와 저자들의 설정(암호문 출력) 사이의 간극을 메운다.

3. 주요 결과

주요 결과는 양자 커밋먼트(quantum commitments)의 존재를 가정할 때, 직선형 QNIC에 대한 불가능성 정리이다.

정리 1 (비형식적): $O$ 를 유니터리 오라클에 대한 효율적으로 시뮬레이션 가능한 분포라고 하자. 다음을 가정한다:

$O$ 에 대해 양자 커밋먼트가 존재한다.
$O$ 에 대해 $(1-\epsilon)$ -완전하고, $\delta$ -건전한 직선형 QNIC가 존재하며, 여기서 $\epsilon(n) + 2\delta(n) \leq 3/5$ 이다.

그러면, QMA = BQP이다.

특정 모델에서의 함의:

Plain Model / CRS Model: 양자 커밋먼트와 작은 오차를 가진 직선형 QNIC가 존재한다면, QMA = BQP이다.
QROM / Quantum Haar Random Oracle Model (QHROM): 이 모델들에서 양자 커밋먼트는 무조건적으로 존재하므로, 작은 오차를 가진 직선형 QNIC의 존재 자체가 QMA = BQP를 함의한다.

오차 범위 $\epsilon + 2\delta \leq 3/5$ 는 증명에 사용된 특정 연속성 경계(Jordan-Hahn 분해 및 Stinespring 확장에 관련됨)에서 기인한다. 저자들은 병렬 반복(parallel repetition)이 오차를 줄일 수는 있지만 "직선형" 속성을 파괴한다는 점을 언급하며, 따라서 이 정리는 비직선형 컴파일러에는 적용되지 않는다고 명시한다.

4. 의의 및 범위

논문의 주장

본 논문은 (피아트-샤피르 변환과 같은) "상호작용 제거" 방식의 제너릭 컴파일러를 양자 통신이 포함된 양자 프로토콜에 보안하게 적용하는 것이, 양자 복잡도 클래스 QMA와 BQP가 붕괴하지 않는 한 불가능하다는 형식적 근거를 제공한다.

부정적 답변: 양자 프로토콜에서 상호작용을 제너릭하게 제거할 수 있는지에 대한 질문에 대해 부분적인 부정적 답변을 제시한다.
장벽 식별: 해싱(측정 필요)의 파괴적 성질과 양자 코히어런스 보존(완전성 필요) 사이의 긴장이 직선형 컴파일러를 위한 근본적인 장벽임을 밝힌다.
상대화(Relativization): 이 결과는 Random Oracle Model(ROM) 및 Quantum Random Oracle Model(QROM)에서도 유효하며, 이는 피아트-샤피르가 Plain Model에서 일반적으로 안전하지 않다는 점을 고려한 것이다.

한계 및 향후 과제

저자들은 자신들의 불가능성 결과의 범위를 다음과 같이 제한적으로 설정한다:

직선형 제한: 이 결과는 프로버/검증자와 단일 직선형 패스로 상호작용하는 컴파일러에만 적용된다. (Fischlin 변환과 같이 여러 번의 상호작용을 요구하는 컴파일러는 제외된다.)
공개 vs. 지정 검증자: 이 불가능성은 공개 검증 가능한 프로토콜에 적용된다. 비밀 설정을 사용하는 지정 검증자(designated-verifier) 방식의 QMA용 NIZK는 여전히 가능하며 이미 존재함이 알려져 있다.
프로토콜의 하위 클래스: 이 결과는 모든 $\Xi$ -프로토콜에 작동하는 컴파일러를 배제한다. 즉, 특정 제약 조건을 만족하는 특정 하위 클래스의 프로토콜에 대해서는 별도의 컴파일러가 존재할 가능성을 열어둔다.
대안적 접근법: 본 논문은 (고전 암호학의 hidden bits 모델과 유사하게) 상호작용을 제거하는 방식이 아닌 다른 방식으로 QMA를 위한 비대화형 증명 시스템이 구축될 가능성을 인정한다.

요약하자면, 본 논문은 단일 패스 블랙박스 변환을 통해 인터랙티브 양자 증명을 비대화형으로 컴파일하는 표준 패러다임이, 양자 복잡도가 붕괴하지 않는 한 양자 암호학의 보안 요구사항과 근본적으로 양립할 수 없음을 입증한다.