기술 요약: 인증된 삭제(Certified Deletion)를 이용한 준-양자 암호학 (Semi-Quantum Cryptography)

1. 문제 정의

본 논문은 준-양자(Semi-Quantum) 환경에서의 인증된 삭제(Certified Deletion) 문제를 다룬다. 인증된 삭제란 클라이언트가 양자 상태(quantum state)로서 암호화된 데이터를 서버에 업로드하고, 이후에 복호화 키가 유출되더라도 서버가 더 이상 해당 데이터를 복구할 수 없음을 입증하는 검증 가능한 인증서를 요청할 수 있는 기능을 의미한다.

기존의 연구들은 다양한 프리미티브(primitive)에 대해 인증된 삭제를 확립하였으나, 일반적으로 클라이언트가 초기 업로드 시 양자 능력을 갖추어야 한다는 제약이 있었다. 구체적으로는 다음과 같다:

• 업로드: 초기 양자 암호문을 준비하고 업로드하기 위해 양자 통신이 필요했다.
• 감사(Auditing): 데이터 도난 여부(침입 탐지)를 감지하기 위해 저장된 암호문에 대한 결맞음 접근(coherent access)이 필요했다.
• 검색(Retrieval): 데이터를 검색하는 동시에 서버로부터 삭제하는 과정에서, 나중에 키가 유출되었을 때 복호화될 수 있는 영구적인 클래식 복사본을 남기지 않고 수행하기가 어려웠다.

본 논문이 던지는 핵심 질문은 다음과 같다: 클라이언트가 클래식한 능력을 유지하면서도, 양자 서버에 암호화된 데이터를 업로드, 감사, 그리고 삭제하거나 검색할 수 있는가? 동시에 미래의 키 유출로부터 데이터를 보호할 수 있는가?

2. 방법론 및 핵심 기술

저자들은 임의의 의미론적 보안(semantically secure) 암격 프리미티브(예: PKE, ABE, IBE, FHE, Commitments)를 초기 업로드가 순수하게 클래식한 버전의 인증된 삭제 기능이 포함된 형태로 변환하는 **일반 컴파일러(general compiler)**를 제안한다. 이 구성은 plain model에서의 LWE(Learning With Errors) 문제에 기반한 포스트 양자 하드니스(post-quantum hardness)에 의존한다.

2.1 암호문 설계: 위상 주입 (Phase Injection)

핵심 구성은 **트랩도어 클로-프리 함수(Trapdoor Claw-Free Functions, TCFs)**와 적응형 하드코어 비트(Adaptive Hardcore Bit) 성질을 활용한다. 메시지를 숨기기 위해 preimage를 사용하고 삭제를 위해 Hadamard 기저를 사용했던 기존 방식과 달리, 본 연구는 이 관계를 역전시킨다:

• 메시지 인코딩: 메시지 $m$은 양자 상태의 **위상(phase)**에 인코딩된다.
• 인증서: TCF의 preimage들이 삭제 인증서 역할을 한다.

결과적인 암호문은 다음과 같은 양자 상태 형태를 취한다:
$$|0, x_0\rangle + (-1)^p |1, x_1\rangle$$
여기서 $p$는 메시지와 관련이 있다 ($p \oplus m$). 클래식 쉐어(share)는 $(p \oplus m, td_A)$를 포함하며, 여기서 $td_A$는 TCF 인스턴스 $A$에 대한 트랩도어이다.

복호화: 클라이언트는 Hadamard 기저에서 양자 상태를 측정하여 위상 $p$를 복구한 후, 트랩도어 $td_A$를 사용하여 preimage를 복구하고 $m$을 드러낸다.
삭제: 서버는 computational basis에서 상태를 측정하여 preimage($x_0$ 또는 $x_1$)를 얻는다. 이 측정은 위상 $p$를 파괴하여, 트랩도어가 있더라도 메시지를 복구할 수 없게 만든다.

2.2 얽힘을 통한 클래식 업로드 (Classical Upload via Entanglement)

클래식한 클라이언트가 이 양자 상태를 업로드할 수 있도록, 저자들은 두 개의 TCF 인스턴스($A$와 $B$) 및 증거 보존 지식 논증(Witness-Preserving Arguments of Knowledge)([KKR26] 기반)을 사용하는 프로토콜을 개발하였다:

1. 서버는 두 TCF의 preimage들에 대한 중첩(superposition)을 준비한다.
2. 클라이언트는 서버에게 동일한 비트 $b$를 사용하여 두 인스턴스의 preimage에 대한 지식을 증명하도록 도전한다(두 인스턴스를 얽히게 함).
3. 서버는 인스턴스 $B$의 preimage를 Hadamard 기저에서 측정한다. 이 측정은 인스턴스 $A$의 중첩에 위상 $p_B$를 주입한다.
4. 클라이언트는 위상 $p_B$를 계산하고 $(p_B \oplus m, td_A)$의 암호문을 다시 보낸다.

이 과정은 서버가 두 번째 TCF의 측정에 의해 위상이 결정되는 얽힌 상태를 보유하도록 강제하며, 이를 통해 클라이언트는 양자 통신 없이도 상태의 무결성을 검증할 수 있게 한다.

2.3 클래식 채널을 통한 정화 (Purification Over Classical Channels)

본 연구의 주요 기술적 난제는 (BB84 스타일의 증명에서 흔히 쓰이는) **정화 기반 보안 논증(purification-based security arguments)**을 클래식한 상호작전(interaction)을 통해 준비된 상태에 적응시키는 것이다. 표준 양자 증명에서는 챌린저가 중첩 상태를 준비할 수 있지만, 여기서는 클래식한 트랜스크립트(transcript)가 상태를 유일하게 결정한다.

저자들은 이를 극복하기 위해 **위상 주입 렘마(Phase Injection Lemma)**와 시뮬레이션 기법을 도입하였다:

• 구별 불가능한 추출 (Indistinguishable Extraction): 프로토콜은 witness(preimages)를 결맞게 추출하고, 위상 시프트(Z-gate)를 적용한 뒤, 추출기를 역으로 적용하여 witness를 되돌려주는 unitary extractor를 사용한다.
• 정화 (Purification): 이를 통해 보안 환원(reduction)이 트랜스크립트가 클래식함에도 불구하고 위상을 중첩(purified) 상태로 취급할 수 있게 한다. 환원은 Z-gate 적용 여부를 제어함으로써 위상의 선택을 "정화"할 수 있으며, 이를 통해 서버의 뷰(view)를 위상이 결맞게 선택된 시나리오와 구별할 수 없게 만든다.

2.4 고급 관리 기능

• 침입 부재 증명 (Proofs of No Intrusion, PoNI): [KKR26]의 일반 컴파일러를 사용하여, 비파괴적 감사를 지원하는 스킴을 제공한다. 서버는 암호문을 파괴하지 않고도 유효한 삭제 인증서를 보유하고 있음을 증명할 수 있어, 클라이언트는 데이터가 제3자에게 유출되지 않았음을 검증할 수 있다.
• 삭제를 동반한 검색 (Decryption with Deletion): 클라이언트가 메시지를 검색하는 동시에 서버로부터 이를 삭제하는 인터랙티브 프로토콜을 제시한다. 이는 암호문을 (새로운 위상을 더해) **재무작위화(rerandomizing)**한 후 클래식한 형태로 변환함으로써 달성되며, 이를 통해 서버가 나중에 복호화 키를 알게 되더라도 원래의 메시지는 숨겨진 상태로 남게 된다.

3. 주요 결과

본 논문은 LWE의 포스트 양자 하드니스를 가정하여 다음과 같은 주요 결과를 확립한다:

1. 일반 컴파일러: 임의의 프리미티브 $X \in \{\text{Secret Sharing, PKE, ABE, IBE, Commitments, FHE}\}$를 공개 검증 가능한 인증된 삭제와 클래식 업로드 기능을 갖춘 준-양자 버전으로 변환하는 컴파일러가 존재한다.
2. 공개 검증 가능성: 삭제 인증서는 클래식하며 누구나 검증할 수 있어, 비파괴적 감사가 가능하다.
3. 클래식 검색: 클라이언트는 메시지를 검색하는 동시에 서버가 데이터를 삭제하도록 보장할 수 있으며, 이는 검색된 데이터에 대한 미래의 키 유출 공격을 방지한다.
4. 구체적 구성:
   • 준-양자 비밀 공유 (Semi-Quantum Secret Sharing): 인증된 삭제가 포함된 2-out-of-2 스킴.
   • 공개 키 암호화 (PKE, ABE, IBE): 암호문은 양자 상태이지만 업로드는 클래식한 방식의 스킴들.
   • 커밋먼트 (Commitments): 계산적 은닉(computational hiding)과 붕괴 결합(collapse binding)을 지원.
   • 완전 동형 암호 (FHE): 양자 암호문에 대한 회로의 결맞은 평가(coherent evaluation)를 지원하며 인증된 삭제가 가능함.

4. 의의 및 주장

저자들은 본 연구의 의의를 다음과 같이 주장한다:

• 간극 해소: 양자 인프라를 요구하지 않고도 완전한 클래식 클라이언트가 양자 암호화된 데이터를 관리(업로드, 감사, 삭제/검색)할 수 있게 하는 미해결 문제를 해결하였다.
• 새로운 기법: 주요 기술적 기여는 클래식한 상호작용을 통해 준비된 상태에 정화 기반 보안 논증을 적용하는 방법론이다. 이 기법은 실제 실행 시 트랜스크립트가 상태를 유일하게 결정함에도 불구하고, 보안 환원이 상태의 "정화된" 뷰를 유지할 수 있게 한다. 저자들은 이 기법이 다른 양자 암호 구성에서도 독립적인 가치가 있을 것이라고 언급한다.
• 광범위한 적용성: 본 컴파일러는 범용적이어서, 특정 인증된 삭제 접근 방식(예: 수신자의 non-committing encryption을 요구하는 방식)과 호환되지 않았던 ABE나 FHE와 같은 고급 암호 체계에도 적용 가능하다.
• 완만한 가정: 본 구성은 LWE의 포스트 양자 하드니스만을 기반으로 하며, 이전의 클래식 업로드 시도들에서 필요했던 extractable witness encryption이나 one-shot signature와 같은 복잡한 프리미티브를 피한다.

저자들은 본 기술이 인증된 삭제와 관리 기능을 달的是 하지만, 원격 상태 준비(Remote State Preparation, RSP)의 엄밀한 의미에서의 **시뮬레이션 보안성(simulation-security)**이나 **검증 가능성(verifiability)**을 달성하는 것은 아니라고 명시한다. 즉, 공격자가 TCF를 클래식하게 평가할 수 있기 때문이다. 그러나 인증된 삭제라는 특정 목표를 위해서는 제공된 구별 불가능성 보장이 충분하다.