기술 요약: 보안 키 리싱(Secure Key Leasing) 및 복제 방지(Copy Protection)를 갖춘 트랩도어 함수(Trapdoor Functions)

1. 문제 정의 및 동기

본 연구는 복제 불가능한 암호학(unclonable cryptography) 분야의 공백, 즉 보안 키 리싱(SKL) 및 복제 방지(CP) 맥락에서의 **트랩도어 함수(TDF)**에 대한 연구 부족 문제를 다룹니다. TDF는 고전적 공개키 암호학에서 기초적인 프리미티브로서(IND-CPA 및 IND-CCA 보안 공개키 암호 구현을 가능하게 함), 키가 양자 상태이고 기능이 복제 불가능해야 하는 양자 환경에서의 연구는 미비했습니다.

또한, 기존의 공개키 암호 보안 키 리싱(PKE-SKL) 및 단일 복호자 암호(Single-Decryptor Encryption, SDE) 구성은 **키 파괴(key destruction)**라고 알려진 치명적인 취약점을 가집니다. 이러한 스킴들에서 양자 복호 키는 일반적으로 양자 상태입니다. 만약 공격자가 (반드시 정직한 암호화 알고리즘에 의해 생성된 것이 아닌) 악의적으로 선택된 암호문을 키 보유자에게 보낸다면, 복호 과정이 양자 상태를 붕괴시켜 향후 복호에 키를 사용할 수 없게 만들 수 있습니다. 기존 스킴들은 임의의 암호문을 복호한 후에도 양자 복호 키가 재사용 가능하다는 것을 보장하지 못합니다.

본 논문은 두 가지 핵심 질문을 제기합니다:

1. 표준적인 가정으로부터 보안 키 리싱을 갖춘 TDF와 복제 방지를 갖춘 TDF를 구축할 수 있는가?
2. 키 파괴 공격에 대해 안전한 강건한(robust) PKE-SKL 및 SDE 스킴을 구축할 수 있는가?

2. 방법론 및 정의

2.1 보안 키 리싱을 갖춘 트랩도어 함수 (TDF-SKL)

저자들은 TDF-SKL을 $(KG, Eval, Inv, Del, Vrfy)$의 튜플로 정의합니다:

• KG는 고전적 평가 키($ek$), 양자 트랩도어($td$), 그리고 고전적 검증 키($vk$)를 출력합니다.
• Eval은 입력을 출력으로 매핑하는 결정론적 알고리즘입니다.
• Inv는 $td$를 사용하여 함수를 역산하는 양자 알고리즘입니다.
• Del은 $td$의 보유자가 이를 삭제하고 고전적 인증서를 생성할 수 있게 합니다.
• Vrfy는 $vk$를 사용하여 인증서를 검증합니다.

보안 개념은 **일방성(one-wayness)**입니다: $ek$와$td$를 얻고 유효한 삭제 인증서를 제출한 후, 무작위 입력$x$의 결과물인 챌린지 이미지$y$를 받은 공격자는$x$를 복구할 수 없습니다.

논문은 두 가지 변형을 구분합니다:

1. 도메인 샘플러가 없는 TDF-SKL: 일방성은 균등하게 무작위로 샘포링된 입력에 대해 성립합니다.
2. 도메인 샘플러를 포함한 TDF-SKL: 샘플링 알고리즘 $Samp$를 포함합니다. 일방성은$Samp$에 의해 샘플링된 입력에 대해 성립하며, 공격자는 챌린지 이미지와 함께 검증 키$vk$를 받습니다(PKE-SKL의 IND-VRA 보안과 유사함).

2.2 복제 방지를 갖춘 트랩도어 함수 (TDF-CP)

TDF-CP는 $(Setup, KG, Eval, Inv)$로 정의됩니다:

• Setup은 고전적 $ek$와$td$를 생성합니다.
• KG는 $td$로부터 양자 트랩도어$td$를 생성합니다.
• Eval은 결정론적입니다.
• Inv는 양자 역산 알고리즘입니다.

보안 개념은 탐색 안티-파이러시(search anti-piracy) 보안입니다. 보안 게임에서 공격자 $A$는 양자 트랩도어를 받고, 이를 $B$와 $C$가 공유하는 이분 상태(bipartite state)로 분할한 뒤, 그들에게 각각 독립적인 입력 $x_B$와 $x_C$에 대응하는 챌린지 이미지 $y_B$와 $y_C$를 보냅니다. $B$와 $C$는 동시에 각자의 챌린지를 역산해야 합니다. 보안은 두 명 모두 성공할 확률이 무시할 수 있을 정도로 작음을 요구합니다.

2.3 강건성 (Robustness)

스킴이 **강건하다(robust)**는 것은 양자 복호 키가 (악의적으로 구성된 암호문을 포함하여) 어떠한 암호문을 복호한 후에도 재사용 가능함(즉, 복호 전과 후의 상태 사이의 트레이스 거리(trace distance)가 무시할 수 있는 수준임)을 의미합니다.

3. 주요 구성 및 결과

3.1 TDF-SKL의 구성

저자들은 서로 다른 가정에 기반한 두 가지 구성을 제공합니다:

1. 도메인 샘플러가 없는 TDF-SKL:

   • 가정: LWE(Learning With Errors) 및 Hinting 의사 난수 생성기(PRG).
   • 방법론: Garg 등[GHMO21]의 접근 방식을 채택하되, 인증서 제출과 챌린지 수신 순서 문제로 인해 SKL 설정에서 실패하는 "미러링 기법(mirroring technique)"을 피하도록 수정했습니다. 대신, Naor의 커밋먼트 스킴과 Hinting PRG를 사용하여 "거의 모든 키(almost-all-keys)"에 대한 정당성을 달성합니다.
   • 메커니즘: 평가 키는 무작위 문자열 $r_i$를 포함합니다. 출력 $y_i$는 PKE 암호문과 PRG 출력을 사용하여 구성됩니다. 역산 알고리즘은 $r_i$와 관련된 체크를 바탕으로 두 가지 잠재적 암호문을 일관되게 복호하려고 시도합니다.

2. 도메인 샘플러를 포함한 TDF-SKL:

   • 가정: IND-CPA 보안 PKE 및 Hinting PRG.
   • 방법론: 이 변형은 IND-VRA 보안을 갖는 PKE-SKL(IND-CPA PKE로부터 구축 가능)에 의존합니다. 구성은 첫 번째 방식과 유사하지만 도메인 샘플러를 통합하며, 공격자가 챌려지 단계에서 검증 키를 받도록 보장합니다.

3.2 TDF-CP의 구성

• 가정: 은닉 함수(Indistinguishability Obfuscation, iO) 및 LWE.
• 방법론: 저자들은 Ananth와 Behera[AB24]가 제안한 모듈형 프레임워크를 따릅니다.
  1. Puncturable TDFs: 저자들은 먼저 iO, puncturable PRF, 그리고 injective OWF를 사용하여 (두 지점에서 펑처링된 트랩도어가 있어도 역산이 안전한) 펑처러블 TDF를 구축합니다.
  2. Unclonable Puncturable Obfuscation (UPO): 이들은 UPO(iO와 LWE로부터 구축됨)를 사용하여 펑처러블 TDF를 난독화합니다.
  3. 구성: 최종 TDF-CP는 UPO를 사용하여 펑처러블 TDF의 역산 알고리즘을 난독화함으로써 형성됩니다.

3.3 응용: 강건한 PKE-SKL 및 강건한 SDE

이 새로운 TDF 프리미티브의 주요 응용은 강건한 암호 스킴을 구축하는 것입니다.

1. 강건한 PKE-SKL:

   • 구성: 도메인 샘플러를 갖는 TDF-SKL로부터 구축됩니다.
   • 메커니즘: 암호화는 Goldreich-Levin 정리를 사용합니다. 복호 알고리즘은 TDF-SKL의 일관된 역산을 수행합니다. 입력이 유효한 이미지라면 역산은 높은 확률로 성공하며, 그렇지 않으면 $\perp$를 출력합니다.
   • 강건성 증명: Gentle Measurement Lemma에 의해, 측정 결과(성공 또는 실패)가 거의 결정론적이라면, 측정 후의 상태는 원래의 상태와 매우 가깝게 유지됩니다. TDF-SKL 역산은 유효한 입력에 대해 거의 항상 정확하고 유효하지 않은 입력은 항상 거부하므로, 복호 키는 재사용 가능합니다.
   • 보안: 결과적인 스킴은 IND-VRA 보안을 가집니다.

2. 강건한 SDE:

   • 구성: TDF-CP로부터 구축됩니다.
   • 메커니즘: 강건한 PKE-SKL과 유사하게 Goldreich-Levin 정리를 활용하고 TDF-CP 역산을 사용합니다.
   • 보안: 결과적인 스킴은 CPA+ 안티-파이러시 보안을 가지며 강건합니다.

4. 의의 및 주장

본 논문은 보안 키 리싱 및 복제 방지 설정에서 TDF 연구를 시작한 최초의 연구임을 주장합니다. 그 의의는 다음과 같습니다:

1. 기초적 확장: 고전 암호학의 초석인 TDF의 활용 범위를 복제 불가능한 양자 암호 영역으로 확장했습니다.
2. 키 파괴 문제 해결: 기존 PKE-SKL 및 SDE 스킴의 취약점인 키 파괴를 해결했습니다. 구축된 스킴들은 **강건(robust)**하며, 이는 양자 복호 키가 임의의(잠재적으로 악의적인) 암호문을 복호한 후에도 생존함을 의미합니다.
3. 블랙박스 구성: 저자들은 강건한 PKE-SKL 구축이 오직 암호적 프리미티브의 **블랙박스 사용(black-box use)**에만 의존한다는 점을 강조합니다. 이는 본질적으로 비-블랙박스 방식인 비대화형 영지식 증명(NIZK)을 사용하는 대안적 접근 방식과 대조됩니다.
4. 광범위한 인스턴스화: 이 접근 방식은 Hinting PRG 및 PKE를 통해 그룹 액션 기반 가정(group-action-based assumptions) 하에서도 구현이 가능합니다. 반면 NIZK 기반의 강건성은 현재 이러한 가정 하에서 알려져 있지 않습니다.
5. 모듈형 프레임워크: 본 연구는 복잡한 양자 암호 프리미티브를 표준 가정(iO, LWE)으로부터 구축하기 위해 모듈형 프레임워크(복제 방지를 위한 UPO 등)의 강력함을 입증합니다.

저자들은 자신의 연구가 LWE, iO와 같은 표준 가정에 기반한 구성을 제공하고 있지만, 복제 불가능한 암호학 분야가 여전히 발전 중인 단계이며, 본 연구가 이러한 양자 환경에서의 TDF 탐구를 위한 토대를 마련했다는 점을 언급하며 겸허한 태도를 유지합니다.