당신이 친구에게 특수한 양자 잠금 상자를 이용해 비밀 메시지를 보내려 한다고 상상해 보세요. 양자 물리학의 세계에는 기이한 규칙이 하나 있습니다. 원본을 파괴하지 않고는 양자 상태 (특정 원자 배열과 같은) 를 완벽하게 복제할 수 없다는 것입니다. 이를 복제 불가 정리 (No-Cloning Theorem) 라고 부릅니다.

이 논문은 복제 불가 암호화 (Uncloneable Encryption) 라는 새로운 유형의 '양자 잠금 상자'에 관한 것입니다. 목표는 해커가 잠긴 상자를 훔쳐도 나중에 열어보기 위해 완벽한 복제본을 만들 수 없는 시스템을 만드는 것입니다. 만약 그들이 복제를 시도한다면, 복제본은 무효화되고 메시지는 손실됩니다.

저자들은 매우 구체적인 질문을 던집니다: 단 하나의 메시지가 아닌, 여러 메시지를 위해 이러한 초보안 상자가 작동하도록 하려면 수학 및 물리학의 미래에 대해 얼마나 적은 가정을 해야 할까요?

다음은 간단한 비유를 사용한 그들의 발견 사항에 대한 해설입니다:

1. 출발점: '복제 불가 비트'

마법 동전이 하나 있다고 상상해 보세요. 동전을 던지면 결과 (앞면 또는 뒷면) 가 나옵니다. 이 논문은 이 단일 동전을 상자에 잠그는 방법이 이미 존재한다고 가정합니다. 즉, 아무도 상자를 복제할 수 없으며, 복제를 시도하면 복제본은 무용지물이 됩니다.

문제: 이 마법은 오직 하나의 동전 (단일 메시지) 에만 작동합니다. 우리는 보안이 무너지지 않은 채로 같은 비밀 키를 사용하여 여러 개의 메시지 (예: 온전한 소설 전체) 를 보내고자 합니다.
목표: 저자들은 오직 이 하나의 마법 동전과 다른 표준 도구들만을 사용하여 '다중 사용'이 가능한 보안 시스템을 구축하고자 합니다.

2. 첫 번째 주요 발견: '범용 어댑터'

저자들은 그 단일 마법 동전을 가져와 긴 메시지 (예: 온전한 책) 를 여러 번 암호화할 수 있는 시스템으로 변환하는 방법을 발견했습니다.

비유: 마법 동전을 작고 fragile 한 씨앗이라고 생각하세요. 저자들은 그 씨앗을 가져와 거대하고 재사용 가능한 나무를 키워내는 '온실 (컴파일러)'을 구축했습니다.
단점: 이 나무의 첫 번째 버전에서, 상자를 잠그는 사람은 상자를 열는 사람과 약간 다른 키가 필요했습니다. 문을 잠그는 마스터 키는 있지만, 여는 것은 더 간단하고 다른 키를 사용해야 하는 것과 같습니다. 이는 다소 불편합니다.
결과: 그들은 마법 동전과 재사용 가능한 표준 잠금 장치 (존재한다고 가정) 가 있다면, 오늘날 우리가 가진 최고의 표준 잠금 장치만큼이나 안전한 시스템을 구축할 수 있음을 증명했습니다. 그보다 더 나은 것은 불가능하므로, 이 결과는 'tight(완벽하게 효율적)'합니다.

3. 두 번째 주요 발견: '일반적'이고 '동일한' 시스템 만들기

저자들은 시스템을 더 개선할 수 있음을 깨달았지만, 이를 위해 한 가지 추가 재료가 필요했습니다: 의사 난수 유니타리 (Pseudorandom Unitaries).

그게 무엇인가요? 인간에게는 완전히 무작위로 보이지만 실제로는 특정 비밀 공식에 의해 생성되는 숫자를 생성하는 기계를 상상해 보세요. 양자 세계에서는 이 기계가 데이터를 무작위처럼 보이는 혼란으로 뒤섞지만 실제로는 통제된 방식으로 작동합니다.
업그레이드: 이 추가 기계를 통해 그들은 '서로 다른 키' 문제를 해결했습니다. 이제 상자를 잠그는 사람과 여는 사람은 정확히 같은 키를 사용합니다. 이를 '일반 형태 (Normal Form)'라고 합니다.
'동일한 복제본' 보너스: 일반적으로 메시지를 보낼 때, 양자 상자는 보낼 때마다 약간 다르게 보일 수 있습니다 (흐린 사진과 선명한 사진과 같이). 저자들은 새로운 방법으로 동일한 메시지를 보낼 때마다 상자가 이전 것과 동일하게 보임을 보여주었습니다.
- 왜 중요한가요? '복제 불가' 게임에서 해커는 상자의 $t$ 개의 복제본을 받고 $t'$ 개의 복제본을 만들려고 시도합니다.
- 표준 버전: 해커는 $t$ 개의 약간 다른 흐린 사진을 받습니다.
- 동일 버전: 해커는 $t$ 개의 완벽한 동일한 사진을 받습니다.
- 저자들은 흐린 사진을 복제할 수 없다면, 완벽한 동일한 사진은 더더욱 복제할 수 없음을 증명했습니다. 이는 보안을 훨씬 더 강력하고 현실적으로 만듭니다.

4. '마이크로크립트 (Microcrypt)' 세계

이 논문은 '마이크로크립트' 라는 개념을 언급합니다.

비유: 컴퓨터가 엄청나게 강력하여 어떤 수학 퍼즐도 즉시 해결할 수 있는 ($P=NP $) 세상을 상상해 보세요. 현재의 세계에서는 비밀을 안전하게 지키기 위해 수학 퍼즐을 푸는 것이 어렵다는 점에 의존합니다. 만약$ P=NP$라면, 대부분의 현재 잠금 장치는 무너질 것입니다.
주장: 저자들은 수학 퍼즐이 쉬운 이 '무너진' 세계에서도 그들의 새로운 복제 불가 암호화 시스템이 여전히 작동할 수 있음을 보여줍니다. 이는 어려운 수학 퍼즐이 아니라 양자 물리학의 기이한 법칙 (복제 불가 비트) 과 '무작위처럼 보이는' 기계 (의사 난수 유니타리) 에 의존합니다.
교훈: 수학 세계가 붕괴되더라도, 이 양자 보안은 여전히 견딜 수 있을지도 모릅니다.

'레시피' 요약

이 논문은 궁극적인 양자 잠금 상자를 구축하는 레시피를 제공합니다:

재료 A: '복제 불가 비트' (단일 데이터 비트를 위한 일회용 양자 잠금 장치).
재료 B: 표준 재사용 잠금 장치 (일반 암호화를 위한).
- 결과: 긴 메시지를 위한 재사용 가능한 잠금 상자를 얻지만, 잠금 키와 열기 키는 다릅니다.
재료 C 추가: 의사 난수 유니타리 (가짜 무작위 양자 혼란을 생성하는 기계).
- 결과: 잠금 키와 열기 키가 동일하고, 메시지를 보낼 때마다 상자가 이전 것과 동일하게 보이는 재사용 가능한 잠금 상자를 얻습니다. 이는 해킹을 극도로 어렵게 만듭니다.

간단히 말해: 저자들은 이러한 초보안 양자 시스템을 구축하기 위해 불가능한 것을 가정할 필요가 없음을 증명했습니다. 우리는 단지 약간의 양자 마법 (복제 불가 비트) 과 몇 가지 표준 도구만 있으면, 나머지 세계의 수학 보안이 실패하더라도 안전한 시스템을 구축할 수 있습니다.

기술적 요약: 마이크로크립트에서 복제 불가능 암호화의 증폭에 대한 주석

문제 제기

복제 불가능 암호화 (UE) 는 양자 정보의 복제 불가능성과 암호화의 의미론적 보안을 결합한 양자 암호학적 원시적 요소입니다. 일회성 안전한 UE(복제 불가능 비트) 는 정보이론적으로 존재할 것으로 믿어지지만, 재사용 가능 (다중 회) 보안을 달성하려면 암호학적 가정이 필요합니다.

이전 연구는 "마이크로크립트"(P=NP 일지라도 안전한 비구조적 양자 암호학의 세계) 에서 재사용 가능한 UE 가 존재함을 입증했으나, 이러한 결과들은 구체적 가정 대신 이상화된 모델(특히 Haar 무작위 오라클) 에 의존했습니다. 또한, 기존 구성들은 종종 "정규 형태"(암호화 키와 복호화 키가 동일한 경우) 나 "동일 복사 보안"(적극자가 독립적인 혼합 상태가 아닌 동일한 순수 상태의 여러 복사본을 받는 경우) 을 갖추지 못했습니다.

본 주석은 재사용 가능한 UE 에 필요한 구체적 가정을 최소화하는 것을 목표로 합니다. 구체적으로, 정보이론적 $t \to t'$ 복제 불가능 비트(적극자가 $t$ 개의 복사본을 복제하여 $t'$ 개의 유효한 복호화를 생성할 수 없는 1 비트 메시지에 대한 일회성 안전한 체계) 의 존재가 임의 길이 메시지에 대한 재사용 가능한 UE 를 구성하기에 충분한지, 그리고 어떤 추가 가정 하에 더 강력한 보안 개념을 달성할 수 있는지 조사합니다.

방법론

저자들은 약한 원시적 요소를 더 강력한 재사용 가능한 UE 체계로 변환하기 위해 두 가지 주요 컴파일러 기법을 사용합니다:

1. 분해 가능 양자 무작위 인코딩 (DQRE) 을 통한 평문 확장

이 논문은 [HKNY24] 에 의해 일회성 UE 를 위해 원래 소개된 컴파일러를 적용합니다.

메커니즘: 이 구성은 메시지 $m$ 을 출력하는 회로 $C[m]$ 을 인코딩하기 위해 DQRE 를 사용합니다. 암호화 키는 일회성 복제 불가능 키 ($udk$) 와 일련의 재사용 가능한 대칭 키로 구성됩니다.
핵심 혁신: 재사용성을 방해하던 일회성 패드에 의존했던 이전 iterations 과 달리, 이 구성은 일회성 패드를 재사용 가능한 IND-CPA 대칭 키 암호화 (SKE) 체계로 대체합니다.
보안 논증: 보안은 DQRE 의 구별 불가능성에 의존합니다. $m_0$ 과 $m_1$ 의 암호화 간 구별이 근본적인 DQRE 라벨의 구별로 축소되고, 이는 다시 복제 불가능 비트 게임의 보안으로 축소되도록 도전 암호문들이 구성됩니다.
정규 형태: "정규 형태"(동일한 암호화/복호화 키) 를 달성하기 위해, 저자들은 기반 재사용 가능한 SKE 가 의사 난수(암호문이 최대 혼합 상태와 구별 불가능함) 일 경우, 암호화 프로토콜이 "사용되지 않는" 키 비트에 대한 특정 값을 암호화하는 대신 무작위 문자열을 샘플링할 수 있음을 관찰합니다. 이는 사용하지 않는 비트에 대한 복호화 키를 적대자에게 공개할 필요성을 제거합니다.

2. 정화 채널을 통한 동일 복사 보안

이 논문은 표준 UE 보안(적극자가 독립적인 혼합 상태를 받음) 과 동일 복사 보안(적극자가 동일한 순수 상태의 여러 복사본을 받음) 사이의 격차를 해소합니다.

메커니즘: 양자 학습 이론의 최근 결과 ([TWZ26, PSTW25, GML26]) 와 복사 보호에 대한 이전 연구 ([AG25, C¸GK+25]) 에 기반하여, 저자들은 정화 채널을 활용합니다.
가정 축소: 이전 연구들은 혼합 상태의 $t$ 개 복사본을 정화 앙상블의 $t$ 개 복사본으로 대체하는 시뮬레이터를 구성하기 위해 일방향 함수 (OWF) 를 필요로 했습니다. 저자들은 **의사 난수 유니타리 (PRU)**가 이 시뮬레이터를 구현하기에 충분함을 보여줍니다.
구성: 암호화 알고리즘은 PRU 키 $k$ 를 무작위성으로 받습니다. 이는 암호문을 정화하고 정화 레지스터에 유니타리 $U_k$ 를 적용합니다. 결과 상태는 원래 암호문에 적용된 이상적인 정화 채널의 출력과 구별 불가능합니다.

주요 기여 및 결과

1. 재사용 가능한 UE 와 재사용 가능한 SKE 의 동등성

이 논문은 $t \to t'$ 복제 불가능 비트의 존재와 재사용 가능한 SKE 의 결합이 임의 길이 메시지에 대한 재사용 가능한 $t \to t'$ UE 를 구성하기에 충분함을 입증합니다.

정리 1.1 (비공식): $t \to t'$ 복제 불가능 비트와 재사용 가능한 SKE 가 존재한다면, 재사용 가능한 $t \to t'$ UE 가 존재합니다.
경직성: 재사용 가능한 UE 는 재사용 가능한 SKE 를 함축하므로, 이 결과는 경직적입니다. 즉, 복제 불가능 비트가 주어지면 재사용 가능한 UE 는 재사용 가능한 SKE 와 동등합니다.

2. 정규 형태 및 동일 복사 보안

저자들은 약간 더 강력하지만 표준적인 마이크로크립트 가정 하에 더 강력한 보안 개념이 달성 가능함을 보여줍니다.

정리 1.2 (비공식): $t \to t'$ 복제 불가능 비트와 **의사 난수 유니타리 (PRU)**가 존재한다면, 정규 형태를 가지며 동일 복사 보안을 갖는 재사용 가능한 $t \to t'$ UE 체계가 존재합니다.
계 1.8: 이 결과는 평문 확장 컴파일러 (정규 형태를 위해 PRU 기반 SKE 사용) 와 정화 채널 변환 (동일 복사 보안을 위해 PRU 사용) 을 결합하여 유도됩니다.

3. 보안 게임의 일반화

이 연구는 적대자가 $t$ 개의 도전 암호문을 $t'$ 개의 유효한 복호화로 복제하려는 시도를 분석하는 통합된 프레임워크를 제공함으로써 표준 $1 \to 2$ 복제 게임을 임의의 $t \to t'$ 매개변수로 일반화합니다.

중요성 및 주장

이 논문은 재사용 가능한 복제 불가능 암호화의 기반이 되는 가정에 대해 더 명확하고 체계적인 그림을 제공한다고 주장합니다. 그 주요 중요성은 다음과 같습니다:

가정 최소화: 재사용 가능한 UE 가 공개키 암호화나 특정 대수적 구조와 같은 복잡하고 구조화된 원시적 요소를 필요로 하지 않으며, 복제 불가능 비트라는 매우 약한 가정과 표준 마이크로크립트 원시적 요소 (SKE 및 PRU) 로부터 구축될 수 있음을 입증합니다.
마이크로크립트에서의 구체적 실현: 재사용 가능한 UE 의 존재를 이상화된 모델 (Haar 무작위 오라클) 의 영역에서 P=NP 일지라도 타당하게 성립할 수 있는 구체적 가정으로 이동시킵니다.
통합: PRU 라는 단일 가정 하에 정규 형태 및 동일 복사 보안이 있는 UE 의 구성을 통합하여, 이러한 바람직한 특성들이 상호 배타적인 것이 아니라 표준 양자 암호학적 구성 요소에서 자연스럽게 파생됨을 보여줍니다.

저자들은 명시적으로 그들의 결과가 다중 회 안전한 복제 불가능 암호화가 "마이크로크립트의 구체적 가정에서 비롯될 수 있음"을 보여준다고 밝힙니다. 그들은 이러한 원시적 요소를 첫 번째 원리 (예: 격자 문제) 에서 구성한다고 주장하는 것이 아니라, 문제를 이러한 구체적이고 잘 연구된 양자 원시적 요소의 존재로 환원시킵니다.

A Note on Boosting Uncloneable Encryption in Microcrypt