기술 요약: 퀀텀 헤드에서의 MPC (중첩 보안 제로 지식)

문제 정의

본 논문은 악의적인 검증자가 중첩(superposition) 상태에서 챌린지를 발행하고 응답을 받을 수 있는 상황에서도 보안이 유지되는 제로 지식(Zero-Knowledge, ZK) 프로토콜 구축 문제를 다룹니다. 이러한 "중첩 보안(superposition security)"은 고전적 암호 장치와 상호작용하는 양자 공격자나, 더 큰 양자 프로토콜 내에 임베딩된 고전적 프리미티브가 존재하는 시나리오를 고려할 때 필수적인 강화 요소입니다.

Damgård 등[19]이 NP에 대해 이 개념을 개척했으나, 그들의 구성은 표준 암호 가정하에서는 존재가 알려지지 않은 **완전 은닉(perfectly hiding) 및 무조건적 결합(unconditionally binding) 이중 모드 약속(dual-mode commitments)**에 의존했습니다. 또한, 그들의 기법은 양자 증거(witness)를 드러내지 않고 양자 계산을 검증해야 하는 근본적인 어려움 때문에 QMA(NP의 양자 버전)로 자연스럽게 확장되지 못했습니다.

기존의 대안인 비대화형 제로 지식(NIZK) 증명은 표준 가정하에서 QMA에 대한 것이 알려져 있지 않거나, 양자 랜덤 오라클 또는 난해화(obfuscation)와 같은 휴리스틱 모델에 의존합니다. 또한, NIZK는 효율성을 위해 선호되는 3라운드 $\Sigma$-프로토콜보다 일반적으로 더 무겁습니다.

방법론

저자들은 **"양자 헤드에서의 MPC(MPC in the Quantum Head)"**라고 명명된, MPC-in-the-Head 패러다임[30]의 양자 설정에 대한 일반화를 제안합니다. 핵심 방법론은 두 가지 구별되지만 연관된 구성을 포함합니다.

1. NP를 위한 중첩 보안 ZK

저자들은 Damgård 등[19]의 프로토콜을 재검토하되, 완전 은닉 약속 대신 이중 모드 약속(한 모드에서는 통계적으로 은닉되고 계산적으로 결합되며, 다른 모드에서는 완벽하게 결합되고 계산적으로 은닉됨)을 사용합니다.

• 기법: 증명 전략은 하이브리드 논증을 활용합니다. 실제 세계에서 약속은 MPC 뷰(view)에 대한 것입니다. 하이브리드 단계에서 약속은 통계적 은닉 모드로 전환됩니다. 결정적으로, 저자들은 약속을 (정직한 뷰 대신) 0으로 하는 하이브리드를 도입하지만, 이는 계산적 결합 성질(무제한 시뮬레이터에 의해 깨질 수 있는)을 사용하여 여전히 정직한 뷰로 열 수 있습니다.
• 보안 논증: 약속이 0이 되면, 열린 뷰(공유값의 일부)와 열리지 않은 약속은 완전 보안 비밀 공유(perfectly secure secret sharing) 체계를 형성합니다. 저자들은 $2t$개 미만의 셰어(share)가 쿼리될 경우 완전 비밀 공유가 중첩 공격에 대해 안전하다는 [19]의 보조 정리를 활용합니다. 이를 통해 완전 은닉 약속 없이도 보안 증명을 진행할 수 있습니다.

2. QMA를 위한 양자 헤드에서의 MPC

이를 QMA로 확장하려면 양자 증거와 양자 검증 회로를 처리해야 합니다.

• 장애물: 고전적 MPC-in-the-Head에서 증명자는 당사자들의 "뷰"(트랜스크립트)를 공개합니다. 반면 다자간 양자 계산(MPQC)에서 당사자들은 양자 메시지를 교환하므로, 공개할 클래식 트랜스크립트가 존재하지 않으며 당사자는 최종 양자 상태만을 보유하게 됩니다.
• 해결책: 저자들은 전역 MPQC 프로토콜을 양자 회로로 모델링합니다(메시지 전달를 SWAP 게이트로 대체). 이후 이 회로에 Kitaev의 회로-해밀토니안 환원(Circuit-to-Hamiltonian reduction)[34]을 적용합니다.
  • "증거"는 해밀토니안의 **히스토리 상태(history state)**가 되며, 이는 MPQC가 수락될 때 낮은 에너지를 가집니다.
  • 증명자는 **양자 원타임 패드(QOTP)**를 사용하여 이 히스토리 상태를 큐비트 단위로 약속하고, QOTP 키를 이중 모드 약속을 사용하여 약속합니다.
  • 검증자는 특정 로컬 해밀토니안 항에 해당하는 큐비트를 열도록 증명자에게 챌린지를 던집니다.
• 검증: 검증자는 열린 큐비트를 측정하여 로컬 해밀토니안 항을 확인합니다. 만약 에너지가 낮다면, 히스토리 상태는 유효한 실행에 대응함을 의미합니다.
• 제로 지식: ZK 속성은 열린 큐비트의 부분 집합이 기초가 되는 MPQC의 일부 당사자를 제어하는 것 이상의 정보를 드러내지 않는다는 사실에 기반합니다. 저자들은 완전 $2t$-프라이빗 MPQC 프로토콜[17, 39]을 활용하여, 중첩 쿼리가 존재하는 상황에서도 비밀 공유된 증거에 대한 히스토리 상태가 더미 입력에 대한 히스토리 상태와 구별 불가능함을 보장합니다.

주요 기여

1. MPC-in-the-Head의 일반화: 본 논문은 양자 기능(MPQC)에 대한 MPC-in-the-Head 패러다임의 첫 번째 인스턴스화를 제시하며, 실질적으로 "양자 MPC-in-the-Head"를 생성합니다.
2. NP를 위한 중첩 보안 ZK: 저자들은 모든 포스트 양자 이중 모드 약속(예: LWE로부터 도출된)을 기반으로 중첩 공격에 안전한 NP용 3라운드 $\Sigma$-프로토콜을 구축합니다. 이는 완전 은닉 약속의 필요성을 제거함으로써 [19]를 개선합니다.
3. QMA를 위한 중첩 보안 ZK: 본 논문은 학습 오류(LWE) 가정에 기반하여 중첩 공격에 안전한 QMA용 3라운드 $\Sigma$-프로토콜을 최초로 구축합니다. 이는 표준 가정하에서 QMA에 대한 NIZK가 부재했던 공백을 메웁니다.
4. 새로운 증명 기법:
   • 0으로의 약속 전환을 통해 완전 비밀 공유의 특성을 활용하여 중첩 공격에 대한 NP 보안을 달성하는 새로운 하이브리드 논증.
   • 회로-해밀토니안 환원과 MPQC 및 QOTP를 결합하고, 중첩 쿼리 상황에서 EPR 쌍과 원타임 패드의 구별 불가능성을 활용하는 QMA 기법.

결과

본 논문은 다음 정리들을 확립합니다(비형식적):

• 정리 1.1: LWE의 포스트 양자 보안을 가정할 때, 중첩 쿼리를 수행하는 악의적인 검증자에 대해 제로 지식을 만족하는 QMA용 3라운드 $\Sigma$-프로토콜이 공통 참조 문자열(CRS) 모델에서 존재한다.
• 정리 1.2: 모든 포스트 양자 이중 모드 약속의 존재를 가정할 때, 중첩 쿼리를 수행하는 악의적인 검증자에 대해 제로 지식을 만족하는 NP용 3라운드 $\Sigma$-프로토콜이 CRS 모델에서 존재한다.

이 프로토콜들은 **통계적 건전성(statistical soundness)**과 계산적 제로 지식(computational zero-knowledge)(중첩 접근 권한을 가진 양자 다항 시간 공격자에게도 안전함)을 달성합니다.

의의 및 주장

저자들은 이 연구를 제로 지식 암호학을 양자 영역으로 확장하는 자연스럽고 필수적인 과정으로 규정합니다.

• 이론적 중요성: 표준 가정하에서 QMA에 대한 중셉 보안 ZK를 구축하는 난제를 해결했습니다. 이는 적절한 NIZK나 약속 체계의 부재로 인해 매우 어려운 과제로 여겨졌던 작업입니다.
• 실용적 관련성: 3라운드 구조 덕분에 이 프로토콜들은 NIZK보다 훨씬 가벼우며, 중첩 공격이 가능한 양자 공격자에게 안전해야 하는 포스트 양자 서명 및 보안 다자간 계산 컴파일러(예: GMW 스타일 컴파일러)를 위한 실질적인 경로를 제공합니다.
• 개념적 진보: "양자 헤드에서의 MPC" 프레임워크는 양자 계산의 부분 검증을 요구하는 다른 커밋-앤-오픈(commit-and-open) 또는 컷-앤-츄즈(cut-and-choose) 프로토콜에 적용될 수 있는 일반화 가능한 기법으로 제시됩니다.

본 논문은 QMA에 대한 NIZK가 오라클 모델이나 지정된 검증자 모델에서는 존재하지만, 중첩 공격이라는 특정 위협 모델에 대해 표준 가정과 공개 설정(CRS)을 사용하는 3라운드 프로토콜에 집중함으로써 더 직접적이고 효율적인 솔루션을 제공한다고 명시합니다.