기술 요약: 도청자 불투명 원격 상태 준비(Eavesdropper-Blind Remote State Preparation) 및 이를 활용한 양자 공개키 암호화

1. 문제 정의

원격 상태 준비(Remote State Preparation, RSP)는 고전적인 클라이언트가 고전적 통신만을 사용하여 특정 양자 상태를 준비하도록 양자 서버에 지시할 수 있게 하는 양자 암호학의 근본적인 프리미티브(primitive)이다. 기존의 RSP 구성은 위임된 계산(delegated computation), 양자성 증명(proofs of quantumness), 양자 공개키 암호화(QPKE)와 같은 응용 분야를 지원하는 양자-고전 통신(QCCC) 모델의 핵심이다.

그러나 현재의 RSP 프로토콜은 두 가지 중요한 한계에 직면해 있다:

1. 강한 가정: 알려진 모든 구성은 "트랩도어(trapdoor)" 암호학적 프리미티브, 특히 트랩도어 클로-프리 함수(Trapdoor Claw-Free Functions, TCF)에 의존한다. 이러한 트랩도어에 대한 의존성은 주요한 미해결 과제인데, 암호학적 가정을 (예: 일방향 함수나 대수적 구조로) 완화하는 것이 암호학의 주요 목표 중 하나이기 때문이다.
2. 보안 오버헤드: 표준 RSP 정의는 "악의적 서버 불투명성(malicious-server blindness)"을 요구하며, 이는 서버가 프로토콜에서 임의로 벗어나더라도 준비된 상태에 대해 아무것도 알 수 없음을 보장한다. 이러한 강력한 보안 개념은 종종 복잡한 프로토콜과 특정한 가정을 필요로 한다.

본 논문은 더 약한 형태의 RSP가 유용한 암호학적 응용을 여전히 지원할 수 있는지, 그리고 트랩도어가 없는 더 약한 가정으로부터 구성을 허용할 수 있는지를 조사한다. 구체적으로 저자들은 다음과 같은 질문을 던진다:

• 유용한 응용 프로그램들이 완화된 보안 보증을 가진 RSP 프로토콜으로부터 도출될 수 있는가?
• 그러한 더 약한 RSP를 트랩도어 없이 구축할 수 있는가?

2. 방법론 및 정의

도청자 불투명 원격 상태 준비 (Eavesdropper-Blind Remote State Preparation, EB-RSP)

저자들은 **도청자 불투명 원격 상태 준비(EB-RSP)**라는 새로운 프리미티브를 도입한다. 이는 표준 불투명성 요구 사항을 완화한다:

• 표준 불투명성 (Standard Blindness): 양자 증명자(서버)는 악의적일지라도 준비된 상태에 대해 아무것도 알 수 없다.
• EB-RSP 불투명성 (EB-RSP Blindness): 이 프로토콜은 검증자(verifier)와 정직한 증명자 사이의 정직한 상호작용을 관찰하는 외부 도청자에게만 불투명하다. 정직한 증명자 자체는 자신이 준비하는 상태를 알 수 있도록 허용된다.

공식 정의: EB-RSP 프로토콜은 고전 검증자 $V$와 양자 증명자 $P$를 포함한다.

• 정확성 (Correctness): $P$는 상태 $|+\theta\rangle = \frac{1}{\sqrt{2}}(|0\rangle + e^{i\theta}|1\rangle)$를 보유하며, 여기서 $\theta \in \Theta_N = \{k \cdot \frac{2\pi}{N} \mid 0 \le k \le N-1\}$이고, $V$는 클래식 설명 $\theta$를 보유한다.
• 도청자 불투명성 (Eavesdropper Blindness): 정직한 실행의 클래식 트랜스크립트(transcript)가 주어졌을 때, 양자 다항 시간(QPT) 도청자는 실제 $\theta$를 $\Theta_N$에서 균등하게 샘플링된 값과 구별할 수 없다.

저자들은 특히 두 메시지 EB-RSP(검증자로부터 하나의 메시지, 증명자로부터 하나의 메시지) 프로토콜에 집중하는데, 이 구조는 그들의 주요 응용 분야를 위해 충분하기 때문이다.

암호학적 가정

본 논문은 **일방향 군 작용(One-Way Group Actions, OWGA)**으로부터 EB-RSP를 구성한다.

• 군 작용 (Group Action): 군 작용 공리를 만족하는 사상 $\star: G \times X \to X$.
• 자유 (Free/Semiregular): 작용이 $g \star x = x$일 때 $g = 1$을 의미하면 작용은 자유롭다.
• 일방향성 (One-Wayness): $(x, s \star x)$가 주어졌을 때, QPT 공격자가 $s' \star x = s \star x$를 만족하는 $s'$를 찾는 것은 계산적으로 어렵다.
• 주요 차이점: TCF와 달리, OWGA는 검증자가 함수를 역산할 수 있는 트랩도어를 본질적으로 제공하지 않는다. 이 구성은 미지의 파라미터를 상쇄하기 위한 군 작용의 대수적 성질에 의존한다.

3. 주요 기여 및 결과

A. OWGA로부터의 두 메시지 EB-RSP 구축

저자들은 $G = \mathbb{Z}_p^\lambda$ (여기서 $p$는 소수)인 자유로운 OWGA에 기반한 구체적인 두 메시지 EB-RSP 프로토콜을 제시한다.

프로토콜 개요:

1. 검증자 ($V$): $x_0 \in X$와 $r, s \in G$를 샘플링한다. $x_1 = (-s) \star x_0$를 계산한다. $P$에게 $(x_0, x_1, r)$을 보낸다.
2. 증명자 ($P$):
   • $b \in \{0,1\}$ 및 $g \in G$에 대한 중첩(superposition)을 준비한다.
   • $g \star x_b$를 중첩 상태로 계산한다.
   • 출력 레지스터를 측정하여, (작용의 자유성 덕분에) "클로(claw)" 상태 $|0, g_0\rangle + |1, g_0 + s\rangle$로 붕괴시킨다.
   • $r$과의 내적을 계산하고 레지스터에 QFT를 적용한다.
   • 결과를 얻기 위해 $g$와 $z$를 측정하고 이를 $V$에게 보낸다.
   • $\theta = \langle s, z \cdot r + g \rangle \cdot \frac{2\pi}{p}$인 상태 $|+\theta\rangle$를 출력한다.
3. 검증자 ($V$): 자신의 비밀 $s$와 수신된 $g, z$를 사용하여 $\theta$를 계산한다.

구성의 의의:

• 트랩도어-프리 (Trapdoor-Free): 검증자는 $\theta$를 계산하기 위해 트랩도어가 필요하지 않다. 대신, 군 작용의 대수적 구조가 미지의 파라미터(예: $g_0$)가 QFT 측정 중에 상쇄되도록 보장하며, 검증자가 알고 있는 항들만 남게 한다.
• 보안성: 보안은 **양자 골드라이히-레빈 정리(Quantum Goldreich-Levin Theorem)**에 의존한다. $g$는 균등하게 무작위이며 공격자의 뷰와 독립적이므로, 항 $\langle s, z \cdot r + g \rangle$은 균등 분포와 계산적으로 구별 불가능하며, 따라서 $\theta$를 도청자로부터 숨긴다.
• 일반화: 이 프로토콜은 병렬 서브루틴을 실행함으로써 합성 $N$ (서로 다른 소수들의 곱)으로 확장될 수 있다.

B. EB-RSP로부터의 QPKE 구축

저자들은 **두 메시지 EB-RSP가 클래식 공개키와 양자 암호문을 가진 양자 공개키 암호화(QPKE)**를 구축하는 데 충분함을 입증한다.

구성 (Black-Box):

• KeyGen: EB-RSP 설정을 $n$번 실행한다. 공개키 $pk$는 검증자의 첫 번째 메시지들로 구성되며, 비밀키$sk$는 검증자의 내부 상태들로 구성된다.
• Enc: 비트 $b$를 암호화하기 위해, 암호화자(증명자 역할)는 각 $pk$인스턴스에 대해 EB-RSP 계산을 실행하여 상태$|+\theta_i\rangle$들을 생성한다. 그 후, 위상을 바꾸기 위해 유니터리$U_b = R_z(b \cdot \lfloor N/2 \rfloor \cdot \frac{2\pi}{N})$를 적용한다. 암호문은 변환된 상태들과 증명자의 메시지들이다.
• Dec: 복호화자는 $sk$를 사용하여$\theta_i$를 복구하고, 위상을 제거하기 위해$R_z(-\theta_i)$를 적용한 후, 하다마르(Hadamard) 기저에서 측정하여 $b$를 복구한다.

보안성: QPKE의 IND-CPA 보안은 근저에 있는 EB-RSP의 도청자 불투명성에 직접적으로 의존한다. 도청자는 무작위 각도 $\theta$를 균등 분포와 구별할 수 없으므로, 암호화된 상태($\theta + b \cdot \text{shift}$에 의존함)를 무작위 상태와 구별할 수 없다.

C. 기존 TCF 기반 프로토콜의 적응

본 논문은 일반적인 TCF(예: [BKM+25])에 기반한 기존 RSP 구성들이 두 메시지 EB-RSP 모델로 적응될 수 있음을 관찰한다. 메시지를 병합하고, 정직한 실행에서 TCF 기반 RSP의 "부산물 비트(byproduct bit)"가 각도와 독립적이라는 점을 이용하면, 이러한 프로토콜들 또한 도청자 불투명성을 만족한다. 이는 TCF로부터의 또 다른 QPKE 구성을 제공한다.

4. 의의 및 주장

본 논문은 다음과 같은 의의를 주장한다:

1. 최초의 트랩도어-프리 RSP형 프리미티브: 저자들이 알고 있는 바로는, 유용한 암호학적 응용을 가지면서 트랩도어 프리미티브에 의존하지 않는 최초의 RSP 유형 프리미티브이다. 이는 대수적 가정(OWGAs)이 특정 RSP 작업을 위해 트랩도어 가정을 대체할 수 있음을 보여준다.
2. 더 약한 보안, 동일한 효용: 본 연구는 도청자 불투명성(표준적인 악의적 서버 불투명성보다 약한 보안 개념)이 클래식 공개키를 가진 QPKE를 구축하는 데 충분함을 입증했다. 이는 표준 RSP의 강력한 보안 요구 사항이 특정 응용 분야에서는 불필요할 수 있으며, 잠재적으로 더 단순한 프로토콜과 더 약한 가정을 허용할 수 있음을 시사한다.
3. 모듈형 접근 방식: 저자들은 두 메시지 EB-RSP에서 QPKE로의 일반적인 블랙박스 리덕션(reduction)을 제공한다. 이는 상태 준비 프리미티브와 그 응용 분야인 암호화를 분리하여, 두 구성 요소 중 어느 쪽에서도 모듈식 개선을 가능하게 한다.
4. 기초적 단계: 이 구성은 특정 군 작용에 국한되어 있으며 아직 트랩도어 없는 검증 가능한 RSP나 악의적 서버에 대한 RSP를 달성하지는 못하지만, 양자 암호 체계의 근간이 되는 암호학적 가정을 완화하기 위한 "첫 걸음"을 제공한다.

한계 및 열린 질문:

• 현재 구성은 $N$이 소수이거나 서로 다른 소수들의 곱인 경우에 작동한다. 소수의 거듭제곱에 대한 QFT의 정확성 문제로 인해 소수의 거듭제곱으로 확장하는 것은 아직 불분명하다.
• 본 논문은 트랩도어 없는 가정으로부터 검증 가능한 RSP나 악의적 서버에 대한 불투명한 RSP를 구축한다고 주장하지 않으며, 이를 명시적으로 향후 연구 과제로 남겨두었다.
• 결과물인 QPKE는 (일부 TCF 기반 구성과 달리) 양자 암호문을 생성한다.

요약하자면, 본 논문은 더 약한 RSP 개념(EB-RSP)에 대한 연구를 개시하고, 이를 트랩도어 없는 일방향 군 작용으로부터 구축하며, QPKE를 구축하기 위한 충분성을 증명함으로써 양자 암호학에서 사용할 수 있는 가정의 지평을 넓힌다.