Efficient Fuzzy Private Set Intersection from Secret-shared OPRF

제시된 논문 "Efficient Fuzzy Private Set Intersection from Secret-shared OPRF"에 대한 상세한 기술 요약입니다.

1. 문제 정의 (Problem)

**퍼지 프라이빗 세트 인터섹션 (Fuzzy PSI, FPSI)**은 송신자가 가진 집합 $Q$와 수신자가 가진 집합 $W$에 대해, 정확한 일치뿐만 아니라 거리 함수 (예: $L_p$ 거리) 하에서 임계값 $\delta$ 이내에 있는 항목들 ($dist(q, w) \le \delta$) 의 교집합을 안전하게 계산하는 프로토콜입니다. 이는 생체 인증 (지문, 얼굴 인식) 등 환경적 변이나 노이즈로 인해 정확한 매칭이 불가능한 상황에서 필수적입니다.

기존 연구들은 다음과 같은 한계를 가지고 있었습니다:

• 고비용의 암호화: 대부분의 기존 선형 복잡도 프로토콜 (Gao et al., Dang et al.) 은 덧셈 동형 암호 (AHE, 예: ElGamal, Paillier) 에 크게 의존하여 실제 실행 시 계산 및 통신 오버헤드가 매우 컸습니다.
• 비효율적인 복잡도: 일부 프로토콜은 요소의 차원 (dimension) 에 대해 지수적 복잡도를 가지거나, 거리 임계값 $\delta$에 대해 선형 의존성을 가져 대규모 데이터나 큰 $\delta$에서 비실용적이었습니다.

2. 방법론 (Methodology)

이 논문은 공개키 암호 연산을 최소화하고 경량 대칭키 연산을 주로 활용하여 효율성을 극대화하는 새로운 FPSI 프로토콜을 제안합니다.

핵심 구성 요소

1. 비관적 프로그래밍 가능한 PRF (so-OPPRF):

   • 기존 OPRF(비관적 의사 난수 함수) 의 변형으로, 송신자와 수신자가 각각 PRF 출력의 **비밀 공유 (secret shares)**를 받도록 설계되었습니다.
   • **OKVS(Oblivious Key-Value Store)**와 **비밀 공유 OPRF (so-OPRF)**를 결합하여 구현됩니다. 송신자가 프로그래밍된 점들에 대한 값을 인코딩하고, 수신자가 이를 디코딩하여 비밀 공유된 값을 얻습니다. 이는 수신자에게 추가적인 정보 (부분 매칭 등) 를 누설하지 않으면서도 효율적인 프로그래밍을 가능하게 합니다.

2. 모듈러 퍼지 매핑 (Modular Fuzzy Mapping):

   • 국소 매핑 (Local Mapping): 각 파티는 자신의 집합 요소를 고유한 로컬 ID 로 매핑합니다. 이때 $L_\infty$ 거리를 기반으로 $\delta$ 반경 내의 모든 점이 동일한 값을 가지도록 설계됩니다.
   • 전역 매핑 (Global Mapping): **비밀 공유 입력 OPRF (si-OPRF)**를 사용하여, 송신자와 수신자가 각자의 로컬 매핑 값을 결합하여 최종적인 전역 ID 를 생성합니다. 이 과정에서 $so$-OPPRF 와 $si$-OPRF 를 조합하여, 로컬 매핑 시 발생할 수 있는 중첩 (overlap) 으로 인한 정보 누설을 방지하고 정확한 매칭 ID 를 보장합니다.

3. 정제 필터링 (Refined Filtering):

   • 퍼지 매핑으로 생성된 동일한 ID 를 가진 후보 쌍에 대해, 실제 거리가 $\delta$ 이내인지 확인합니다.
   • $so$-OPPRF 를 활용하여 거리 계산에 필요한 값을 비밀 공유 형태로 얻고, **비밀 공유 평등성 테스트 (PEQT)**를 통해 정확히 0 인지 확인한 후, **비관적 전송 (OT)**을 통해 최종 교집합을 추출합니다.

4. 접두사 최적화 (Prefix Optimization):

   • 큰 거리 임계값 ($\delta$) 에 대한 효율성을 높이기 위해 접두사 표현 (Prefix Representation) 기법을 도입했습니다.
   • 전체 구간 $[q-\delta, q+\delta]$를 프로그래밍하는 대신, 해당 구간을 덮는 $O(\log \delta)$개의 접두사만 프로그래밍합니다. 이를 통해 통신 및 계산 복잡도를 $\delta$에 대한 선형에서 **로그 ($O(\log \delta)$)**로 감소시켰습니다.

3. 주요 기여 (Key Contributions)

1. 새로운 원시 기법 (so-OPPRF): 출력을 비밀 공유 형태로 분산하는 새로운 OPRF 변형을 제안하여, 퍼지 매핑 및 PSI 프로토콜의 핵심 빌딩 블록으로 활용합니다.
2. 선형 복잡도 달성: 집합 크기 ($m, n$), 차원 ($d$), 거리 임계값 ($\delta$) 에 대해 선형 복잡도를 가지며, 고비용인 동형 암호 대신 경량 대칭키 연산을 주로 사용합니다.
3. 접두사 기반 최적화: 큰 $\delta$ 환경에서 복잡도를 로그 수준으로 낮추는 최적화 기법을 통합했습니다.
4. 광범위한 평가: 기존 최첨단 (SOTA) 프로토콜 (Gao et al. '24, Dang et al. '25) 과 비교한 실험을 통해 성능 우위를 입증했습니다.

4. 실험 결과 (Results)

실험 환경 (AMD EPYC 64-core, 10Gbps 네트워크) 에서 $L_1, L_2, L_\infty$ 거리 척도에 대해 다양한 파라미터 ($m=n=2^8 \sim 2^{16}$, $d=4 \sim 16$, $\delta=16 \sim 32$) 로 평가되었습니다.

• 성능 향상:
  • 실행 시간: 기존 Gao et al. 대비 12~145 배, Dang et al. 대비 9~80 배 빠른 속도를 기록했습니다.
  • 통신 비용: Gao et al. 대비 3~8 배, Dang et al. 대비 5~19 배 감소했습니다.
  • 특히 대규모 입력 ($m=n=2^{16}$) 과 큰 차원 ($d=16$) 에서 성능 차이가 극명하게 나타났습니다.
• 접두사 최적화 효과:
  • 큰 $\delta$ (예: 1024) 환경에서 기존 비접두사 프로토콜 대비 통신 비용을 11 배 줄이고 실행 시간을 약 절반으로 단축했습니다.
  • Dang et al. (CCS'25) 와 비교하여 통신 효율성 710 배, 계산 효율성 1338 배의 개선을 보였습니다.

5. 의의 및 결론 (Significance)

이 논문은 퍼지 프라이빗 세트 인터섹션 분야에서 실용적인 효율성을 크게 개선한 획기적인 연구입니다.

• 암호학적 혁신: 고비용인 공개키 암호 (동형 암호) 에 대한 의존성을 제거하고, 경량 대칭키 연산과 비밀 공유 기술을 효과적으로 결합하여 실제 배포 가능한 프로토콜을 제시했습니다.
• 확장성: 고차원 데이터와 큰 거리 임계값을 처리할 수 있어, 생체 인증, 위치 기반 서비스, 의료 데이터 분석 등 다양한 고차원 데이터 프라이버시 보호 응용 분야에 직접 적용 가능합니다.
• 모듈러 설계: 제안된 $so$-OPPRF 는 퍼지 PSI 외에도 다른 프라이버시 보호 계산 작업에 독립적으로 유용한 구성 요소로 활용될 수 있습니다.

결론적으로, 이 연구는 퍼지 PSI 의 이론적 복잡도 한계를 넘어, 실제 시스템에서의 실행 속도와 통신 비용을 획기적으로 낮춤으로써 상용화 가능성을 크게 높였습니다.