기술 요약: 검증 가능하고 공모 저항성을 갖춘 다자간 양자 사적 집합 연산

1. 문제 정의

사적 집합 교집합(PSI)과 합집합(PSU)을 포함한 사적 집합 연산(PSO)은 안전한 다자간 계산(SMC)의 근간이 된다. 고전적인 암호학적 해결책들이 존재하지만, 양자 알고리즘(예: 쇼어 알고리즘)의 등장은 현재의 수론적 체계들을 위협하고 있다. 결과적으로 연구의 흐름은 양자 PSI(QPSI)로 이동하고 있다.

그러나 기존의 양자 PSO(QPSO) 프로토콜은 다음과 같은 중대한 한계에 직면해 있다:

• 위협 모델: 기존의 대부분의 QPSI 방식은 반-정직한 신뢰할 수 있는 제3자(TP)를 가정하거나, TP가 참여자와 공모할 수 없다는 가정에 의존한다.
• 공모 저항성: 이전의 다자간 QPSI(MP-QPSI) 프로토콜은 TP와 일부 참여자 간의 공모를 방어하지 못하거나, 단 한 명의 참여자 부패만을 허용하는 경우가 많다.
• 검증 가능성: 많은 방식이 TP가 규정된 양자 회로를 올바르게 실행했는지 검증하는 메커니즘이 부족하여, 악의적인 이탈에 취약하다.

2. 방법론

저자들은 **검증 가능한 양자 완전 동형 암호(vQFHE)**와 **임계치 완전 동형 암호(TFHE)**를 결격한 다자간 양자 사적 집합 교집합(MP-QPSI) 프로토콜을 제안한다. 이 프로토콜은 $n$명의 데이터 보유 참여자, 강력한 양자 TP, 그리고 신뢰할 수 있는 권위자(TA)가 포함된 모델에서 작동한다.

핵심 구성 요소

1. 임계치 키 관리 (TFHE):

   • 복호화를 위한 비밀키는 $(t, n)$-임계치 비밀 공유 방식을 사용하여 $n$명의 참여자 사이에 분산된다.
   • 복호화에는 최소 $t$명의 참여자가 협력해야 한다. 이는 부패한 참여자의 부분 집합이나, $t$명 미만의 참여자와 TP 사이의 공모가 비밀키를 복구하거나 사적 입력을 알아내는 것을 방지한다.

2. 검증 가능한 양자 평가 (vQFHE):

   • 프로토콜은 [ADS+17]의 TrapTP 구성을 vQFHE 계층으로 활용한다.
   • 암호화: 참여자들은 CSS 코드를 사용하여 자신의 사적 집합을 양자 상태로 인코딩하고, 트랩 큐비트($|0\rangle$ 및 $|+\rangle$)를 추가하며, 무작위 치환을 적용한 후 양자 일회용 패드(QOTP)로 마스킹한다. QOTP 키는 TFHE 하에서 암호화되며 MAC(메시지 인증 코드)으로 인증된다.
   • 평가: TP는 암호화된 양자 상태에 대해 다자간 AND 회로($C_{\text{AND}}$)의 동형 평가를 수행한다. TP는 암호화된 QOTP 키를 동형적으로 업데이트하며, 가든 호스(garden-hose) 모델을 따라 비-클리포드(non-Clifford) T 게이트를 처리하기 위해 "가젯(gadgets)"(매직 상태)을 소비한다.
   • 검증: TP는 평가의 클래식 트랜스크립트(로그)를 생성한다. 참여자와 TA는 MAC, 게이트 배열, 그리고 트랩 코드 측정을 통해 이 로그를 검증하여 TP가 대상 회로에서 이탈하지 않았음을 확인한다.

3. 프로토콜 흐름:

   • 1단계 (준비): TA가 키를 생성하고, 치환을 샘플링하며, T-게이트 가젯을 준비하고, 비밀 공유분을 배분한다.
   • 2단계 (암호화): 참여자들은 집합을 양자 상태로 인코딩하고, 트랩과 QOTP를 적용한 후, 암호화된 상태와 키를 TP에게 보낸다.
   • 3단계 (평가): TP는 $C_{\text{AND}}$ 회로를 동형적으로 실행하며, 키를 업데이트하고 트랜스크립트를 기록한다.
   • 4단계 (검증 및 복호화): 참여자들은 클래식 검증(MAC, 게이트 및 트랜스크립트 확인)과 임계치 복호화를 수행하여 QOTP 키를 복구한다. TA는 양자 검증(트랩 체크)을 수행하고 최종 상태를 복호화하여 교집합 결과를 브로드캐스트한다.

3. 주요 기여

• 다자간 확장: 저자들은 vQFHE를 TFHE와 결합하여 다자간 환경으로 확장함으로써, $n$명의 당사자가 사적 데이터를 드러내지 않고 집합 교집합을 계산할 수 있도록 하였다.
• 공모 저항성: 기존의 QPSI 방식과 달리, 이 프로토케은 TP와 최대 $t-1$명의 참여자 간의 공모를 저항한다. 임계치 메커니즘은 부패한 당사자가 $t$명 미만인 한 비밀키와 사적 입력이 안전하게 유지됨을 보장한다.
• 악의적 TP에 대한 검증 가능성: 프로토콜은 의미론적 보안과 검증 가능성을 제공한다. 클래식 트랜스크립트 검증과 양자 트랩 코드 체크의 조합을 통해, TP가 규정된 회로(예: 게이트 배열이나 출력을 변경하는 행위)에서 이탈하는 것을 탐지할 수 있다.
• 모듈형 프레임워크: 이 구조는 모듈형 프레임워크로 제시된다. 저자들은 다음과 같은 방법을 시연한다:
  • T-게이트 수를 줄이기 위해 (예: $C_nX$ 대신 CCCZ 게이트 사용) 회로 복잡도를 낮추는 법.
  • 오픈-컨트롤 제어 연산을 통해 AND 회로를 OR 회로로 대체하여 양자 사적 집합 합집합(QPSU) 기능을 확장하는 법.
  • 효율성/보안성 트레이드오프를 위해 기초가 되는 vQFHE 인스턴션을 교체하는 법.

4. 결과 및 분석

• 정확성: 저자들은 IBM 양자 플랫폼과 Qiskit을 사용하여 논리적 다자간 AND 게이트를 검증하였다. 시뮬레이션 결과, 출력 분포가 논리적 AND 연산의 이상적인 진리표와 일치함을 확인하였다.
• 보안 증명:
  • 개인정보 보호: 프로토콜은 양자 상태에 대해서는 (QOTP 및 최대 혼합 상태 덕분에) 정보 이론적으로 안전하며, 클래ical 데이터에 대해서는 (TFHE 및 MAC 덕분에) 계산적으로 안전함이 증명되었다.
  • 공모: 정리 3은 부패한 참여자들의 연합(크기 $<t$)이 TP와 공모하더라도 교집합 결과 이상의 정보를 얻을 수 없음을 증명한다.
  • 검증 가능성: $\kappa$-SEM-VER 의미론적 보안 모델 하에서, 프로토콜은 검증 가능함이 입증되었다. 하이브리드 논증을 통해 TP의 어떠한 이탈도 압도적인 확률로 탐지됨을 보여준다.
• 성능:
  • 통신 복잡도: 양자 통신 비용은 $O(n\kappa L)$이며, 여기서 $n$은 참여자 수, $\kappa$는 보안 파라미터, $L$은 집합 크기이다.
  • 비교: 기존 방식들(예: [SMZ+15], [ZLS+20], [HZZ24])과 비교했을 때, 제안된 프로토콜은 TP-참여자의 공모 및 악의적 TP 행동에 대한 저항성을 제공하면서 PSI와 PSU 기능을 모두 지원하는 유일한 프로토콜이다.

5. 의의 및 주장

본 논문은 기존 QPSI 솔루션의 고질적인 문제인 "TP-참여자 공모" 격차를 해결함으로써 양자 보안 계산 분야의 중요한 진전을 이루었다고 주장한다.

• 강건성: TFHE를 통합함으로써, 이 프로토콜은 양자 PSI에서 이전에 볼 수 없었던 수준의 공모 저항성을 달al하며, TP와 일부 참여자가 공모하더라도 보안을 보장한다.
• 신뢰 최소화: 검증 계층은 TP의 정직함이 아닌 계산 능력만을 신뢰하게 함으로써, TP가 악의적일지라도 시스템이 안전하게 작동할 수 있게 한다.
• 유연성: 모듈형 설계는 프레임워크가 다양한 집합 연산(합집합, 카디널리티)에 적응하고, 서로 다른 하드웨어 제약 조건(예: T-게이트 복잡도 감소)에 최적화될 수 있도록 한다.

저자들은 본 프로토콜이 강력한 보안을 제공하지만, TrapTP 기반 vQFHE와 관련된 클래식 오버헤드를 상속받는다는 점을 인정한다. 향후 연구로는 가젯이 없는(gadget-free) T-핸들링 탐색과 클래식 통신 비용을 줄이기 위한 추가적인 최적화가 제안되었다.