💻 computer science

Fuzzy PSI from Symmetric Primitives with Exact Logarithmic Dependence on Distance Threshold

본 논문은 오직 의무적 전송(oblivious transfer)과 대칭키 프리미티브만을 사용하여 거리 임계값 $\delta$ 에 대해 최적의 로그 의존성을 달al성함으로써, 비용이 많이 드는 동형 암호를 사용할 필요를 없애고 런타임 및 통신 측면에서 기존의 최첨단 솔루션들을 크게 능가하는 일반적인 $L_p$ 거리에 대한 새로운 퍼지 사적 집합 교집합(Fuzzy Private Set Intersection, FPSI) 프로토콜을 제시한다.

원저자: Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang

게시일 2026-06-16

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

두 사람, **앨리스(Alice)**와 **밥(Bob)**이 서로의 전체 목록을 보여주지 않고도 각자의 컬렉션에 "유사한" 아이템이 있는지 알아내고자 한다고 가정해 봅시다.

문제점: 표준적인 게임에서는 두 아이템가 정확히 일치해야만 매칭됩니다 (예: 둘 다 "빨간 사과"를 가지고 있는 경우).
반전 (Fuzzy PSI): 이 새로운 게임에서 그들은 "충분히 가까운" 아이템을 매칭하고자 합니다. 예를 들어, 앨리스는 "빨간 사과"를 가지고 있고 밥은 "약간 멍든 빨간 사과"를 가지고 있다면, 이들은 매칭된 것으로 간 만큼 합니다. 규칙은 다음과 같습니다: "만약 우리 아이템 사이의 차이가 특정 거리(임계값/Threshold)보다 작다면, 우리는 매칭된다."

이 과정을 보안을 유지하며 수행하는 것이 과제입니다. 앨리스는 밥의 전체 목록을 알 수 없어야 하며, 밥 또한 앨리스의 전체 목록을 알 수 없어야 합니다. 그들은 오직 어떤 아이템들이 충분히 가까운지만을 알고 싶어 합니다.

기존 방식: 느리고 비싼 탐색

기존의 "퍼지 매칭(Fuzzy Matching)" 방식에는 두 가지 큰 문제가 있었습니다.

"선형적(Linear)" 함정: 만약 "가까움"의 임계값이 크다면 (예: 100 단위), 컴퓨터는 모든 아이템에 대해 100개의 서로 다른 가능성을 확인해야 했습니다. 이는 마치 모든 짚단을 하나하나 확인하며 바늘을 찾는 것과 같았습니다. 임계값이 커질수록 더 느려졌습니다.
"중장비" 문제: 이를 보안적으로 구현하기 위해, 기존 방식들은 매우 무겁고 느린 암호화 도구들(예: 가산 동형 암호)을 사용했습니다. 이것은 마치 자전거로 충분할 상황에서 거대하고 연료를 많이 소모하는 트럭을 사용하여 비밀 메시지를 보내는 것과 같습니다.

새로운 돌파구: "접두사(Prefix)" 지름길

이 논문은 더 빠르고, 가볍고, 스마트하게 이 게임을 플레이하는 새로운 방법을 소개합니다.

1. "우편번호" 비유 (접두사/Prefixes)

숫자의 범위(예: 10, 11, 12... 100까지 확인하는 것)를 일일이 확인하는 대신, 저자들은 **접두사(Prefixes)**라는 기술을 사용합니다.

당신이 도시에서 집을 찾고 있다고 상상해 보세요.

기존 방식: 당신은 친구가 살고 있는지 확인하기 위해 동네의 모든 문을 두드립니다.
새로운 방식: 당신은 우편번호를 봅니다. 만약 당신의 친구가 "10001"에 살고 있다면, 당신은 해당 접두사를 가진 집들만 확인하면 됩니다. 도시 전체를 확인할 필요가 없습니다.

저자들은 어떤 "범위"의 숫자(임계값)라도 단 몇 개의 "우편번호"(접두사)로 분해될 수 있다는 점을 깨달았습니다.

마법 같은 효과: 이 접두사들을 확인하는 데 걸리는 시간은 임계값의 크기에 따라 늘어나지 않고, 로그(logarithmic) 함수를 따르며 증가합니다.
- 임계값이 두 배가 되어도, 작업량은 아주 조금만 늘어납니다.
- 임계값이 100배 커져도, 작업량은 두 배 정도밖에 늘어나지 않습니다.
- 비유: 이것은 도서관에서 책을 찾는 것과 같습니다. 모든 책을 확인하는 것은 영원히 걸리겠지만, 선반의 라벨(접두사)을 확인하는 것은 선반에 책이 얼마나 많든 상관없이 몇 초면 끝납니다.

2. "가벼운" 도구들 (대칭 키 프리미티브/Symmetric Primitives)

저자들은 무거운 "트럭"(비싼 암호화)을 "자전거"(대칭 키 프리미티브 및 의사 전송/Oblivious Transfer)로 교체했습니다.

의사 전송 (Oblivious Transfer, OT): 웨이터가 당신이 무엇을 골랐는지 알지 못하고, 당신 또한 웨이터가 무엇을 골랐는지 알지 못하는 상태에서, 두 가지 비밀 메뉴 중 하나를 당신에게 주는 상황을 상상해 보세요. 저자들은 정보를 보안적으로 교환하기 위해 이 기술을 사용합니다.
결과: 이 시스템은 전적으로 이러한 가볍고 빠른 도구들로 구축되었습니다.

두 가지 시나리오: 작은 방 vs 거대한 홀

이 논문은 데이터가 얼마나 "밀집되어 있는지"(차원/dimensionality)에 따라 두 가지 다른 전략을 제공합니다.

시나리오 A: 낮은 차원 (아파트 가정)

설정: 사람들이 서로 멀리 떨어져 있는(임계값의 2배 이상) 작은 방을 생각해보세요.
전략: 이들은 **공간 해싱(Spatial Hashing)**을 사용합니다. 방을 격자 모양의 타일로 나누는 것을 상상해 보세요. 만약 두 사람이 가깝다면, 그들은 반드시 같은 타일이나 인접한 타일에 있어야 합니다. 프로토콜은 오직 이 특정 타일들만을 확인합니다.
혁신: 저자들은 이 격자 시스템을 새로운 "접두사" 지름길 및 특수한 "동등성 확인" 도구(ECSS)와 결합했습니다. 이를 통해 모든 쌍을 일일이 확인하지 않고도 즉각적으로 매칭을 찾아낼 수 있습니다.

시나리오 B: 높은 차원 (분리 가정)

설정: 다차원의 거대한 창고를 생각해보세요. 고차원에서는 공간을 격자로 나누면 너무 많은 빈 타일이 생기는 현상("차원의 저주")이 발생합니다.
전략: 이들은 **분산 ID 생성(Distributed ID Generation)**을 사용합니다. 격자 대신, 각 아이템에 위치에 기반한 고유한 "ID 카드"를 부여합니다.
혁신: 저자들은 이 "접두사" 기술을 사용하여 이러한 ID를 안전하게 생성하는 새로운 방법을 만들었습니다. 거대한 창고에서도, 실제 위치를 드러내지 않으면서도 두 아이템이 가까우면 ID가 일치하도록 이 ID들을 생성할 수 있습니다.

"비밀 소스": 등가 조건 합 (Equality Conditional Sum)

이들의 발명 핵심은 **등가 조건 합(Equality Conditional Sum, ECSS)**이라는 새로운 수학적 도구입니다.

작동 원리: 앨리스와 밥이 모두 숫자 목록을 가지고 있다고 가정해 봅시다. 그들은 특정 조건이 충족될 때만 숫자를 더하고 싶습니다 (예: "접두사가 일치하는 경우에만 숫자를 더한다").
마법: 그들은 서로의 숫자를 드러내지 않고도 이 덧셈을 안전하게 수행할 수 있습니다. 만약 접두사가 일치하지 않으면 결과는 그저 무작위 노이즈가 됩니다. 만약 접두사가 일치하면, 결과는 정확한 합계가 됩니다. 이를 통해 그들은 실제 값을 전혀 보지 않고도 아이템이 가까운지 확인할 수 있습니다.

결과: 엄청난 속도 향상

저자들은 작동하는 버전의 시스템을 구축하여 기존의 가장 뛰어난 방법들과 테스트했습니다.

속도: 이 시스템은 기존 최적의 방식보다 최대 43.7배 더 빠릅니다.
데이터 사용량: 네트워크를 통해 전송되는 데이터 양이 최대 31.3배 적습니다.
확장성: 다른 시스템들은 데이터 세트가 매우 커지면 작동이 멈추거나(메모리 부족) 무너졌지만, 이 시스템은 원활하게 계속 실행되었습니다.

요약

요약하자면, 이 논문은 "접두사"를 사용하여 "퍼지 매칭" 문제를 다음과 같이 해결합니다:

느리고 무거운 암호화를 빠르고 가벼운 도구로 교체했습니다.
"접두사"(우편번호와 같은)를 사용하여 느린 선형 탐색을 빠른 로그 탐색으로 전환했습니다.
두 당사자가 비밀을 드러내지 않고도 근접성을 확인할 수 있는 새로운 "비밀 합" 도구를 만들었습니다.

그 결과, 이 시스템은 거대한 규모의 프라이버시 보호 데이터 매칭을 처음으로 실용화하여, 대규모의 프라이빗 데이터셋에서 "유사한" 아이템을 거의 즉각적으로 찾아낼 수 있게 되었습니다.

기술 요약: 대칭형 프리미티브를 이용한 거리 임계값에 대한 정확한 로그 의존성을 갖는 퍼지 PSI

문제 정의
퍼지 개인 집합 교집합(Fuzzy Private Set Intersection, FPSI)은 $d$ 차원 벡터의 집합 $Q$ 를 가진 송신자와 집합 $W$ 를 가진 수신자가, $q \in Q$ 에 대해 $\text{dist}(q, w) \le \delta$ 를 만족하는 $w \in W$ 가 존재함을 식별할 수 있게 하되, 추가적인 정보를 드러내지 않도록 한다. 표준 PSI는 높은 효율성을 달ener왔으나, 기존의 FPSI 프로토콜은 상당한 이론적 및 실무적 병목 현상에 직면해 있다. 기존 연구들은 일반적으로 거리 임계값 $\delta$ 에 대해 선형 스케일링( $O(\delta)$ )을 보이거나, $L_\infty$ 거리에 대해서만 폴리 로그 의존성을 달성한다. 일반적인 민코프스키 거리( $L_p, p \in [1, \infty]$ )를 지원하면서 $\delta$ 에 대해 로그 의존성을 달성하는 프로토콜들은 비용이 많이 드는 가법 동형 암호(Additive Homomorphic Encryption, AHE)에 의존하거나, 보안 결함 및 차원 $d$ 에 대한 지수적 복잡도 항을 겪어왔다. 본 연구의 목표는 오직 효율적인 대칭 키 프리미티브만을 사용하여 일반적인 $L_p$ 거리에 대해 $\delta$ 에 대한 정확한 로그 의존성을 달성하는 것이다.

방법론 및 핵심 기술
저자들은 AHE와 같은 공개키 연산을 피하고, 오직 옵티컬 트랜스퍼(OT)와 대칭 키 프리미티브로만 구축된 새로운 FPSI 프로토콜을 제안한다. 이 구성은 apart 가정(저차원 설정에 적합)과 separate 가정(고차원 설정에 적합)이라는 두 가지 주요 가정을 기반으로 한다.

접두사 표현 및 구간 테스트 (Prefix Representation and Interval Testing):
핵심 혁신은 모든 정수 $[q_k - \delta, q_k + \delta]$ 를 열거하는 방식(비용 $O(\delta)$ )을 $O(\log \delta)$ 개의 접두사를 사용하는 접두사 표현 방식으로 대체하는 것이다. 이를 통해 차원당 구간 테스트 비용을 $O(\log \delta)$ 로 줄인다.
등가 조건 합/내적 공유 (Equality Conditional Sum/Inner-Product Share, ECSS/ECIPS):
송신자의 입력을 드러내지 않으면서 접두사 매칭에 필요한 상호작용을 처리하기 위해, 저자들은 두 가지 새로운 암호학적 프리미티브를 도입한다:

등가 조건 합 공유 (ECSS): $L_\infty$ 거리에 사용된다. 이는 입력 벡터 간의 일치(equality match)를 조건으로 값의 합을 계산할 수 있게 하며, 결과의 비밀 공유(secret shares)를 출력한다.
등가 조건 내적 공유 (ECIPS): 일반적인 $L_p$ 거리에 사용된다. 이는 일치를 조건으로 내적을 계산하며, 특정 항을 드러내지 않고 이항 전개를 통해 $|w_k - q_k|^p$ 를 계산할 수 있게 한다.
이 두 프리미티브는 OT, 옵리비어스 프로그래머블 PRF(OPPRF), 그리고 Permute+Share (PS) 프로토콜을 사용하여 효율적으로 구현된다.

다중 요소 처리 (Handling Multiple Elements):

저차원 ( $L_\infty$ 및 $L_p$ ): 프로토콜은 쌍별 비교 횟수를 줄이기 위해 공간 해싱(spatial hashing, 그리드 셀)과 Cuckoo 해싱을 활용한다. 저자들은 빈 빈(bin)에 더미 값을 넣을 필요를 없애는 공유 OPRF(sOPRF)를 사용한 최적화를 도입하여, 송신자의 해싱 위치를 숨기고 특정 구성에서 전역 순열 단계가 필요하지 않도록 한다.
고차원 ( $L_\infty$ 및 $L_p$ ): 공간 해싱의 $O(2^d)$ 비용을 피하기 위해, 저자들은 분산 ID 생성(Distributed ID Generation, dIDG) 프로토콜을 사용한다. 이 프로토콜은 가까운 요소들이 ID를 공유하도록 하는 고유 ID를 생성한다. 저자들은 [DZL25] 등에서 나타난 충돌 누출(collision leakage)과 관련된 보안 결함을 식별하고, sOPRF와 ECSS를 사용하는 안전한 대칭 키 기반의 dIDG를 제안한다.

주요 기여

새로운 프리미티브: $\delta$ 에 대한 정확한 로그 의依存성을 가지며 오직 대칭 프리미티브만을 사용하여 효율적인 퍼지 매칭을 가능하게 하는 ECSS 및 ECIPS를 도입하였다.
최적의 복잡도: 일반적인 $L_p \in [1, \infty]$ 거리에 대해 $\delta$ 에 대해 엄격한 로그 복잡도 $O(d \log \delta)$ 를 달성한 최초의 FPSI 프로토콜이다. 이는 길이 $O(\delta)$ 인 구간 내의 값을 구별하는 데 $\Omega(\log \delta)$ 비트의 정보가 필요하다는 점에서 이론적으로 최적이다.
보안 및 효율성: AHE에 대한 의존성을 제거하고 이를 OT 및 대칭 키 연산으로 대체하였다. 또한 마스크 재사용 및 충돌 누출 문제를 겪었던 기존의 접두사 기반 프로토콜(예: [DZL25])의 보안 취약점을 식별하고 수정하였다.
확장 가능한 구성: 저차원(공간 해싱 사용)과 고차원(dIDG 사용) 설정을 위한 별도의 구성을 제공하며, 두 경우 모두 최적의 점근적 복잡도를 달성한다.

실험 결과
저자들은 제안된 프로토콜을 구현하여 최신 기술([GQL+24], [DZL25], [BGMP25])과 비교하였다.

성능: 제안된 프로토콜은 기존 기술보다 성능이 월등히 뛰어나다. 저차원 설정에서, 제안된 프로토콜은 기존 기술 대비 최대 43.7배 빠른 실행 시간과 31.3배 낮은 통신 오버헤드를 달성했다.
확장성: [GQL+24] 및 [DZL25]와 같은 기존 연구들이 고차원 설정에서 집합 크기 $2^{16}$ 에서 메모리 오버플로를 겪은 반면, 제안된 프로토콜은 동일한 구성 하에서 성공적으로 실행되었다.
임계값 의존성: 실험을 통해 제안된 프로토콜의 실행 시간 및 통신 비용이 $\delta$ 에 따라 로그 스케일링됨을 확인하였으며, 이는 기존의 선형 의존성 프로토콜에서 관찰된 선형 스케일링과 대조된다.

의의
본 논문은 FPSI를 위한 최적의 임계값 스케일링에 대한 이론적 돌파구를 제시하며, 비용이 많이 드는 공개키 암호 없이도 일반적인 $L_p$ 거리에 대해 정확한 로그 $\delta$ 의존성이 달성 가능함을 입증한다. 실무적으로, 이는 거리 임계값 및 차원과 관련된 효율성 병목 현상을 제거함으로써 유전체 서열 매칭, 유사 이미지 검색, 탈취된 자격 증명 탐지 등 퍼지 매칭을 요구하는 도메인에서 확장 가능한 FPSI 애플리케이션의 실현 가능성을 높인다.