기술 요약: 무조건적 복제 불가능 암호화를 향하여

1. 문제 정의

복제 불가능 암호화(Uncloneable encryption)는 고전적인 메시지를 양자 암호문으로 암호화하도록 설계된 양자 암호 프리미티브로, 두 명의 양자 공격자가 복호화 키와 암호문으로부터 유도된 양자 부가 정보(side-information)를 가졌을 때, 동시에 메시지를 복호화할 수 없도록 한다. QROM(Quantum Random Oracle Model) 및 특정 계산적 가정(예: 난해화/obfuscation) 하에서 이러한 속성을 달성하는 스킴들이 제안되어 왔으나, 평면 모델(plain model)에서 무조건적으로 안전한(unconditionally secure) 복제 불가능 암호화 스킴의 존재 여부는 여전히 미해결 과제로 남아 있다.

이 핵심 과제의 중심에는 "복제 불가능 비트(uncloneable bit)" 문제가 있다. 이는 단일 클래식 비트($m \in \{0, 1\}$)를 암호화하는 가장 단순한 사례이다. 이 단순함에도 불구하고, 계산적 가정 없이 복제 불가능-구별 불가능성(uncloneable-indistinguishability) 보안을 만족하는 스킴은 아직 증명되지 않았다. 이 스킴의 보안은 해적(P)이 양자 암호문을 밥(B)과 찰리(C)를 위한 두 개의 레지스터로 분할하려고 시도하는 "노-클로닝 게임(no-cloning game)"에 의해 정의된다. B와 C는 각각 비밀 키를 보유하며, 원래의 비트를 맞출 확률은 $1/2 + \text{negl}(\lambda)$ (강한 보안) 또는 $1/2 + f(\lambda)$ (단, $f(\lambda) \to 0$) (약한 보안)에 의해 제한된다.

2. 방법론

저자들은 클리리포드 대수(Clifford algebras)와 쌍으로 반교환하는 파울리 문자열(pairwise anti-commuting Pauli strings)의 구조를 기반으로 한 후보 스킴을 제안한다.

후보 스킴

• 키 생성: 키 $k$는 크기가 $K = 2^\lambda$ (짝수 $\lambda$인 경우) 또는 $K = 2^\lambda + 1$ (홀수 $\lambda$인 경우)인 집합에서 균등하게 샘플링된다.
• 암호화: 메시지 $m \in \{0, 1\}$는 특정 헤르미션 유니터리 $\Gamma_k$의 고유값 $(-1)^m$에 대한 정규화된 투영체(projector)인 양자 상태 $\rho_{m,k}$로 인코딩된다. 집합 $\{\Gamma_1, \dots, \Gamma_K\}$는 힐베르트 공간 차원 $d = 2^\lambda$에서 작용하는 쌍으로 반교환하는 연산자(예: 특정 파울리 문자열)들로 구성된다.
  $$\rho_{m,k} = \frac{I + (-1)^m \Gamma_k}{2}$$
• 복호화: 수신자는 키 $k$에 대응하는 $\Gamma_k$의 고유 기저(eigenbasis)에서 상태를 측정한다.

분석 프레임워크

보안 분석은 특정 연산자 $W_K$의 연산자 노름(operator norm)에 대한 최적화 문제로 환원된다. 승리 확률은 다음과 같이 상한이 결정된다:
$$\Pr[\text{win}] \leq \frac{1}{2} + \frac{1}{2K} \sup_{\{U_k\}} \left\| \sum_{k=1}^K \left( \Gamma_k \otimes (U_k \otimes I + I \otimes U_k) + I \otimes U_k \otimes U_k \right) \right\|_{\text{op}}$$
여기서 $U_k$는 공격자들의 측정 전략을 나타내는 헤르미션 유니터리이다.

저자들은 모든 쌍으로 반교환하는 헤르미션 유니터리 $\Gamma_k$와 모든 헤르미션 유니터리 $U_k$에 대하여 다음이 성립한다고 가정하는 Conjecture 1을 제안한다:
$$\left\| \sum_{k=1}^K \left( \Gamma_k \otimes (U_k \otimes I + I \otimes U_k) + I \otimes U_k \otimes U_k \right) \right\|_{\text{op}} \leq K + 2\sqrt{K}$$
이것이 참이라면, 이는 승리 확률의 상한이 $1/2 + \frac{1}{2\sqrt{K}}$임을 의미하며, 약한 보안(weak security)을 입증한다.

이 추측을 검증하기 위해 저자들은 다음을 활용한다:

1. 합-제곱(Sum-of-Squares, SoS) 분해: 연산자 $P_K = (K + 2\sqrt{K})I - W_K$의 비음성(non-negativity)을 증명하기 위해 명시적인 다항식 인증서를 구성한다.
2. NPA 계층(Navascués-Pironio-Acín): SoS의 쌍대(dual) 관계에 있는 첫 번째 및 두 번째 단계의 NPA 계층을 사용하여, 연산자 노름의 상한을 제공하는 준정부호 프로그래밍(SDP)을 정식화한다.
3. 시소(Seesaw, 교대 최적화): 상태 벡터와 측정 연산자에 대해 반복적으로 최적화함으로써 $W_K$의 최대 고유값에 대한 하한을 찾는 휴리스틱 수치 알고리즘을 사용한다.

3. 주요 기여 및 결과

분석적 증명

• 작은 $K$에 대한 검증: 저자들은 $K \leq 7$인 경우에 대해 Conjecture 1을 확인하는 명시적인 SoS 분해와 분석적 증명을 제공한다.
• 점근적 상한: NPA 계층의 첫 번째 단계의 분석적 해법을 사용하여, $K > 7$인 경우에 대한 점근적 상한을 도출한다. 이 상한은 $5/8 + \frac{1}{2(K-2)} - \frac{1}{4K}$이며, $K \to \infty$일 때 $5/8$로 수렴한다. 이는 자명한 상한인 1보다 유의미한 개선이다.

수치적 증거

• NPA 레벨 2: 저자들은 분석을 두 번째 단계의 NPA 계층으로 확장하여, 그 결과로 나오는 SDP를 수치적으로 해결한다. 이를 통해 $K \leq 17$인 경우에 대해 추측이 성립함을 확인한다.
• 최선의 알려진 상한: $K=35$인 경우, NPA 레벨 2 최적화는 약 0.5980의 수치적 상한을 산출한다. 저자들은 이것이 자신들이 아는 한 해당 프리미티브에 대한 최선의 무조건적 상한이라고 밝힌다.
• Seesaw 방법: $K=18$인 경우, 교대 최적화 알고리즘은 추측을 위반하는 사례를 발견하지 못했으며, 이는 추측이 더 큰 $K$에 대해서도 성립한다는 휴리스틱한 증거를 제공한다.

구별 불가능성(Indistinguishability)

본 논문은 후보 스킴이 완화된 형태의 구별 불가능성 보안을 만족함을 증명한다. 구체적으로, 무작위 비트와 고정된 비트 사이의 암호문을 공격자가 구별할 확률은 $O(1/\sqrt{K})$의 속도로 $1/2$에 수렴한다.

4. 의의 및 주장

본 논문은 양자 암호학의 근본적인 미해결 과제를 다루며, 무조건적 복제 불가능 암호화를 위한 후보 스킴을 제시한다. 저자들은 모든 $K$에 대해 추측을 증명했다고 주장하는 대신, 다음을 제공한다:

1. 강력한 증거: 작은 파라미터에 대한 엄밀한 분석적 증명과 $K \leq 17$(및 $K=18$에 대한 휴리스틱 체크)까지의 광범-한 수치적 검증의 결합.
2. 개선된 상한: $5/8$의 점근적 상한과 $\sim 0.5980$의 수치적 상한을 도출하였으며, 이는 해당 프리미티브에 대해 알려진 가장 타이트한 무조건적 상한이다.
3. 향후 연구를 위한 토대: 본 연구는 (클리포드 대수를 기반으로 한) 연산자 노름 최적화 프레임워크를 구축함으로써, QROM이나 계산적 가정의 한계를 넘어 무조건적 복제 불가능성을 조사하는 기초를 마련하였다.

저자들은 임의의 큰 $K$에 대해 추측을 증명하는 것이 여전히 미해결 과제로 남아 있으며, 이것이 평면 모델에서 최초의 무조건적 복제 불가능 암호화 증명이 될 것임을 명시한다. 또한, 본 스킴이 이전 연구들에서 정의된 "강한" 보안(지수적 감소)보다는 "약한" 보안(이차적 수렴)을 달mesi 한다는 점을 인정하며, 강력한 보안을 갖춘 스킴의 구축을 향후 목표로 남겨두었다.