On the Impossibility of Simulation Security for Quantum Functional Encryption

기술 요약: 양자 함수 암호(Quantum Functional Encryption)의 시뮬레이션 보안 불가능성에 관하여

문제 정의
함수 암호(Functional Encryption, FE)는 데이터에 대한 세밀한 접근을 허용하는 암호 기술로, 사용자가 함수 키 $fk_F$를 보유하면 $m$의 암호문으로부터 $m$ 이외의 다른 정보는 학습하지 않고 $F(m)$을 계산할 수 있다. FE의 가장 강력한 보안 개념은 **시뮬레이션 기반 보안(simulation-based security, SIM-security)**이며, 이는 공격자가 암호문과 함수 키로부터 계산할 수 있는 모든 것이 오직 함수의 출력값만을 사용하여 시뮬레이션될 수 있어야 함을 요구한다.

고전적인 불가능성 결과들은 특정 쿼리 모델(예: 단일 적응적 키를 사용하는 다수의 암호문, 또는 단일 암호문을 사용하는 다수의 비적응적 키) 하에서 일반 다항식 회로에 대해 SIM-보안 FE를 달성하는 것이 불가능함을 입증해 왔다. 그러나 이러한 증명들은 본질적으로 고전적인 논리에 의존한다. 핵심적인 미결 과제는 다음과 같았다: 이러한 고전적 불가능성이 양자 영역에도 확장되는가? 구체적으로, 양자 자원(양자 암호문, 양자 함수 키, 또는 양자 공개 키)이 이러한 장벽을 극복하여 SIM-보안 양자 함수 암호(QFE)를 실현할 수 있는가?

방법론
저자들은 고전적인 불가능성 증명을 양자 설정으로 확장하고, 이를 양자 상태 및 연산을 처리할 수 있도록 조정함으로써 이 질문을 다룬다. 방법론은 서로 다른 세 가지 QFE 보안 변형을 대상으로 하는 세 가지 별개의 불가능성 증명을 포함한다:

1. 정보 이론적 압축 논증: 저자들은 SIM-보안 게임에서의 시뮬레이터의 과업을 정보 압축 문제로 재해석한다. 만약 SIM-보안 스킴이 존재한다면, 이는 대량의 정보(메시지 또는 상태)를 작은 양자 상태(함수 키 또는 암호문)로 압축하면서도 완벽한 복구를 허용하는 압축 알고리즘의 존재를 함의함을 보여준다.
2. 양자 비압축성 정리(Quantum Incompressibility Lemmas):
   • 다수 암호문 케이스의 경우, 저자들은 얽힘 보조 통신(entanglement-assisted communication)에 관한 [20]의 결과를 활용하여 $n$ 비트를 $n/2$ 미만의 큐비트로부터 신뢰성 있게 복구할 수 없음을 보여준다.
   • 간결한 스킴(succinct scheme) 케이스의 경우, 저자들은 **의사 난수 상태(Pseudorandom States, PRS)**의 비압축성에 관한 새로운 정리를 증명한다. 저자들은 $n$-큐비트 PRS를 $n-k$ 큐비트로 압축하면 구조가 거의 완전히 소실되며, 복구 기대 충실도(fidelity)가 압축량에 따라 지수적으로 감소함을 보여준다. 이는 평균 충실도와 얽힘 충실도 사이의 관계와 Haar 난수 상태에 대한 측도 집중(concentration of measure)에 관한 Levy의 보조 정리를 결ang하여 증명된다.
3. 표준 암호 가정으로의 환원(Reductions to Standard Cryptographic Assumptions):
   • 다수 키 쿼리 케이스의 경우, 저자들은 SIM-보안 QFE의 존재로부터 **공개키 암호(Public-Key Encryption, PKE)**를 깨는 것으로의 환원을 구성한다. 저자들은 1-M-NA(단일 메시지, 다수 쿼리, 비적응적) QFE를 위한 시뮬레이터가 여러 개의 독립적인 PKE 암호문에 대한 정보 압축기로 작용하게 되며, 이는 기저 PKE 스킴의 보안을 위반함을 보여준다.

주요 기여 및 결과

본 논문은 비밀키 QFE(이는 즉시 공개키 QFE의 불가능성을 의미함)에 대한 세 가지 주요 불가능성 결과를 확립한다:

1. M-1-AD SIM-보안 QFE의 무조건적 불가능성:

   • 설정: 공격자가 많은 메시지($M$)의 암호화를 요청한 후, 항등 함수(identity function)에 대한 단일 적응적 함수 키(1-AD)를 얻는다.
   • 결과: 그러한 스킴은 존재할 수 없다.
   • 메커니즘: 시뮬레이터는 메시지를 모르는 상태에서 $n$ 개의 암호문을 생성해야 한다. 항등 키를 받은 후, 시뮬레이터는 $n$ 개의 메시지를 모두 복구해야 한다. 이는 $n$ 개의 무작위 메시지를 $p \ll n$ 크기의 다항식으로 제한된 함수 키로 압축해야 함을 의미하며, 저자들은 이것이 고전적 정보를 더 작은 양자 상태로 압축하는 정보 이론적 한계를 위반하므로 양자 상태를 사용하더라도 불가능함을 증명한다.

2. Succinct 1-1-NA SIM-보안 QFE의 조건부 불가능성:

   • 설정: 공격자가 단일 메시지와 단일 비적응적 함수 키를 요청한다. 이 스킴은 간결하며(ciphertext size가 함수 크기에 독립적임), 대상은 PRS 생성기 회로 클래스이다.
   • 가정: 의사 난수 상태(PRS)의 존재.
   • 결과: 그러한 스킴은 존재할 수 없다.
   • 메커니즘: 저자들은 PRS 생성기에 대한 간결한 QFE가 PRS의 압축 및 복구를 허용함을 보여준다. 저자들은 PRS가 비압축적임을 증명한다(이는 PRF가 PRS를 함의한다는 점에서 고전적 PRF보다 강한 성질이다). 만약 간결한 QFE가 존재한다면, 압축된 상태가 복구 가능한지 확인함으로써 PRS를 Haar 난수 상태와 구별할 수 있게 되며, 이는 PRS 가정을 깨뜨린다.

3. 1-M-NA SIM-보안 QFE의 조건부 불가능성:

   • 설정: 공격자가 단일 암호문과 다수의 비적응적 함수 키를 요청한다.
   • 가정: 클래식 키를 가진 공개키 암호(PKE)의 존재.
   • 결과: 그러한 스킴은 존재할 수 없다.
   • 메커니즘: 저자들은 공격자가 $n$ 개의 독립적인 PKE 암호문(서로 다른 메시지를 암호화함)을 단일 QFE 암호문으로 압축하는 데 QFE 시뮬레이터를 사용하는 공격을 구성한다. 만약 시뮬레이터가 성공한다면, 단일 압축 암호문과 함수 키들로부터 $n$ 개의 메시지를 모두 복구할 수 있게 된다. 이는 기저 PKE 스킴의 보안을 위반한다. 주목할 점은, 이 결과는 PRS 기반 결과와 달리 비간결한(non-succinct) 스킴에 대해서도 성립한다는 것이다.

의의 및 주장

본 논문은 양자 자원이 SIM-보안 FE의 고전적 장벽을 우회할 수 있는지에 대한 핵심적인 질문을 해결했다고 주장한다. 저자들은 고전적 불가능성이 양자 세계에서도 대체로 확장됨을 결론짓는다. 다만, 그 증명에는 양자 상태를 다루기 위한 새로운 기술적 도구들이 필요했다.

• 미묘한 차이의 장벽: 결과는 고전적인 것보다 더 미묘하다. 예를 들어, 양자 환경에서의 1-M-NA SIM-보안 불가능성은 PKE(또는 간결한 스킴의 경우 PRS)의 가정에 의존하는 반면, 고전적 결과는 무조건적이다(고전적 FE는 PRF를 함의하므로). 이는 장벽은 존재하지만, 이를 증명하기 위해 필요한 구체적인 암호학적 가정이 양자 영역에서는 다르다는 점을 강조한다.
• 가정의 독립성: 논문은 사용된 가정들(PRS와 PKE)이 서로 비교 불가능하다고 강조한다. PKE는 일방향 함수(및 따라서 PRS)와 분리되어 있음이 알려져 있으며, 역방향의 함의는 존재하지 않는다. 따라서 두 가지 조건부 불가능성 결과는 SIM-보안 QFE의 존재에 대한 독립적인 증거를 제공한다.
• 증명의 참신함: 저자들은 독자적인 관심사가 될 수 있는 PRS에 대한 새로운 비압축성 성질을 도입한다. 또한, 스킴의 간결성에 의존하지 않는 1-M-NA SIM-보안 QFE에 대한 최초의 불가능성 증명을 제공한다.
• 범위: 결과는 일반적인 회로 클래스에 적용된다. 저자들은 제한된 클래스(예: "preimage sampleable" 회로)나 특정 모델(예: bounded-quantum-storage 모델)은 여전히 SIM-보안을 허용할 수 있음을 인정하지만, 일반적인 QFE에 대해서는 시뮬레이션 기반 보안 목표가 달성 불가능해 보인다고 밝힌다.

요약하자면, 본 논문은 암호문에 담긴 정보와 함수 키(또는 그 반대)의 크기 사이의 근본적인 긴장 관계가 양자 설정에서도 지속되어, 함수 암호의 가장 강력한 보안 개념인 SIM-보안의 실현을 방해한다는 것을 보여준다.