기술 요약: NP의 최악의 경우 어려움으로부터 양자 비식별성 난독화를 통한 양자 암호학까지

문제 정의

비식별성 난독화(indistinguishability obfuscation, iO)는 강력한 암호학적 프리미티브로, 일방향 함수(one-way functions, OWFs)와 결 조합될 때 방대한 양의 고급 암호 도구들을 구축할 수 있게 한다. 그러나 iO 그 자체만으로는 OWF의 존재를 함의하지 않으며, NP의 어려움에 관한 추가적인 가정이 필요하다. 고전적 설정에서, Komargodski 등 [KMN+14]은 NP의 무한히 자주 발생하는(infinitely-often) 최악의 경우 어려움($NP \not\subseteq i.o.BPP$)을 가정하면, 고전적 iO로부터 OWF를 구성할 수 있음을 입증했다.

본 연구에서 다루는 핵심 문제는 **양자 비식별성 난독화(quantum iO)**의 암호학적 능력이다. 고전적 난독화기와 달리, 양자 난독화기는 측정으로 인해 본질적으로 무작위성을 띠므로, 랜덤 시드를 고정함으로써 "역무작위화(derandomization)"할 수 없다. 결과적으로, derandomizability에 의존하는 [KMN+14]의 고전적 OWF 구성 방식는 양자 환경으로 직접 확장되지 않는다. 양자 iO가 NP의 양자적 최악의 경우 어려움($NP \not\subseteq i.o.BQP$)과 결합되었을 때, 어떠한 암호학적 프리미티브(종종 "Microcrypt" 프리미티브라 불리는, OWF를 요구하지 않는 것들)를 함의할 수 있는지는 여전히 불분명하다.

방법론

저자들은 세 가지 구성 요소(난독화 알고리즘, 평가 알고리즘, 난독화된 인코딩)의 계산적 성격(고전적 vs 양자적)에 기반하여 다양한 변형을 정식화함으로써 양자 iO에 대한 체계적인 연구를 시작한다.

1. 난독화 알고리즘 ($Obf$)
2. 평가 알고리즘 ($Eval$)
3. 난독화된 인코딩 ($\hat{C}$)

이들은 $X, Y, Z \in \{Q, C\}$ (여기서 $Q$는 양자, $C$는 고전을 의미)를 나타내는 $(X, Y, Z)$-iO를 정의한다. 본 논문은 다섯 가지 유의미한 변형인 $(Q, Q, Q)$, $(Q, Q, C)$, $(Q, C, C)$, $(C, Q, C)$, 그리고 $(C, C, C)$에 초점을 맞춘다.

핵심 기술적 접근법

그들의 결과의 토대는 NP의 최악의 경우 어려움으로부터 특정 암호학적 분포의 존재성으로의 환원(reduction)이다. 방법론은 다음과 같이 진행된다:

1. Valiant-Vazirani 환원: 저자들은 Valiant-Vazirani 정리를 활용하여 $NP \not\subseteq i.o.BQP$ 가정을 $UP \not\subseteq i.o.BQP$ (여기서 UP는 유일한 증거를 가진 문제들의 클래스)로 환원한다. 이를 통해 유일한 증거를 가진 문제들을 다룰 수 있게 된다.
2. 점 함수(Point Function)와 제로 함수(Zero Function)의 비식별성: 핵심 기술 정리(정리 4.1)는 $NP \not\subseteq i.o.BQP$ 가정 하에, 랜덤 점 함수 $P_k$(입력 $k$에 대해서만 1을 출력하는 함수)의 난독화가 제로 함수 $Z_m$(모든 입력에 대해 0을 출력하는 함수)의 난독화와 계산적으로 구별 불가능함을 입증한다. 이는 구별자가 동일한 비밀 키 $k$로 생성된 여러 샘플을 제공받는 경우에도 성립한다.
   • 증명 스케치: 만약 구별자가 $Obf(P_k)$와 $Obf(Z_m)$을 구별할 수 있다면, UP 인스턴스의 유일한 증거를 복구하는 알고리즘을 구성할 수 있다. 이는 정확히 하나의 입력($w \oplus v$)에서 제로 함수와 달라지는 회로 $V[x, v]$를 구성함으로써 달성된다. iO의 보안성(특히 이 설정에서의 단일 지점 차이 입력 난독화와의 동치성)에 의해, 난독화된 것들을 구별하는 것은 차이가 발생하는 입력을 추출하여 증거 $w$를 복구하는 것을 가능하게 한다.
3. 프리미티브의 구성: $Obf(P_k)$와 $Obf(Z_m)$의 비식별성을 사용하여 다양한 암호화 방식 및 프리미티브를 구성한다. 구체적인 구성은 $(X, Y, Z)$ 변형에 따라 달라진다:
   • **공개 키 암호화(PKE)**의 경우, $Obf(P_k)$를 공개 키로 사용하며, 입력이 비밀 키와 일치하는지 확인하는 회로를 난독화하여 구성한다.
   • **대칭 키 암호화(SKE)**의 경우, 메시지 1과 0에 대해 각각 $Obf(P_k)$와 $Obf(Z_m)$을 암호문으로 사용한다.

주요 기여 및 결과

본 논문은 양자 iO가 $NP \not\subseteq i.o.BQP$와 결합되었을 때 풍부한 암호학적 프리미티브 계층을 함의함을 보여준다. 결과는 iO의 변형에 따라 다음과 같이 요약된다:

• $(Q, Q, Q)$-iO (양자 난독화, 양자 평가, 양자 인코딩):

  • 비밀 키는 고전적이고 암호문은 양자 상태인 **IND-CPA 보안 양자 대칭 키 암호화(QSKE)**를 함의한다.
  • 일방향 상태 생성기(OWSGs) 및 EFI 쌍을 함의한다.

• $(Q, Q, C)$-iO (양자 난독화, 양자 평가, 고전적 인코딩):

  • 로컬 계산은 양자적이지만 통신은 고전적인 IND-CPA 보안 QCCC SKE(Quantum-computation Classical-communication SKE)를 함의한다.
  • EV-OWPuzzs(효율적으로 검증 가능한 일방향 퍼즐), OWPuzzs, OWSGs, QEFID 쌍, 그리고 EFI 쌍을 함의한다.

• $(Q, C, C)$-iO (양자 난독화, 고전적 평가, 고전적 인코딩):

  • IND-CPA 보안 QCCC PKE를 함의한다.
  • $(Q, Q, C)$-iO와 동일한 프리미티브 세트(EV-OWPuzzs, OWPuzzs, OWSGs 등)를 함의한다.
  • 참고: 난독화기가 양자적이므로, 표준적인 경로를 통해서는 직접적으로 OWF가 함의되지 않지만, 암호화 방식은 직접 구성된다.

• $(C, Q, C)$-iO (고전적 난독화, 양자 평가, 고전적 인코딩):

  • IND-CPA 보안 QCCC PKE를 함의한다.
  • (포스트 양자) OWFs를 함의한다.
  • 결과적으로 의사 난수 유니터리(PRUs)가 함의하는 모든 Microcrypt 프리미티브를 함의한다.

• $(C, C, C)$-iO (고전적 난독화, 고전적 평가, 고전적 인코딩):

  • IND-CPA 보안 PKE 및 (포스트 양자) OWFs를 함의한다.
  • 이는 [KMN+14]의 고전적 결과를 재현하지만, 더 단순화된 증명과 더 약한 요구사항을 가진다.

의의 및 주장

저자들은 다음과 같은 몇 가지 중요한 기여를 주장한다:

1. 양자 iO 연구의 개시: 본 연구는 양자 iO의 암호학적 함의를 체계적으로 분석하고, 자연스러운 변형들을 정의하며, 그 능력을 특정 프리미티브와 매핑하는 최초의 연구이다.
2. 최악의 경우 어려움과 양자 암호학의 연결: 본 논문은 NP의 무한히 자주 발생하는 최악의 경우 어려움이 양자 iO와 결합될 때(특정 변형의 경우 OWF가 없는 경우에도) 광범위한 양자 암호학적 프리미티브(OWSGs 및 EFI 쌍 포함)를 구성하기에 충분함을 입증한다.
3. 고전적 결과의 단순화: 고전적 설정($(C, C, C)$-iO)에서도, 저자들은 불완전한 iO와 최악의 경우 NP 어려움으로부터 OWF를 도출하는, 아마도 더 단순한 새로운 구성을 제공한다. 그들의 접근 방식은 [KMN+14]에서 요구되었던 "연쇄적 난독화"(이미 난독화된 회로를 다시 난독화하는 것)를 피하며, 일반적인 회로 대신 3CNF 공식에 대한 난독화만을 요구한다.
4. 미해결 문제의 해결: 최악의 경우 어려움 하에서 3CNF 공식을 위한 불완전한 iO로부터 OWF를 구성하는 것은 [KMN+14]가 남긴 미해결 문제였다. 저자들은 이 문제가 최근 다른 연구들[HN24, LMP24]에 의해 다른 기술로 해결되었음을 언급하면서도, 자신들의 접근 방식이 대안적이고 더 단순한 경로를 제공한다고 밝힌다.

논문은 이러한 결과들이 양자 iO와 NP의 최악의 경우 어려움에 조건부적임을 강조하며 겸허한 어조를 유지하며, 구성된 특정 프리미티브는 난독화 구성 요소의 양자적/고전적 성격에 크게 의존함을 명시한다.