기술 요약: 단일 실행에서의 임의 손실 허용 양자 위치 검증

1. 문제 정의

양자 위치 검증(Quantum Position Verification, QPV)은 상대론적 신호 전달 제약과 양자 정보를 사용하여 신뢰할 수 없는 증명자의 공간적 위치를 인증하는 것을 목표로 한다. No-cloning 정리(no-cloning theorem)는 고전적인 복제 공격을 방지하지만, 임의로 큰 얽힘을 공유하는 적대자에 대해서는 무조건적인 보안을 달밀할 수 없다. 따라서 연구는 적대자가 제한된 수의 얽힌 큐비트를 공유한다는 유계 얽힘(bounded-entanglement, BE) 모델에 집중한다.

QPF의 중요한 실질적 장애물은 광자 손실이다. 광섬유에서 전송 손실은 거리와 함께 기하급수적으로 증가한다. 표준 QPV 프로토콜(예: $QPV_{BB84}$, $QPV^f_{BB84}$, 그리고 병렬 구조인 $QPV^{f:n\to m}_{BB84}$)은 이상적인 전송을 가정한다. 이러한 가정은 근본적인 취약점을 만든다. 즉, 적대자가 큐비트를 가로채서 무작위 기저로 측정하고, 기저 예측이 맞았을 때만 결과를 보고하며, 그렇지 않을 때는 "손실"이라고 선언하는 전략을 취할 수 있다. 이 전략은 전송률이 50% 미만으로 떨어질 때마다 보안을 무너뜨린다.

이전 연구들은 손실과 얽힘을 각각 별도로 또는 순차적(sequential) 설정에서 동시에 다루었다. 구체적으로, [ABB+23]은 약속 기반의 수정 방식($c-QPV^f_{BB84}$)을 도입하여, 증명자가 측정 기저를 알기 전에 수신된 큐비트를 약속(commit)하도록 함으로써 임의의 손실을 허용했다. 그러나 이 기술은 반복되는 라운드에서 검증자가 불일치하는 약속을 탐지할 수 있는 순차적 구조에 의존했다. 이러한 기술은 단일 실행(single-execution, parallel) 프로토콜에는 확장되지 않는다. 단일 실행 프로토콜은 실질적인 구현과 더 큰 암호 체계의 서브루틴으로서 사용하기에 더 선호되지만, 기존의 단일 실행 프로토콜은 손실을 허용하지 못하거나 빛의 속도로 양자 통신을 수행해야 하는 제약이 있다.

2. 방법론

저자들은 병렬 단일 실행 프로토콜인 $QPV^{f:n\to m}_{BB84}$에 대한 약속 기반 수정안인 $c-QPV^{f:n\to m}_{BB84}$를 제안한다.

프로토콜 구조

프로토콜은 두 명의 검증자($V_0, V_1$)와 한 명의 증명자($P$)로 구성된다:

1. 준비(Preparation): 검증자들은 클래식 입력 $x, y \in \{0,1\}^n$과 함수 $z = f(x,y)$에 기반한 양자 상태(BB84 큐비트)를 생성한다.
2. 분배(Distribution): 양자 상태가 $P$에게 전송된 후, 주장된 위치에 동시에 도착하도록 타이밍이 맞춰진 클래식 문자열 $x$와 $y$가 전달된다.
3. 약속(Commitment - 새로운 단계): $P$는 양자 시스템을 수신한 직후, 그리고 $x$와 $y$를 배우기 전에, 어떤 큐비트가 성공적으로 수신되었는지($c_i=1$) 또는 손실되었는지($c_i=0$)를 나타내는 약속 문자열 $c \in \{0,1\}^m$을 브로드캐스트한다.
4. 검증 조건(Verification Condition): 프로토콜은 약속된 큐비트의 수 $|c| \geq k$ (여기서 $k$는 사전 정의된 임계값)를 만족하는 경우에만 진행된다.
5. 측정(Measurement): $x$와 $y$가 도착하면, $P$는 $z = f(x,y)$를 계산하고 약속된 집합 $C = \{i \mid c_i=1\}$에 속하는 큐비트만을 지정된 기저 $z_C$로 측정한다.
6. 검증(Verification): 검증자들은 보고된 결과가 오차 범위 $\gamma$ 내에서 집합 $C$에 대한 기대값과 일치하면 승인한다.

보안 분석 기법

보안 증명은 단일 실행에서는 하나의 약속 문자열만 제공되어 라운드 간의 불일치를 탐지할 수 없다는 도전에 대응한다. 저자들은 다음 기법들을 사용한다:

• 무신호 제약(No-Signalling Constraints): 분석은 적대자들(Alice와 Bob)이 공간적으로 분리되어 있다는 사실을 활용한다. 그들의 결합된 약속 분포는 무신호 조건을 만족해야 한다. 구체적으로, Alice의 약속은 Bob의 입력 $y$에 의존할 수 없고, 그 반대도 마찬가지이다.
• 수락 확률의 분해(Decomposition of Acceptance Probability): 저자들은 전체 수락 확률을 가능한 약속 문자열 $c$에 대한 합으로 분해한다. 그들은 고정된 $c$에 대한 조건부 수락 확률 $Pr[\text{accept } w_C \mid c]$를, 집합 $C$로 제한된 원래의 $QPV^{f:n\to m}_{BB84}$ 프로토콜의 보안성과 연관 지어 경계값을 설정한다.
• 지수적 감소(Exponential Decay): 무신호 제약과 원래 프로토콜의 건전성(soundness)의 지수적 감소(파라미터 $\lambda_\gamma$에 의해 제어됨)를 결합하여, 임계값 $k$에 따라 지수적으로 감소하는 전역 경계값을 도출한다.
• 정교화된 순차적 분석(Refined Sequential Analysis): 또한 저자들은 [ABB+23]의 순차적 프로토콜을 재검토한다. 그들은 확률적인 정지 시간(polynomial 횟수의 성공적인 라운드를 기다리는 것)을 고정된 $m$번의 라운드와 고정된 임계값 $k$로 대체한다. 이를 통해 "불일치하는 약속"에 대한 "이것 아니면 저것" 식의 진술에 의존하지 않고 직접적인 수락 확률 경계값을 얻을 수 있다.

3. 주요 기여

1. 최초의 손실 허용 단일 샷 QPV: 본 논문은 다음을 동시에 달축하는 최초의 프로토콜인 $c-QPV^{f:n\to m}_{BB84}$를 제시한다:
   • 단일 실행에서의 무시할 만한 건전성(soundness).
   • 클래식 입력 크기에 비례하는 양의 얽힘을 공유하는 적대자에 대한 보안.
   • 빛의 속도로 양자 통신을 요구하지 않음.
   • 임의로 큰 전송 손실에 대한 내성.
2. 약속 패러다임의 일반화: 이 연구는 무신호 상관관계를 사용하여 약속 수정을 순차적 설정에서 병렬 설정으로 성공적으로 확장함으로써, 기존에 병렬 설정을 가로막았던 순차적 구조에 대한 의존성을 극복했다.
3. 개선된 순차적 파라미터: 논문은 고정된 라운드 수와 임계값을 사용하여 순차적 약속 프로토콜을 정교화한다. 이는 적대자의 수락 확률이 임계값 $k$에 대해 지수적으로 감소하게 하며, 보정 항(correction term)은 $O(k^{-1/3})$으로 스케일링된다(이전 연구의 $O(r^{-1/4})$보다 개선됨).
4. 강건성(Robustness): 결과적인 프로토콜은 큐비트당 최대 3.7%의 노이즈 수준까지 강건성을 유지하며, 이는 원래의 기본 프로토콜의 노이즈 내성과 일치한다.

4. 결과

주요 이론적 결과(Theorem 1.1 및 Theorem 4.1)는 적절한 함수 $f$에 대해, BE($O(n)$) 모델에서 적대자가 승인될 확률이 다음과 같이 제한됨을 확립한다:
$$Pr[\text{accept } c-QPV^{f:n\to m}_{BB84}] \lesssim 2(\lambda_\gamma)^{k/2}$$
여기서 $\lambda_\gamma = 2^{h(\gamma)}(\frac{1}{2} + \frac{1}{2}\sqrt{2})$이고 $h(\cdot)$는 이진 엔트로피 함수이다.

• 손실 허용: 보안은 총 전송 큐비트 수 $m$이 아니라 $k$(성공적으로 수신된 큐비트 수)에 의존한다. 따라서 충분한 수의 큐비트가 결국 $k$를 충족할 수 있다면, 전송률이 아무리 낮더라도 프로토콜은 보안을 유지한다.
• 노이즈 허용: $\gamma < 0.037$ (3.7%)인 경우 프로토콜은 보안을 유지한다. 이는 $\lambda_\gamma < 1$임을 보장한다.
• 병렬 반복(Parallel Repetition): 단일 불리언 함수 $g$에 의한 병렬 반복으로 구성된 프로토콜의 경우(즉, $f = g^{\otimes m}$), 약속 버전의 보안은 $k$번의 반복을 가진 비약속 버전의 보안으로 귀결된다: $Pr[\text{accept } c-QPV^{g^{\otimes m}}_{BB84}] \leq 2\sqrt{Pr[\text{accept } QPV^{g^{\otimes k}}_{BB84}]}$.

5. 의의 및 주장

저자들은 이 연구가 QPV의 이론적 보안과 실질적 구현 사이의 중요한 간극을 메운다고 주장한다.

• 임의의 거리에 대한 실현 가능성: QPV를 임의의 손실 허용 가능하게 만듦으로써, 이 연구는 광자 손실이 상당한 장거리에서도 QPV를 실현 가능하게 만들며, 이는 실제 배포를 위한 전제 조건이다.
• 실용적 유용성: 단일 실행 프로토콜의 특성은 근접 미래의 구현 및 순차적 반복이 종종 비실용적인 더 큰 암호적 구성(예: 양자 키 분배, 메시지 인증)의 서브루틴으로서 사용하기에 특히 매력적이라는 점이 강조된다.
• 이론적 발전: 이 연구는 얽힌 공격자에 대한 기본 프로토콜의 보안 보장을 희생하지 않으면서 병렬 설정에서 약속 기반 보안을 달성할 수 있음을 입증한다.
• 실험적 관련성: 논문은 고정된 라운드 수와 수락 임계값을 제공함으로써 실험적 구현을 위한 개선된 정량적 파라미터를 제공하며, 이는 이전의 순차적 접근 방식에 내재된 실행 기간의 불확실성을 제거한다.

논문은 $c-QPV^{f:n\to m}_{BB84}$가 얽힌 공격자로부터 안전한 최초의 완전한 손실 허용 단일 샷 QPV 프로토콜로서, 기존에 QPV를 단거리 또는 이상적인 조건으로 제한했던 전송률 장벽을 효과적으로 제거했다고 결론짓는다.