⚛️ quantum physics

Zero-Knowledge Proofs of Quantumness

이 논문은 악의적인 고전적 검증자가 양자 증명자를 착취하는 것을 방지하기 위해 정보 누출을 제한하는 보안 개념을 정형화하고 추출 가능한 비대화형 인자들을 사용하여 기존의 양자성 체계들을 영지식 변형으로 어떻게 변환할 수 있는지를 입증함으로써 양자성의 영지식 증명 개념을 소개한다.

원저자: Duong Hieu Phan, Weiqiang Wen, Xingyu Yan, Jinwei Zheng

게시일 2026-09-22

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Duong Hieu Phan, Weiqiang Wen, Xingyu Yan, Jinwei Zheng

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

향후 수십 년 동안 컴퓨팅의 세계는 근본적인 변화를 맞이할 준비를 하고 있습니다. 수십 년 동안 가장 강력한 컴퓨터는 1과 0의 선형적인 방식으로 정보를 처리하는 고전적 기계들이었습니다. 이제 '양자 컴퓨터'라고 불리는 새로운 세대의 장치들이 등장하고 있습니다. 이 기계들은 양자 물리학의 기묘한 법칙에 따라 작동하며, 고전적 컴퓨터가 결코 따라올 수 없는 속도로 특정 문제들을 해결할 수 있게 해줍니다. 이러한 장치들이 이론에서 현실로 이동함에 따라 중요한 질문이 제기됩니다. 표준 컴퓨터를 사용하는 사람이 원격 장치가 단순히 영리하게 흉내 낸 것이 아니라 정말로 양자인 것을 어떻게 확신할 수 있을까요? 이것이 바로 '양자성 증명(proofs of quantumness)'의 과제입니다. 이는 양자 기계가 자신의 독특한 능력을 고전적 관찰자에게 증명해야 하는 디지털 악수와 같습니다. 그러나 이 상호작용에는 숨겨진 위험이 따릅니다. 마치 사람이 은행원에게 자신이 소유하지 않은 돈을 인출하기 위해 속임수를 쓰는 것처럼, 부정직한 관찰자는 양자 기계를 속여 어려운 문제를 대신 풀게 함으로써, 대가를 지불하지 않고도 그 계산 능력을 사실상 훔칠 수도 있습니다.

연구팀은 이제 '영지식 양자성 증명(zero-knowledge proofs of quantumness)'이라는 새로운 보안 계층을 도입하여 이 취약점을 해결했습니다. 그들의 연구에서, 연구진은 양자 장치가 추가적인 정보를 노출하지 않으면서도 자신이 양자임을 증명할 수 있는 방법을 공식화했습니다. 여기서 정보 노출이란 부정직한 관찰자가 악용할 수 있는 정보를 의미합니다. 연구진은 현재 시스템에서 악의적인 관찰자가 표준 검증자인 척함으로써 큰 수의 인수분해나 복잡한 수학적 퍼즐의 해답과 같은 유용한 데이터를 추출하기 위해 상호작용을 조작할 수 있음을 보여주었습니다. 새로운 프레임워크는 관찰자가 얻는 정보가 표준적인 비양자 컴퓨터에 의해 생성될 수 있는 수준을 넘지 않도록 보장함으로써 이를 방지합니다. 이는 양자 장치의 독특한 힘이 보호되며, 관찰자가 이 상호작용을 이용해 부당한 이득을 취할 수 없음을 의미합니다.

연구진은 오늘날 양자성을 증명하는 데 사용되는 가장 저명한 두 가지 방법론에 집중했습니다. 첫 번째는 양자 컴퓨터에는 쉽지만 고전적 컴퓨터에는 어려운 작업인 큰 수의 인수분해 난이도에 의존합니다. 두 번째는 '오류를 포함한 학습(learning with errors)'으로 알려진 데이터의 오류와 관련된 수학적 문제입니다. 두 경우 모두 연구진은 기존 프로토콜을 업그레이드하는 방법을 찾아냈습니다. 그들은 상호작용이 시작되기 전에 관찰자(고전적 검증자)가 특수한 종류의 디지털 인증서를 제공하도록 요구함으로써 이를 수행했습니다. 이 인증서는 관찰자가 부정직하게 행동하거나 숨겨진 비밀을 추출하려고 시도하지 않는다는 것을 증명합니다. 이는 관찰자가 정직하게 행동하거나, 적어도 악의적으로 행동하지 않는다는 보증 역할을 합니다. 만약 관찰자가 가짜나 조작된 숫자를 사용하여 양자 기계를 속이려 한다면, 그들은 스스로 비밀 해답을 알지 못하는 한 이 인증서를 생성할 수 없으며, 이는 속임수의 목적을 무색하게 만듭니다.

이를 구현하기 위해 연구진은 양자 증명과 '추출 가능한 비대화형 영지식 논증(extractable non-interactive zero-knowledge argument)'이라는 고전적 보안 도구를 결합했습니다. 이 도구는 관찰자가 해당 비밀 지식을 드러내지 않고도 인증서를 생성하는 데 필요한 비밀 지식을 보유하고 있음을 검증할 수 있게 해줍니다. 관찰자가 정직하다면 인증서는 유효하며 양자 증명이 진행됩니다. 만약 관절자가 악의적이고 가짜 숫자를 사용하여 속이려 한다면, 그들은 유효한 인증서를 생성할 수 없으며 상호작용은 실패합니다. 이는 양자 장치가 착취로부터 안전한 체계를 만듭니다. 연구진은 이 접근 방식이 인수분해 기반 방법과 오류를 포함한 학습 방법 모두에서 작동함을 입증했습니다. 그들은 고전적 컴퓨터가 상호작용을 시뮬레이션할 때 양자 컴퓨터와 정확히 동일한 결과를 생성할 수 있음을 증명했으며, 이는 추가적인 정보가 유출되지 않았음을 의미합니다.

이 연구의 의의는 양자 장치 소유자의 이익을 보호하는 능력에 있습니다. 양자 컴퓨터가 서비스 형태로 제공되는 미래에, 사용자들은 서버가 작업을 수행하기 전 실제로 양자인지 확인하고 싶어 할 것입니다. 이 새로운 보안 계층이 없다면, 부정직한 사용자는 서버를 속여 어려운 문제를 무료로 풀게 하거나, 더 나아가 사용자가 직접 풀어야 할 문제의 해답을 추출할 수도 있습니다. 연구진은 영지식 양자성 증명을 구현함으로써 검증 과정 자체가 탈취를 위한 루프홀(허점)이 되지 않도록 보장합니다. 양자 서버는 자신의 비밀이나 계산적 우위를 전혀 내주지 않으면서도 자신의 능력을 입증할 수 있습니다.

또한 이 연구는 이러한 상호작용을 바라보는 미묘하지만 중요한 관점의 변화를 강조합니다. 전통적으로 이러한 증명의 보안은 양자 기계가 거짓말을 하지 않는 데 초점을 맞추었습니다. 이 새로운 접근 방식은 관찰자가 거짓말을 하지 않도록 보장하는 데 초점을 맞춤으로써 그 흐름을 뒤집습니다. 이는 관찰자를 제약해야 할 대상으로 취급하며, 관찰자가 악의적으로 행동하지 않음을 증명하도록 요구합니다. 양자 테스트와 함께 고전적 보안 체크를 수행하는 과정에서 증명자와 검증자가 모두 역할을 수행하는 이 이중적 역할은 더욱 견고한 시스템을 만듭니다. 연구진은 인수분해 방법의 경우 관찰자가 숫자의 인수들을 알고 있음을 증명해야 하며, 오류를 포함한 학습 방법의 경우 데이터와 관련된 비밀 키를 알고 있음을 증명해야 한다는 것을 발견했습니다. 두 경우 모두 이러한 증명 요구 사항은 관찰자가 양자 기계를 자신의 어려운 문제를 해결하기 위한 도구로 사용하는 것을 차단합니다.

연구진은 이 두 가지 특정 스킴을 성공적으로 변환했지만, 모든 양자성 증명 방법이 이와 같이 쉽게 업그레이드될 수 있는 것은 아님을 인정합니다. 일부 기존 방법은 다른 가정을 기반으로 하거나 연구진이 사용한 표준 '질의-응답(challenge-and-response)' 형식을 따르지 않습니다. 예를 들어, 무작위 패턴 샘플링에 기반한 방법은 동일한 상호작용 구조를 따르지 않기 때문에 적응하기가 더 어렵습니다. 연구진은 자신들의 접근 방식이 가장 흔한 스킴들에는 강력하지만, 모든 유형의 양자 증명에 대한 보편적인 해결책을 찾는 것은 여전히 열린 과제로 남아 있다고 제안합니다. 또한 시스템이 미래의 양자 컴퓨터에 대해서도 완전히 안전하려면, 인증서에 사용되는 기초적인 고전적 도구들 자체가 양자 공격에 저항력이 있어야 한다고 언급했습니다. 그들은 이러한 수준의 보안을 제공할 수 있는 기존의 수학적 구조들을 지목했습니다.

궁극적으로, 이 연구는 더 안전한 검증의 미래를 위한 청사진을 제공합니다. 이는 분야를 단순한 능력 테스트에서, 양자 장치의 능력이 존중받는 안전하고 신뢰할 수 없는(trustless) 상호작용으로 이동시킵니다. 이 맥el에서 영지식 개념을 공식화함으로써, 연구진은 양자 기계의 무결성을 훼pt하지 않으면서도 양자성을 검증하는 것이 가능하다는 것을 보여주었습니다. 이는 양자 서비스의 실질적인 배포를 향한 중요한 단계이며, 양자 시대로의 전환이 보안과 신뢰의 토대 위에 구축되도록 보장합니다. 결과적으로, 이 시스템은 양자 컴퓨팅의 독특한 힘이 비밀을 훔치려는 자들에게 착취당할 염려 없이 입증되고 활용될 수 있도록 합니다.

=== 기술 요약: 양자성 제로 지식 증명 (Zero-Knowledge Proofs of Quantumness) ===

문제 정의

양자성 증명(Proofs of Quantumness, PoQ)은 양자 증명자(prover)가 자신의 양자 계산 능력을 고전적 검증자(verifier)에게 입증할 수 있도록 설계된 암호학적 프로토콜이다. 기존의 PoQ 방식(예: 소인수 분해 또는 LWE 기반 방식)은 클래식 증명자가 양자 장치인 것처럼 가장하는 위험(완전성/건전성)은 다루고 있지만, 악의적인 클래식 검증자에 대한 공식적인 보호 기능은 결여되어 있다.

현재의 방식들에서 악의적인 검증자( $V^*$ )는 상호작용을 악용하여 유용한 정보를 추출하거나, 정당한 계산 비용을 지불하지 않고 난제를 해결할 가능성이 있다. 예를 들어:

소인수 분해 기반 방식에서, 악의적인 검증자는 도전 정수 $N$ 을 특정 합성수 $N^*$ (예: RSA 공개 키로부터 유도된 숫자)로 대체하여 양자 증명자가 이를 소인수 분해하도록 강제함으로써, 어려운 계산 작업을 효과적으로 외주화할 수 있다.
LWE 기반 방식(예: [BCM+18])의 경우, 검증자가 LWE 인스턴스를 직접 풀 수는 없더라도, 양자 증명자가 생성한 트랜스크립트(transcripts)에는 클래식 증명자는 가질 수 없는 정보가 포함되어 있다. 악의적인 검증자는 이러한 상호작용을 활용하여 단순히 양자성을 검증하는 수준 이상의 이득을 취할 수 있다.

핵심 문제는 검증자가 증명 과정 중에 유용한 정보를 추출하는 것을 방지하는 공식화의 부재이다. 본 논문은 다음과 같은 질문을 던진다: 양자 증명자가 다른 유용한 정보를 드러내지 않으면서도 양자 능력을 입증할 수 있는 "제로 지식(zero-knowledge)" 양자성 증명이 존재하는가?

방법론

저자들은 **양자성 제로 지식 증명(Zero-Knowledge Proofs of Quantumness, ZKPoQ)**을 제안한다. 핵심적인 직관은 클래식 검증자가 양자 증명자와 상호작용하며 얻는 정보가, 동일한 검증자와 상의하는 시뮬레이션된 클래식 증명자에 의해 시뮬레이션될 수 있는 정보의 양을 초과해서는 안 된다는 것이다.

핵심 기술 접근법: 검증자 측 제로 지식 (Verifier-Side Zero-Knowledge)

본 논문은 증명자에게 제로 지식 증명을 요구하는 것이 종종 불가능하다고 주장한다. LWE 기반 방식에서 검증자는 자신이 알고 있는 특정 문장(예: 특정 방정식의 증거/witness)으로 증명자에게 도전한다. 증명자는 자신이 알지 못하는 문장에 대해 제로 지식 증명을 생성할 수 없다.

대신, 저자들은 검증자가 자신이 악의적으로 행동하지 않고 있음을 입증하기 위해 제로 지식 증명을 제공해야 한다는 **이중 역할 프레임워크(dual-role framework)**를 제안한다. 구체적으로:

추출 가능한 비대화형 제로 지식 증명 (Extractable NIZK): 검증자는 PoQ 챌린지에 사용된 비밀 파라미터(예: $N$ 의 소인수 분해 또는 LWE 비밀값 $s$ )의 유효성을 입증하는 추출 가능한 NIZK 증명을 제출해야 한다.
추출을 통한 시뮬레이션 (Simulation via Extraction): 제로 지식 속성을 위한 시뮬레이터는 검증자의 NIZK 증명으로부터 비밀 증거(witness)를 추출할 수 있다. 이 증거를 사용하여, 시뮬레이터는 양자 장치 없이도 상호작용 트랜스크립트를 완벽하게 재현할 수 있다.
건전성 보존 (Soundness Preservation): 클래식 증명자가 추출된 비밀을 사용하여 검증을 통과하는 것을 방지하기 위해, NIZK 증명 자체도 제로 지식이어야 한다. 이는 악의적인 클래식 증명자가 증명으로부터 비밀을 학습할 수 없도록 보장하며, 검증을 통과하기 위해서는 반드시 기저의 난제(소인수 분해 또는 LWE)를 독립적으로 해결해야 함을 의미한다.

주요 기여

1. ZKPoQ의 공식 정의

본 논문은 ZKPoQ를 다음 세 가지 속성을 만족하는 양자 증명 대화형 증명(QPIP) 시스템으로 정의한다:

양자 완전성 (Quantum Completeness): 정직한 양자 증명자는 높은 확률로 수락된다.
클래식 건전성 (Classical Soundness): 클래식 증명자는 무시할 수 없는 확률로 검증을 통-과할 수 없다.
계산적 제로 지식 (Computational Zero-Knowledge): 임의의 PPT 검증자 $V^*$ 에 대하여, $V^*$ 가 양자 증명자와 상호작용할 때의 뷰(view)와 시뮬레이터와 상호작용할 때의 뷰가 계산적으로 구별 불가능한 PPT 시뮬레이터 $Sim_{V^*}$ 가 존재한다.

2. 소인수 분해 기반 PoQ의 변환

저자들은 Shor의 소인수 분해 기반 PoQ를 ZKPoQ 방식으로 변환하는 방법을 보여준다 (그림 7):

검증자는 $N = p \cdot q$ 를 생성하고, 소인수 분해 $(p, q)$ 에 대한 추출 가능한 NIZK 증명을 제공한다.
양자 증명자는 진행하기 전에 이 증명을 검증한다.
보안성: 제로 지식 속성은 NIZK의 추출 가능성(시뮬레이터가 $p, q$ 를 얻을 수 있음)에 의존한다. 건전성은 NIZK의 제로 지식 속성(클래식 증명자가 증명으로부터 $p, q$ 를 학습하는 것을 방지함)에 의존한다.

3. LWE 기반 PoQ의 변환

저자들은 [BCM+18] LWE 기반 PoQ 방식을 ZKPoQ 방식으로 변환한다 (그림 8):

검증자는 NTCF 키 $k$ 와 그에 대응하는 트랩도어(trapdoor) $t_k$ 를 생성한다.
검증자는 $k$ 와 관련된 LWE 비밀값 $s$ 에 대한 추출 가능한 NIZK 증명을 제공한다.
보안성: 소인수 분해 사례와 마찬가지로, 시뮬레이터는 $s$ 를 추출하여 프로토콜을 시뮬레이션한다. 건전성은 NIZK의 제로 지식 속성이 클래식 증명자가 $s$ 를 학습하여 검증을 통과하는 것을 방지하기 때문에 유지된다.

4. 실현 가능성 및 가정

이 변환은 공통 참조 문자열(CRS) 모델에서의 추출 가능한 NIZK 증명의 존재에 의존한다.
저자들은 ZKPoQ 자체를 위해 클래식적으로 안전한 추출 가능한 NIZK가 충분하다는 점을 언급한다. 그러나 인증 가능한 무작위성(certifiable randomness)이나 키 리싱(key leasing)과 같이 양자 증명자 자체가 악의적일 수 있는 응용 분야에서는 **양자 내성(post-quantum secure)**을 가진 LWE 기반의 추출 가능한 NIZK가 필요하다.

결과

본 논문은 두 가지 주요 정리를 확립한다:

정리 1: 추출 가능한 NIZK가 주어지면, 소인수 분해 기반 PoQ 방식을 ZKPoQ 방식으로 변환할 수 있다.
정리 2: 추출 가능한 NIZK가 주어지면, LWE 기반 PoQ 방식 [BCM+18]을 ZKPoQ 방식으로 변환할 수 있다.

저자들은 이 변환된 방식들이 양자 완전성, 클래식 건전성, 그리고 계산적 제로 지식을 만족함을 증명한다. 또한, 제로 지식 속성이 악의적인 검증자가 양자 장치를 이용해 난제(특정 정수의 소인수 분해 또는 LWE 인스턴스 해결 등)를 해결하여 이득을 취하는 것을 방지함을 명시적으로 보여준다.

의의 및 주장

본 논문은 ZKPoQ를 양자성 증명을 위한 강화된 보안 개념으로 위치시킨다.

검증자 행동 규제: 이 프레임워크는 검증자의 행동을 "악의적"인 상태에서 "정직하지만 호기심 많은(honest-but-curious)" 상태로 효과적으로 규제하여, 검증 과정 중에 양자 장치의 계산 능력이나 비밀이 탈취되지 않도록 보장한다.
실용적 관련성: 양자 서비스에 클래식 사용자가 구독하게 될 포스트 양자 시대에, ZKPoQ는 검증 과정이 양자 서버의 능력이나 비밀을 유출하지 않도록 보장한다.
한계 및 향-연구 과제: 저자들은 추출 가능한 NIZK를 사용하는 자신들의 일반적인 변환이 챌린지-응답(challenge-response) 프로토콜(소인수 분해 및 LWE)에 특화되어 있음을 인정한다. 또한, 이 접근 방식이 다른 LWE 기반 프로토콜(예: 랜덤 오라클 기반)이나 효율적인 클래식 검증이 불가능한 보손 샘플링(Boson Sampling)과 같은 비대화형 방식에도 적용될 수 있는지 여부는 불분명하다고 언급한다. 마지막으로, CRS 모델을 제거하고 플레인 모델(plain model)로 이동하는 것을 향후 연구 방향으로 제시한다.

요약하자면, 본 논문은 양자성 증명 맥락에서 제로 지식을 공식화한 최초의 연구이며, 악의적인 검증자로부터 보호하기 위해 기존 PoQ 방식을 업그레이드할 수 있는 구체적이고 증명 가능한 보안 방법을 제공한다.