기술 요약: 시공간을 통한 큐비트 추적 방법

1. 문제 정의

위치 기반 암호(Position-based cryptography, PBC)는 사용자의 물리적 위치를 암호학적 자격 증명으로 사용하는 것을 목표로 한다. 표준 프리미티브인 양자 위치 검증(Quantum Position Verification, QPV)은 검증자가 주장된 위치 $L$에 있는 증명자에게 양자 챌린지를 보내고, 엄격한 타이밍 제약 내에 응답이 도착하는지 확인하는 과정을 포함한다.

그러나 기존의 QPV 보안 정의는 개념적 간극을 가지고 있다. 현재의 정의는 분산된 적대적 팀 중 적어도 한 명이 $L$에 위치하고 있음을 보장할 뿐이다. 이는 적대적 팀의 구성원 중 누구도 $L$에 있지 않더라도, 필요한 양자 정보를 공간과 시간에 걸쳐 분산시킴으로써 증명자를 모사(spoofing)할 수 있는 시나리오를 허용한다. 결과적으로, 성공적인 QPV 증명이 반드시 특정 위치에 단일하고 지속적인 엔티티가 있었음을 인증하는 것은 아니며, 분산된 팀이 움직이는 증명자를 모사하는 것을 방지하지도 못한다.

이러한 한계는 궤적 검증(trajectory verification), 즉 증명자가 시공간 상의 특정 경로 $L(\cdot)$을 따라 이동했음을 검증하는 능력의 실현을 가로막는다. 경로 상의 서로 다른 지점에서 별도의 QPV 프로토콜을 실행하는 것은, 개별 QPV 프로토콜의 보안 보장이 시간의 흐름에 따라 양자 상태를 연결하지 못하기 때문에, 단일한 이동 증명자와 정지된 증명자들의 사슬을 구분하지 못한다.

2. 방법론 및 핵심 개념

저자들은 특정 시공간 지점 $(L, t)$에 특정 불변(unclonable) 객체가 존재하도록 요구함으로써 적대자의 행동을 해당 지점으로 "고정(pinpoint)"하는 더 강력한 보안 개념인 **양자 국소화(Quantum Localization)**를 도입한다. 저자들은 세 가지 유형의 국소화를 정의한다:

1. 얽힘 국소화(Entanglement Localization): $(L, t)$에 있는 증명자의 상태로부터 검증자의 얽힌 쌍의 절반을 추출할 수 있는 능력.
2. 상태 국소화(State Localization): $(L, t)$에 있는 특정 불변 양자 상태(예: 코셋 상태 패밀리로부터의 상태)를 추출할 수 있는 능력.
3. 기능 국소화(Functionality Localization): $(L, t)$에서 비밀 함수 $f_k$를 계산할 수 있는 능력을 추출할 수 있는 능력이며, 이 능력은 다른 곳에서는 계산될 수 없음을 보장한다.

양자 앵커 상태 (The Quantum Anchor State)

이 구조는 **양자 앵커 상태(Quantum Anchor State)**라 불리는 이분 양자 상태 $|\Psi\rangle_{\mathcal{A}\mathcal{V}}$에 의존한다:

• $\mathcal{A}$ (Anchor)는 검증자가 보유한다.
• $\mathcal{V}$ (V-essel)는 증명자에게 전송된다.
• 이 상태는 EPR 쌍과 "디코이(decoy)" 큐비트로 구성되며, 무작위 기저 변경 유니터리 $U_{shift}$에 의해 스크램블링된다.
• 구조는 부분 공간 $S \le T \le \mathbb{F}_2^{3n}$와 시프트 $u, v$에 의해 정의된다. Vessel 레지스터는 이러한 부분 공간들에 대한 코셋 상태의 중첩을 포함한다.

비붕괴형 vs 붕괴형 오라클 (Non-Collapsing vs. Collapsing Oracles)

중심적인 기술적 혁신은 얽힘을 파괴하지 않고 검증하는 **비붕괴형 테스트(non-collapsing tests)**의 사용이다.

• 붕괴형 테스트(Collapsing Test): 얽힌 상태를 측정(예: 표준 기저 또는 하다마르 기저에서의 측정)하여 파동함수를 붕괴시키는 표준적인 방식이다.
• 비붕괴형 테스트(Non-Collapsing Test): 증명자는 부분 공간(예: $T+v$ 또는 $S^\perp + u$)에 대한 멤버십을 확인하고 유효한 쿼리에 대해 비밀 값을 반환하는 클래식 오라클(이상적인 난독화로 모델링됨)에 접근 권한을 가진다. 증명자는 이 오라클에 대해 결맞는(coherent) 쿼리를 수행한다.
• 구별 불가능성(Indistinguishability): 압축된 오라클(Compressed Oracle) 기법과 부분 공간 구별 불가능성 보조정리를 사용하여, 저자들은 비붕괴형 테스트를 통과한(상태를 붕괴시키지 않는) 증명자가 그에 대응하는 붕괴형 테스트를 통과했을 증명자와 구별 불가능함을 증명한다. 이를 통해 검증자는 프로토콜 자체에 의해 상태가 파괴되지 않은 상태에서도 프로토콜 이후에 얽힘이나 상태를 추출할 수 있다.

얽힘 단일성 게임 (Monogamy-of-Entanglement Games)

보안을 증명하기 위해 저자들은 서로 다른 시공간 지점에서 챌린지에 답하려고 시도하는 적대자(Left, Middle, Right 구성 요소로 분할됨)를 모델링하는 **다단계 얽힘 단일성 게임(Multi-Stage Monogamy-of-Entanglement Games)**을 정의한다.

• 보안 증명은 만약 적대자가 높은 확률로 성공한다면, "Middle" 구성 요소(검증된 위치에 있는)가 로컬하게 상태를 붕괴시키는 측정(또는 오라클 쿼리)을 수행했어야 함을 보여주는 것에 기초한다.
• **얽힘의 단일성(Monogamy of Entanglement)**을 활용하여, 저자들은 적대자가 여러 위치에서 동시에 검증자의 앵커와 상관관계를 유지할 수 없음을 보여준다. 만약 적대자가 성공한다면, 얽힘은 쿼리가 발생한 특정 시공간 지점으로 국소화되어야만 한다.

3. 주요 기여 및 결과

1. 얽힘 국소화

저자들은 검증자가 특정 시공간 지점 $(L, t)$에 있는 증명자의 상태로부터 자신의 앵커 상태에 대한 얽힌 파트너를 추출할 수 있는 프로토콜을 구축한다.

• 결과: 증명자 전략이 비영가한 확률로 수락되면, $(L, t)$에 있는 상태를 주었을 때 원래의 얽힌 상태와 높은 충실도(fidelity)를 갖는 레지스터를 출력하는 추출기가 존재한다.
• 범위: 이 프로토콜은 이상적 난독화 모델(Ideal Obfuscation Model)(클래식 오라클 모델)에서 안전하며, 이는 양자 내성 난독화(iO) 및 일방향 함수를 사용하여 휴리스틱하게 구현될 수 있다.

2. 궤적 검증

얽힘 국소화를 바탕으로 저자들은 **궤적 검증(Trajectory Verification)**을 정의한다.

• 메커니즘: 검증자는 "vessel" 레지스터를 증명자에게 보내고, 주장된 궤적 $L(\cdot)$을 따라 이산적인 지점들 $(L(t_i), t_i)$에서 일련의 얽힘 국소화 프로토콜을 실행한다.
• 결과: 증명자가 수락되면, 얽힘은 궤적 상의 모든 지점에 국소화된다. 얽힘의 단일성에 의해, 이는 단일 양자 시스템(vessel)이 경로 $L(\cdot)$을 따라 이동했음을 의미한다. 이는 "정지된 증명자들의 사슬" 공격을 배제한다. 그러한 사슬은 전체 궤적 동안 필요한 얽힘을 동시에 유지할 수 없기 때문이다.

3. 상태 및 기능 국소화

• 상태 국소화: 저자들은 얽힘뿐만 아니라 특정 양자 상태(예: BB84 상태 또는 코셋 상태)를 국소화하는 데 이 기술을 적응할 수 있음을 보여준다. 추출기는 검증된 위치에서 특정 상태 $|\psi_k\rangle$를 복구한다.
• 기능 국소화: 저자들은 증명자가 검증된 위치에서 비밀 함수 $f_k$를 계산할 수 있는 능력을 보유해야 한다는 개념을 도입한다. 이는 국소화 기술을 양자 상태 난독화(최적의 복제 방지 기술)와 결합하여 달성된다. 결과적으로 계산 능력은 $(L, t)$에 국소화되며 다른 곳에서는 계산될 수 없음을 보장한다.

4. 부정적 결과: $f$-BB84의 비국소화 가능성

본 논문은 모든 QPV 프로토콜이 국소화를 만족하는 것은 아님을 입증한다. 저자들은 잘 알려진 $f$-BB84 프로토лот($f(x,y)$에 따라 EPR 쌍을 측정하는 프로토콜)이 얽힘 국소화가 불가능함을 보여준다.

• 공격: 세 명의 증명자로 구성된 분산 팀은 양자 일회용 패드(one-time pad)를 공유함으로써 이 프로토콜을 완벽하게 모사할 수 있다. 중간 증명자는 올바른 측정을 수행하지만, 얽힘은 세 명의 증명자 사이에 비국소적으로 분산되어 있어, 어떤 단일 추출기도 중간 위치에서 전체 얽힌 상태를 복구할 수 없게 만든다. 이는 새로운 국소화 정의의 강력함을 강조한다.

4. 의의 및 주장

저자들은 자신들의 연구가 직관적인 목표(물리적 엔티티 추적)와 공식적인 보안 정의 사이의 간극을 해결함으로써 위치 기반 암호학의 더 강력한 토대를 제공한다고 주장한다.

• 개념적 전환: 본 논문은 PBC를 "누군가 거기에 있는가?"라는 이진적 검증에서 "이 특정 양자 정보가 여기에 있는가?"라는 연속적 검증으로 이동시킨다.
• 궤적 검증: 저자들은 시공간 상의 엔티티의 궤적을 검증하는 최초의 실현 가능성을 제시하며, 이는 기존의 표준 QPV 보안 하에서는 정의하기 어렵거나 불가능하다고 여겨졌던 작업이다.
• 물리적 시공간과 정보: 이 결과는 위치와 정보 사이의 밀접한 연결을 탐구하며, 암호학적 능력이 양자 역학을 통해 물리적 시공간 제약과 근본적으로 결합될 수 있음을 시사한다.
• 모델: 보안은 이상적 난독화 모델에서 증명된다. 저자들은 이것이 (iO를 통해 구현되는) 휴리스틱한 가정임을 인정하지만, 고전 암호학에서 랜덤 오라클 모델을 사용하는 것과 마찬가지로 이러한 강력한 프리미티브를 위해 표준적이고 필요한 단계라고 주장한다. 저자들은 플레인 모델(오라클 없는 모델)에서 보안을 증명하는 것이 여전히 주요한 미해결 과제로 남아 있음을 명시한다.

결론적으로, 저자들은 현재의 프로토콜이 무잡음 전송(noiseless transmission)과 정밀한 타이밍을 가정하고 있지만, 이 프레임워크가 향후 견고하고 실제적인 구현을 위한 이론적 기초를 제공한다고 밝히며 마친다.