원저자: James Bartusek, Jiahui Liu, Giulio Malavolta

게시일 2026-06-10

📖 4 분 읽기🧠 심층 분석

원저자: James Bartusek, Jiahui Liu, Giulio Malavolta

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

개요: "마법의 상자" 문제

당신에게는 매우 똑똑하고 빠른 양자 컴퓨터(이를 **증명자(Prover)**라고 부릅시다)가 있습니다. 그리고 당신에게는 일반적인 느린 노트북(이를 **검증자(Verifier)**라고 부릅습니다)이 있습니다. 증명자는 이렇게 주장합니다. "나는 이 믿기지 않을 정도로 어려운 수학 문제를 풀었습니다!"

문제는 증명자의 답이 너무 복잡해서, 만약 당신이 직접 확인하려 한다면 백만 년이 걸릴 수도 있다는 점입니다. 당신은 스스로 그 일을 수행하지 않고도 증명자를 믿을 수 있는 방법이 필요합니다. 이것을 **간결한 논증(Succinct Argument)**이라고 합니다. 이것은 작업이 올바르게 수행되었음을 증명하는 "마법의 영수증"과 같습니다. 하지만 이 영수증은 아주 작고 읽는 데 단 1초밖에 걸리지 않습니다.

일반 컴퓨터(고전 컴퓨터)의 경우, 우리는 오랫동안 이러한 마법의 영수증을 사용해 왔습니다. 하지만 양자 컴퓨터(QMA 문제를 다루는)를 위해서는 훨씬 더 어려웠습니다. 지금까지는 이러한 영수증을 만드는 유일한 방법이 LWE(Learning With Errors)라는 매우 특수하고 강력한 자물쇠를 필요로 했습니다. LWE를 거대하고 복잡한 강철 금고라고 생각해 보세요. 그것은 효과적이지만, 무겁고, 우리는 오직 한 가지 방식으로만 그것을 만드는 법을 알고 있습니다.

이 논문은 다음과 같이 말합니다: "우리는 더 가볍고 유연한 도구를 사용하여 이러한 마법의 영수증을 만드는 새로운 방법을 찾아냈습니다. 이제 더 이상 그 거대한 강철 금고가 필요하지 않습니다."

2단계 구성 방식

저자들은 "모듈형 접근 방식(Modular Approach)"을 사용하여 새로운 시스템을 구축했습니다. 집을 짓는다고 상상해 보세요. 하나의 거대한 콘크리트 판을 붓는 대신, 그들은 두 개의 구별되는 재사용 가능한 단계로 나누어 집을 지었습니다.

1단계: "라운드 효율적인" 설계도

먼저, 그들은 증명자와 검증자가 여러 번 대화를 주고받되, 대화하는 횟수를 낮고 예측 가능한 수준(게임의 정해진 라운드 수처럼)으로 유지하는 프로토콜을 설계했습니다.

기존 방식: 이전 방법들은 증명자가 자신이 답을 알고 있다는 것을 증명하기 위해 많은 힘을 써야 했으며, 종종 그 무거운 "LWE 금고"에 의존해야 했습니다.
새로운 방식: 저자들은 **사전 준비 없는 상태 생성(Oblivious State Preparation, OSP)**이라는 도구를 사용했습니다.
- 비유: 검증자가 증명자에게 특정 양자 상태(클로 상태, claw state)를 준비하도록 요청하고 싶지만, 증명자가 그 상태가 무엇인지는 알지 못하게 하고 싶다고 가정해 봅시다. 이는 마치 요리사에게 재료가 무엇인지 알려주지 않은 채 비밀 레시피를 요리해 달라고 요청하는 것과 같습니다. OSP는 검증자가 이 "비밀 지침"을 안전하게 전달할 수 있게 해줍니다.
- 이 단계는 작동하는 증명 시스템을 만들어내지만, 교환되는 메시지는 여전히 매우 큽니다 (마치 책 한 페이지를 읽었다는 것을 증명하기 위해 도서관 전체의 책을 보내는 것과 같습니다).

2단계: "압축 기계"

이것이 이 논문의 가장 큰 혁신입니다. 그들은 "일반화된 통신 압축 컴파일러(Generalized Communication Compression Compiler)"를 만들었습니다.

문제: 1단계에서 메시지는 너무 컸습니다. 만약 증명자가 어떤 점을 증명하기 위해 100페이지짜리 문서를 보내야 한다면, 검증자는 여전히 100페이지를 읽어야 합니다.
해결책: 그들은 이 거대한 메시지들을 유효성을 잃지 않으면서도 작고 고정된 크기의 패킷으로 압축하는 기계를 만들었습니다.
비유: 당신에게 100페이지짜리 계약서가 있다고 상상해 보세요. 당신은 당신이 거기에 서명했다는 것을 증명하고 싶지만, 종이 전체를 보낼 수는 없습니다. 이때 당신은 특별한 "양자 복사기"(**붕괴하는 해시 함수(Collapsing Hash Functions)**에 기반함)를 사용하여 계약서 전체를 하나의 작은 지문으로 압축하고, 실제 계약서 전체를 가지고 있지 않았다면 그 지문을 위조할 수 없었음을 증명합니다.
마법의 기술: 이 압축은 **양자 경직성(Quantum Rigidity)**이라는 개념에 기반합니다.
- 비유: 해파리를 생각해보세요. 해파리의 한 곳을 찌르면, 해파리 전체가 예측 가능한 방식으로 꿈틀거립니다. 만약 증명자가 속임수를 쓰려고 한다면, 그 "꿈틀거림"(양자 상태)은 규칙과 일치하지 않을 것입니다. 검증자는 메시지가 이제 매우 작아졌음에도 불구하고, 증명자가 정직한지 확인하기 위해 이 꿈틀거림을 확인할 수 있습니다.

이것이 왜 중요한가 ( "무구조적" 이점)

이 논문은 우리가 보안을 생각하는 방식의 중대한 변화를 강조합니다.

기존의 현실: 양자 증명을 검증하기 위해서 우리는 반드시 "LWE 금고"를 사용해야만 했습니다. 그것이 자물쇠에 맞는 유일한 열쇠였습니다.
새로운 현실: 이 논문은 우리가 대신 OSP와 붕괴하는 해시 함수를 사용할 수 있음을 보여줍니다.
- 비유: 만약 LWE가 거대하고 맞춤 제작된 강철 금고라면, 새로운 도구들은 하이테크 숫자 자물쇠와 지문 스캐너와 같습니다. 이것들은 "무구조적(unstructured)"입니다. 즉, 더 유연하며 하나의 특정한, 경직된 수학적 가정에 의존하지 않습니다.

최종 결과

이 두 단계를 결합함으로써, 저자들은 LWE의 어려움에 의존하지 않는 최초의 QMA를 위한 간결하고 고전적으로 검증 가능한 논증을 만들어냈습니다.

간결함 (Succinct): 증명은 매우 작습니다 (몇 킬로바이트).
고전적 검증 가능성 (Classically-Verifiable): 증명을 확인하기 위해 양자 컴퓨터가 필요하지 않습니다. 당신의 일반 노트북으로도 충분히 가능합니다.
모듈형 (Modular): 그들은 새로운 물리 법칙을 발명한 것이 아닙니다. 단지 기존의 도구들(OSP와 해시)을 가져와서 영리한 방식으로 결합했을 뿐입니다.

한 문장 요약

저자들은 "비밀 지침" 도구와 "메시지 압축기"를 결합하여, 양자 계산 검증을 위해 더 가볍고 효율적인 "마법의 영수증" 시스템을 구축함으로써, 양자 검증을 구현하기 위해 무거운 특정 "LWE 금고"가 필요하지 않다는 것을 증명했습니다.

기술 요약: QMA를 위한 간결한 논증에 대한 모듈형 접근 방식

1. 문제 정의

간결한 논증 시스템(Succinct argument systems)은 검증자가 계산 자체를 실행하는 데 필요한 시간보다 훨씬 낮은 복잡도로 계산의 유효성을 확인할 수 있게 해준다. 고전적 설정에서, Kilian (STOC '92)은 임의의 확률적 검사 가능 증명(PCP)이 충돌 저항성 해시 함수(비구조적 가정)만을 사용하여 간결한 논증 시스템으로 컴파일될 수 있음을 입증했다.

양자 설정에서는, 양자 증명을 필요로 하는 문장(QMA, Quantum Merlin-Arthur)을 위한 간결하고 고전적으로 검증 가능한 논증을 구축하는 것이 목표이다. 최근의 연구들은 이러한 시스템의 타당성을 확립했으나, 이는 주로 학습 기반 오류(LWE)라는 구조적 난해성 가정에 크게 의존하고 있다. 이는 구조적 가정이 필요하지 않은 고전적 설정과는 대조적이다.

본 연구가 다루는 핵심 문제는 다음과 같다: LWE의 특정 난해성에 의존하지 않고도 QMA를 위한 간결하고 고전적으로 검증 가능한 논증을 구축할 수 있는가? 즉, 양자 검증을 위한 암호학적 토대를 다양화할 수 있는가?

2. 방법론

저자들은 더 약한 가정 하에서 QMA에 대한 간결성을 달성하기 위해 모듈식의 2단계 프레임워크를 제안한다.

1단계: 라운드 효율적인 고전적 검증

첫 번째 단계는 라운드 복잡도 측면에서는 효율적(poly( $\lambda$ ) 라운드)이지만, 통신 크기 측면에서는 반드시 간결할 필요는 없는 QMA용 고전적 검증 가능 논증 시스템을 설계하는 것이다.

접근 방식: 저자들은 "컴파일된 비로컬 게임(compiled non-local games)" 패러다임(구체적으로 KLVY 컴파일러)을 채택한다. 이들은 상수 완결성-건전성 갭(constant completeness-soundness gap)을 가진 2-증명 비로컬 게임을 활용한다([MNZ24]의 단순화된 프로토콜 기반).
핵심 수정 사항: LWE 기반의 양자 완전 동형 암호(QFHE)나 특정 TCF 속성을 요구했던 이전의 인스턴스들과 달리, 이 프로토콜은 **Oblivious State Preparation (OSP)**에 의존한다. OSP를 통해 고전 클라이언트는 입력 내용을 드러내지 않고 양자 서버에 양자 계산(구체적으로 비로컬 게임의 "Alice" 연산)을 위임할 수 있다.
결과: 이는 라운드 수가 증명 크기에 독립적인 poly( $\lambda$ ) 라운드의 프로토콜을 생성하지만, 각 라운드당 통신량은 클 수 있다(증명 크기에 의존함).

2단계: 일반화된 통신 압축

두 번째 단계는 라운드 효율적인 프로토콜의 통신을 간결한 형식(총 poly( $\lambda$ ) 비트)으로 압축한다.

기술: 저자들은 **일반화된 통신 압축 컴파일러(Generalized Communication Compression Compiler)**를 도입한다. 이 컴파일러는 임의의 $T$ -라운드 대화형 프로토콜을 원래의 메시지 크기와 상관없이 총 통신량이 $T \cdot \text{poly}(\lambda)$ 로 제한되는 프로토콜로 변환한다.
메커니즘:
1. Commitment 기반 Secure Function Sampling (SFS): 컴파일러는 검증자의 메시지를 "커밋된 SFS" 프로토콜로 대체한다. 검증자는 자신의 무작위 시드(seed)를 커밋하고, 증명자는 자신의 메시지를 커밋한다. 이후 상호작용은 증명자가 커밋된 입력값에 대해 검증자의 다음 메시지 함수를 계산하는 보안 함수 평가(secure function evaluation)를 통해 시뮬레이션된다.
2. 양자 강직성(Quantum Rigidity): 압축의 핵심은 양자 강직성 기술(Zhang [Zhang23]의 확장)에 있다. 검증자는 증명자에게 "클로 상태(claw state, 두 개의 역상의 중첩 상태)"를 보낸다. 증명자는 이 중첩 상태에 대해 함수를 계산하며, 정직한 행동을 보장하기 위해 "강직성" 체크(계산 및 Hadamard 기저 테스트)를 통해 테스트받는다.
3. 고전적 검증: 고전적 검증 가능성을 복원하기 위해, 저자들은 클로 상태의 양자 전송을 OSP에 기반한 고전적 프로토콜로 대체한다. 저자들은 OSP가 클로 상태에 대한 Verifiable State Preparation (VSP)을 함의함을 증명하여, 검증자가 완전히 고전적으로 남을 수 있도록 한다.
가정: 이 단계는 Collapsing Hash Functions(충돌 저항성의 양자 대응물)와 OSP에 의존한다.

3. 주요 기여

QMA를 위한 새로운 암호학적 토대: 본 논문은 LWE의 난해성에 의존하지 않고 QMA를 위한 간결하고 고전적으로 검증 가능한 첫 번째 논증 시스템을 제시한다. 대신 다음을 활용한다:
- Oblivious State Preparation (OSP): 평문 트랩도어 클로 없는 함수(TCF)로부터 구축 가능하며, TCF는 LWE, 암호학적 그룹 작용(cryptographic group actions), 격자 동형 문제(lattice isomorphism problem) 등을 기반으로 인스턴스화될 수 있다.
- Collapsing Hash Functions: 양자 무작위 오라클 모델(QROM) 및 다양한 계산 환경에서 성립하는 표준적인 "비구조적" 가정이다.
일반화된 통신 압축 컴파일러: 저자들은 양자 대화형 프로토콜(고전 검증자와 양자 증명자 사이)의 통신 복잡도를 고정된 다항식 수준으로 줄이는 범용 컴파일러를 개발했다. 이 컴파일러는 커밋된 입력을 처리하기 위해 Zhang [Zhang23]의 연구를 확장한 것이며, 그 자체로 독립적인 가치가 있다.
OSP를 통한 라운드 효율적 프로토콜: 저자들은 LWE 기반의 QFHE나 적응형 하드코어 비트(adaptive hard-core bit) 속성을 피하고, 오직 OSP만을 사용하여 QMA를 위한 poly( $\lambda$ )-라운드 고전 검증 가능 프로토콜을 구축했다.
간결한 양자 샘플링: 부산물로서, 이 기술은 양자 샘플링 문제에 대한 간결한 고전적 검증을 제공하도록 확장되어, 이전에는 어떤 가정으로부터도 알려지지 않았던 결과를 확립했다.

4. 결과

정리 1 (주요 결과): OSP와 collapsing hash functions를 가정할 때, 다음을 만족하는 고전 검증 가능 QMA 논증 시스템이 존재한다:
- 통신 크기: $\text{poly}(\lambda)$ .
- 검증자 복잡도: $|x| \cdot \text{poly}(\lambda)$ , 여기서 $|x|$ 는 인스턴스 크기이다.
- 건전성(Soundness): 무시할 수 있는 수준 (순차적 반복을 통해 달성됨).
정리 2 (샘플링): LWE를 가정할 때, 역 다항식 건전성(inverse-polynomial soundness)을 가진 양자 샘플링에 대한 간결한 고전적 논증이 존재한다. (참고: 이 특정 결과는 LWE를 가정하지만, 이는 압축 기술의 일반성을 보여준다).
기술적 보조 정리:
- OSP가 BB84 상태 및 그에 따른 클로 상태에 대한 VSP를 함의한다는 증명 (정리 14).
- 일반화된 KLVY 컴파일러가 OSP 기반의 블라인드 위임을 통해 인스턴스화될 때, 상수 건전성 갭을 가진 라운드 효율적 프로토콜을 생성한다는 증명 (정리 54).

5. 의의 및 주장

본 논문은 간결한 양자 논증을 위한 암호학적 지평을 크게 넓힌다고 주장한다. QMA의 간결성을 LWE로부터 분리함으로써, 본 연구는 양자 검증을 위해 사용할 수 있는 암호학적 난해성의 원천을 다양화한다.

모듈성: 이 접근 방식은 라운드 효율성(OSP와 비로컬 게임이 담당)과 통신 간결성(압축 컴파일러와 collapsing functions가 담당)의 문제를 분리한다. 이러한 모듈성은 전체 시스템을 재설계하지 않고도 각 구성 요소를 향후 개선할 수 있게 한다.
비구조적 가정: 압축 단계에서 collapsing hash functions(비구조적 가정)를 사용하는 것은, NP에 대한 간결한 논증이 비구조적 가정만으로도 존재하는 고전적 설정에 양자 설정을 더 가깝게 만든다.
독립성: 일반화된 통신 압축 컴파일러는 QMA뿐만 아니라 모든 양자 대화형 프로토콜을 압축할 수 있는 도구로서 독립적인 가치를 지닌다.

저자들은 자신들의 구성이 여전히 OSP(현재 LWE 기반 인스턴스가 존재하지만 다른 것도 존재함)와 collapsing functions에 의존하고 있음을 인정하며 신중한 태도를 유지한다. 저자들은 모든 구조적 가정을 제거했다고 주장하는 것이 아니라, OSP와 collapsing functions가 가용하다면 QMA의 간결한 논증을 구축하는 데 있어 LWE가 반드시 필수적인 것은 아님을 성공적으로 입증했다.

A Modular Approach to Succinct Arguments for QMA