이 논문은 양자 암호학의 공개 검증 가능한 NIZK(비대화형 영지식증명)를 QMA에 대해 구성하는 문제를 다룬다. 고전적으로는 Fiat-Shamir 변환을 통해 NP용 HVZK Σ-프로토콜을 NIZK로 컴파일할 수 있지만, 프루버의 첫 메시지가 양자 상태인 QMA용 Ξ-프로토콜(Broadbent-Grilo)에는 이 변환이 양립하지 않는 것으로 알려져 있었다. 저자들은 양자 프로토콜을 위한 일반적인 'Fiat-Shamir류' 컴파일러가 QROM에서 작은 완전성·건전성 오차로 존재한다면 QMA = BQP가 성립함을 증명해, 이것이 사실상 불가능하다는 형식적 증거를 제시한다. 양자 복잡도 이론의 핵심 난제인 QMA와 BQP의 분리 여부와 직결되는 결과로, 양자 NIZK 설계에 근본적 장벽이 있음을 시사한다.
- •QMA용 공개 검증 NIZK를 위한 범용 Fiat-Shamir류 컴파일러가 QROM에서 존재하면 QMA=BQP가 성립함을 증명
- •QMA≠BQP로 널리 추정되는 상황에서 해당 컴파일러의 존재 가능성에 강한 반증을 제공
- •Broadbent-Grilo의 양자 Σ-프로토콜(Ξ-프로토콜)과 Fiat-Shamir 변환의 양립 불가능성을 형식적으로 규명
- •양자 영지식증명을 비대화형으로 만드는 설계에 근본적 장벽이 있음을 시사
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
On Removing Interaction from Quantum Proofs
- 1.QMA에 대한 공개검증 가능 NIZK 구성이라는 양자암호 난제를 다룸
- 2.양자 버전 Σ-프로토콜인 Ξ-프로토콜에 Fiat-Shamir류 변환 적용 가능성을 검토
- 3.QROM에서 범용 Fiat-Shamir류 컴파일러가 존재하면 QMA=BQP가 성립함을 증명
- 4.양자 메시지에 Fiat-Shamir 변환을 그대로 적용하기 어렵다는 강한 반증 제시
왜 중요한가?
QMA=BQP는 복잡도 이론에서 사실상 불가능에 가깝다고 여겨지므로, 현재 알려진 방식으로는 양자 NIZK를 Fiat-Shamir식으로 만들 수 없음을 사실상 보여준다.
본문 미리보기
An important open question in quantum cryptography is the construction of publicly-verifiable NIZKs for QMA. Classically, one can construct NIZKs for NP in the random oracle model (and sometimes in the standard model) by compiling an honest-verifier ZK (HVZK) $\Sigma$-protocol for NP using the Fiat–Shamir transformation. Broadbent and Grilo introduced a quantum analog of a $\Sigma$-protocol (which they call a $\Xi$-protocol) in which the prover's first message is quantum, and show that HVZK $\Xi
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
