Quantum Multi-Party Threshold Private Set Intersection with Explicit Cardinality Testing

기술 요약: 명시적 카디널리티 테스트를 포함한 양자 다자간 임계값 프라이빗 셋 인터섹션(Quantum Multi-Party Threshold Private Set Intersection with Explicit Cardinality Testing)

문제 정의
프라이빗 셋 인터섹션(PSI)은 당사자들이 서로의 비교집합이 아닌 원소들을 드러내지 않고도 자신의 프라이빗 셋 간의 교집합을 계산할 수 있게 해준다. 임계값 PSI(TPSI)는 교집합의 카디널리티(원소 개수)가 공개된 임계값 $\tau$와 같거나 커지는 경우에만 교집합을 공개하도록 확장된 개념이다. 기존의 고전적 TPSI 프로토콜은 존재하지만, 기존의 양자 TPSI 프로토콜(예: [MSD+24, LZY+26, WLS+26])은 일반적으로 최종 측정을 수행하고 결과를 해석하기 위해 제3자(Third Party, TP)에 의존한다. 이러한 방식에서 TP는 정확한 교집합 카디스널리티를 복구한 후 이를 $\tau$와 비교한다. 이러한 접근 방식은 이상적인 TPSI 패러다임에서 벗어나는데, 이는 단 하나의 비트 술어인 $\mathbb{1}[|\bigcap X_i| \ge \tau]$만을 드러내는 대신 정확한 카디널리티 통계치를 TP에게 노출하기 때문이다. 이는 기능적 불일치를 초래하며, TP가 양자 자원 제공자이자 프라이빗 데이터의 의미론적 해석자 역할을 동시에 수행하게 함으로써 권한을 집중시키는 문제를 발생시킨다.

방법론
저자들은 측정 역할과 의미론적 해석 역할을 분리하는 다자간 양자 TPSI(MP-QTPSI) 프로토콜을 제안한다. 이 프로토콜은 $n$명의 참여자($P_1, \dots, P_n$)와 반-정직(semi-honest) 모델의 TP를 포함한다.

1. 양자 단계 (Hidden-Label 구성):

   • 설정: 참여자들은 TP가 없는 양자 컨퍼런스 키 합의(QCKA)를 통해 마스터 키를 구축하여 위치 은닉 키 $k$, 숨겨진 레이블 플립 벡터 $\mathbf{b}$, 그리고 회전 공유값 $\Delta_i$를 도출한다. TP와 각 참여자는 회전 마스크를 위한 쌍별 키 $T_i$를 구축한다.
   • 인코딩: 참여자들은 자신의 셋에 양의 앵커 셋(positive anchor sets)을 추가하고, 위치 은닉 맵 $x \mapsto kx \mod M$을 적용한다. 이들은 자신의 셋을 인디케이터 벡터 $Y_i$로 인코딩한다.
   • 상호작용: TP는 단일 광자 시퀀스를 준비하고 초기 블라인딩 회전을 적용한다. 시퀀스는 참여자들을 순차적으로 통과한다. 각 참여자 $P_i$는 자신의 데이터($0$또는$\pi/n$), 자신의 쌍별 마스크$T_i$, 그리고 회전 공유값$\Delta_i$에 따라 회전을 적용한다.
   • 측정: TP는 알려진 마스크를 제거하고 시퀀스를 측정한다. 상관된 집합적 회전 덕분에, 측정 결과는 모든 참여자가 해당 원소를 보유하고 있거나(교집합) 아무도 보유하지 않은 경우(비교집합)에만 결정적이지만, 이 결과들의 의미론적 의미(어떤 레이블이 "교집합"에 해당하는지)는 숨겨진 플립 벡터 $\mathbf{b}$에 의해 가려진다. TP는 숨겨진 레이블 인디케이터 벡터 $z_S$(동일) 및 $z_O$(반대)를 얻지만, 참여자 측의 정보 없이는 이를 해석할 수 없다.

2. 고전 단계 (카디널리티 테스트):

   • 마스크된 일관성 테스트: 프로토콜은 숨겨진 측정값을 마스크된 레이블 일관성 테스트로 변환한다. 참여자들은 참조 레이블 $\rho$와 실제 및 앵커 도메인에 대한 셀렉터 마스크를 보유한다.
   • 올리비어스 선형 평가 (OLE): TP와 참여자들은 OLE 기반의 Oblivious Inner Product(OIP)를 사용하여, 서로에게 벡터를 드러내지 않고 일관성 카운트(불일치 $d_{\mathcal{R}}$ 및 $d_{\mathcal{A}}$)의 가산 공유(additive shares)를 계산한다.
   • 임계값 결정: 경량 가드형 회로(garbled circuit)가 술어 $\text{flag} = 1 \iff (d_{\mathcal{A}} = 0) \land (d_{\mathcal{R}} \le |\mathcal{R}| - \tau)$를 평가한다. 이 과정은 오직 불리언(boolean) 결과만을 출력하여, 정확한 카디널리티가 TP에게 절대 노출되지 않도록 보장한다.
   • 재구성: 만약 $\text{flag}=1$이면, TP는 숨겨진 벡터를 브로드캐스트하고, 참여자들은 자신의 참조 레이블과 역키 $k^{-1}$를 사용하여 교집합을 재구성한다.

주요 기여

• 명시적 카디널리티 테스트: 이 프로토콜은 정확한 카디널리티 통계를 TP에게 노출하지 않고 오직 임계값 술어 $\mathbb{1}[|\bigcap X_i| \ge \tau]$만을 출력함으로써, 엄격하게 카디널리티 테스트 패러다임을 준수하는 최초의 양자 TPSI이다.
• 숨겨진 레이블 양자 설계: 참여자 측의 상관된 집합적 회전과 숨겨진 플립 벡터를 활용함으로써, TP의 측정 결과가 의미론적으로 가려지도록 보장한다. TP는 단순히 측정 당사자로서 행동하며, 측정 결과를 특정 셋의 원소나 카디널리티로 매핑할 수 없다.
• 공모 및 TP에 대한 보안: 디코이 광자(decoy photons)를 통해 외부 도청자에 대한 보안을 증명하며, 반-정직한 TP(셋이나 카디널리티를 알 수 없음) 및 공모하는 참여자(쌍별 마스크와 미지의 블라인딩 회전으로 인해 타인의 셋을 추론할 수 없음)에 대해서도 보안을 입증한다.
• 변조 탐지: 숨겨진 앵커 셋의 포함은 일관성 체크($d_{\mathcal{A}}=0$)를 가능하게 하여, TP가 보고된 측정 벡터를 수정했는지 여부를 감지할 수 있다.

결과

• 정확성: 이론적 증명을 통해 프로토콜이 교집합 패턴을 올바르게 인코딩하고, 고전적 하위 프로토콜이 임계값 조건을 올바르게 평가함을 보여준다.
• 시뮬레이션: 저자들은 IBM Qiskit 플랫폼을 사용하여 토이 모델($n=3$, 도메인 크기 8)에 대해 양자 단계를 구현하였다. 시뮬레이션에는 데폴러라이징(depolarizing), 페이즈 댐핑(phase-damping), 리드아웃 에러(readout errors)가 포함되었다. 노이즈가 포함된 시뮬레이션 결과(표 3)는 이론적 확률과 밀접하게 일치하였으며, 앵커 체크와 임계값 테스트를 성공적으로 통과하여 올바른 교집합 $\{1, 3\}$을 재구성하였다.
• 복잡도: 양자 통신 비용은 $\mathcal{O}(n(\ell M + \delta))$이며, 계산 비용은 이와 유사하다 (여기서 $M$은 확장된 도메인 크기, $\ell$은 반복 횟수, $\delta$는 디코이의 수이다).

의의 및 주장
본 논문은 제안된 프로토콜의 주요 의의가 기존 양자 TPSI 프로토콜의 "기능적 간극(functionality gap)"을 해결하는 데 있다고 주장한다. 양자 측정 역할과 의미론적 해석 역할을 분리함으로써, 제안된 프로토콜은 임계값 결정이 사후 처리 단계가 아닌 직접적인 술어인 이상적인 고전적 TPSI 정의와 일치한다. 저자들은 이 구조가 최근의 다른 연구들에서 사용되는 양자 호모모픽 암호화(QHE)의 복잡성을 피하면서, 단일 광자 회전과 경량 클래식 사후 처리 단계(OLE 및 가드형 회로)에만 의존한다는 점을 강조한다. 저자들은 이 설계가 TP가 교집합의 크기를 알 수 없어야 하는 다자간 환경에서 더 높은 프라이버시 보호 접근 방식을 제공한다고 주장한다. 결론적으로, 이 프레임워크는 유연하여 가중치 또는 비율 기반 임계값으로 확장될 가능성이 있으나, 현재는 반-정직 TP 모델 하에서 작동함을 밝히며 논문을 마무리한다.