💻 computer science

Efficient Fuzzy PSI under One-Sided Assumptions

본 논문은 일방향 가정을 바탕으로 일반적인 $L_p$ 거리에 대해 경량 대칭키 프리미티브와 접두사 트라이(prefix trie) 기법을 활용하여 $O(\log \delta)$ 복잡도를 달성함으로써, 계산 속도와 통신 오버헤드 측면 모두에서 기존의 최첨단 연구들을 크게 능가하는 최초의 구체적으로 효율적인 퍼지 프라이빗 집합 교집합(fuzzy private set intersection) 프로토콜을 소개한다.

원저자: Xinpeng Yang, Meng Hao, Yanxue Jia, Chenkai Weng, Yonggang Wen, Tianwei Zhang

게시일 2026-08-19

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Xinpeng Yang, Meng Hao, Yanxue Jia, Chenkai Weng, Yonggang Wen, Tianwei Zhang

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

디지털 시대에는 두 조직이 서로의 모든 비밀을 드러내지 않으면서도 공통점을 찾아야 하는 경우가 많습니다. 특정 질환을 가진 환자 명단을 보유한 병원과 자원봉사자 명단을 보유한 연구소가 있다고 가정해 봅시다. 두 기관은 자원봉사자 중 누가 환자인지도 알고 싶어 하지만, 어느 쪽도 자신의 전체 명단을 넘겨주고 싶어 하지 않습니다. 이는 나머지 인원의 개인정보를 노출할 수 있기 때문입니다. 표준 컴퓨터 프로토콜은 이러한 정확한 일치 문제를 효율적으로 해결할 수 있지만, 데이터가 약간 지저분할 때는 실패합니다. 현실 세계에서는 이름이 오타가 나거나, 위치가 약간 어긋나거나, 생체 인식 스캔 결과가 매일 다를 수 있습니다. 병원의 기록에는 "John Smith"라고 되어 있고 자원봉사자의 기록에는 "Jon Smyth"라고 되어 있다면, 표준 시스템은 이를 일치하지 않는 것으로 간주하지만, 실제로는 동일 인물일 수 있습니다. 여기서 "퍼지(fuzzy)" 매칭이 등장합니다. 이는 이러한 근사적인 연결을 찾기 위해 설계된 방법입니다. 그러나 이를 보안을 유지하며 수행하는 것은 매우 어렵습니다. 만약 시스템이 모든 이름의 가능한 모든 변형을 다른 모든 변형과 비교하려고 시도한다면, 교환되는 데이터의 양이 너무 방대해져서 프로세스가 멈추거나, 혹은 매우 무거운 수학적 장치를 필요로 하여 일상적인 사용에 부적합해집니다.

연구팀은 이제 이 퍼지 매칭을 빠르고 가볍게 수행할 수 있는 새로운 방법을 개발했습니다. 그들의 연구는 두 당사자 중 한 쪽만이 자신의 데이터를 배치하는 방식에 대해 엄격한 규칙을 따를 필요가 있고, 다른 한 쪽은 어떤 무질서한 순서의 데이터라도 가질 수 있는 시나리오에 초점을 맞춥니다. 이러한 완화된 조건 하에서 이 문제를 해결하려는 이전의 시도들은 무겁고 느린 암호화 도구에 의존하거나, 두 당사자 모두 완벽하게 정리된 데이터를 가져야만 했습니다. 이는 현실에서는 거의 불가능한 일입니다. 싱가포르와 미국의 연구 기관들로부터 온 신펑 양(Xinpeng Yang)과 동료들이 만든 이 새로운 방법은 오직 단순하고 빠른 구성 요소만을 사용하여 동일한 목표를 달as 성합니다. 그들은 이러한 비교에 필요한 시간과 데이터를 엄청난 폭으로 줄였으며, 이를 통해 많은 실생활 환경에서 보안이 유지되는 근사 매칭을 처음으로 가능하게 만들었습니다.

이 성과의 핵심은 연구진이 데이터 포인트 사이의 "거리"를 처리하는 방식에 있습니다. 이 문맥에서 거리는 두 정보가 얼마나 다른지를 나타내는 척도로, 예를 들어 이름의 글자가 몇 개 다른지 또는 GPS 좌표가 얼마나 떨어져 있는지와 같습니다. 목표는 거리가 특정 임계값보다 작은 쌍을 찾는 것입니다. 연구진은 기존의 방법들이 데이터 포인트의 모든 가능한 변형을 확인하려고 시도했기 때문에, 허용된 차이가 커질수록 탐색 공간이 폭발적으로 증가한다는 점을 깨달았습니다. 이를 해결하기 위해 그들은 스마트 필터처럼 작동하는 기술을 도입했습니다. 모든 가능성을 일일이 확인하는 대신, 시스템은 데이터를 트리 구조로 조직하여 방대한 양의 무관한 정보를 즉시 건너뛸 수 있게 합니다. 이 변화는 계산 노력을 지수적으로 증가하는 수준에서 로그 단위로 성장하는 수준으로 줄였습니다. 실질적으로 이는 데이터 포인트 간의 허용된 차이가 두 배나 세 배가 되더라도, 검사를 실행하는 데 걸리는 시간은 거의 늘어나지 않음을 의미합니다.

연구팀은 자신들의 새로운 프로토콜을 현재 사용 가능한 최고의 기존 방법들과 테스트했습니다. 결과는 극적이었습니다. 2024년의 최근 프로토콜과 비교했을 때, 새로운 시스템은 최대 239배 더 빨랐고 통신 대역폭은 최대 20배 적게 사용했습니다. 2025년 방식에 대해서는 속도가 518배 빨라졌고 데이터 전송량은 63배 감소했습니다. 또 다른 2025년 구조물과의 특정 비교에서는 새로운 시스템이 거의 5,000배 더 빨랐으며 통신량은 282배 적게 필요했습니다. 이 수치들은 단지 이론적인 것이 아니었습니다. 연구진은 전체 시스템을 구현하여 다양한 데이터 크기와 설정에 걸쳐 광범한 실험을 수행했습니다. 그들은 자신들의 접근 방식이 송신자나 수신자 중 어느 쪽이 정리된 데이터를 가지고 있더라도 작동하며, 단순한 거리 측정뿐만 아니라 다양한 유형의 거리 측정을 지원함을 확인했습니다.

그들의 작업에서 핵심적인 혁신은 "단방향(one-sided)" 가정을 처리할 수 있는 능력이었습니다. 많은 기존 보안 시스템에서는 혼란을 피하기 위해 두 당사자 모두 데이터 포인트가 충분히 떨어져 있어야 한다는 것과 같은 엄격한 규칙에 동의해야 했습니다. 이는 데이터가 군집을 이루거나 무작위 패턴으로 들어오는 실제 상황에서는 흔히 불가능한 일입니다. 새로운 방법은 한 쪽이 어느 정도 정리된 데이터셋을 가지고 있기만 하면 되며, 다른 쪽은 완전히 임의적이고 무질서한 데이터를 가질 수 있습니다. 이러한 유연성은 한 엔티티는 알려진 위치에 대한 구조화된 데이터베이스를 가지고 있고, 다른 엔티티는 비구조화된 사용자 입력을 스트림 형태로 받는 접촉 추적이나 위치 기반 서비스와 같은 시나리오에 이 기술을 적용할 수 있게 합니다. 연구진은 빠르고 효율적인 표준 암호화 도구인 경량 대칭 키 기술에만 의존함으로써, 유사한 노력들을 정체시켰던 무겁고 느린 수학적 연산들을 피했습니다.

연구진은 또한 데이터가 희소한 경우, 즉 포인트들이 군집을 이루지 않고 흩어져 있는 경우 시스템을 더욱 효율적으로 만드는 방법을 탐구했습니다. 이러한 경우, 매칭 과정에서 두 당사자의 역할을 바꿈으로써 작업 부하를 더욱 균형 있게 맞추고 성능을 향ло 개선할 수 있다는 것을 발견했습니다. 이러한 적응성은 시스템이 전체적인 재설계 없이도 다양한 유형의 애플리케이션에 맞춰 조정될 수 있음을 시사합니다. 이 연구는 이론적으로 견고할 뿐만 아니라 실질적으로도 빠르게 작동하는 보안 및 프라이버시 보호 시스템을 구축하는 것이 가능하다는 것을 보여줍니다.

이 연구의 영향은 단순히 속도를 넘어섭니다. 퍼지 매칭을 효율적으로 만듦으로써, 연구진은 더 정교한 프라이버시 보호 애플리케이션을 위한 문을 열었습니다. 프라이버시 유출을 우려하거나 매칭 과정이 너무 느려서 데이터 공유를 기피해 왔던 조직들은 이제 보안이 유지되는 협업을 고려할 수 있습니다. 의료 연구를 위해 환자 기록을 매칭하든, 생체 인식 템플릿을 노출하지 않고 사용자 신원을 검증하든, 혹은 카탈로그의 내용을 드러내지 않고 대규모 카탈로그에서 유사한 항목을 찾든, 진입 장벽이 크게 낮아졌습니다. 이 연구는 적절한 알고리즘적 접근 방식이 있다면, 프라이버시와 성능 사이의 절충안을 해결할 수 있으며, 데이터가 불완전하거나 노이즈가 섞여 있더라도 보안이 유지된 채로 흐를 수 있음을 증명합니다.

결론적으로, 이 논문은 수년간 지속되어 온 문제, 즉 속도를 희생하거나 비현적인 조건을 요구하지 않으면서 프라이비시가 적용된 데이터에서 근사 매칭을 찾는 방법에 대한 구체적인 해결책을 제시합니다. 연구진은 단순히 새로운 아이디어를 제안한 것이 아니라, 그것을 직접 구축하고 테스트하여 기존의 모든 것보다 수십 배 이상의 성능을 발휘함을 보여주었습니다. 그들의 작업은 문제의 근본적인 논리를 개선하는 것이 단순히 더 많은 컴퓨팅 파워를 쏟아붓는 것보다 훨씬 강력하다는 것을 보여주는 증거입니다. 호기심 많은 관찰자에게 이 결과는, 마치 무겁고 투박한 기계라기보다는 정밀하고 효율적인 도구처럼 느껴지는, 불완전하고 무질서한 실제 데이터의 세계에서 바로 사용될 준비가 된 시스템으로 다가옵니다.

기술 요약: 일방향 가설 하의 효율적인 퍼지 PSI (Fuzzy PSI)

문제 정의

퍼지 프라이빗 셋 인터섹션(Fuzzy Private Set Intersection, PSI)은 송신자(sender)와 수신자(receiver)라는 두 당사자가 각자의 입력 집합에서 근사하게 일치하는 요소를 식별할 수 있게 합니다. 구체적으로, 거리 임계값 $\delta$ 와 거리 함수 $dist(\cdot, \cdot)$ 가 주어졌을 때, 수신자는 $dist(\mathbf{q}, \mathbf{w}) \le \delta$ 를 만족하는 수신자 요소 $\mathbf{w}$ 가 존재하는 송신자 요소 $\mathbf{q}$ 를 모두 알게 됩니다.

표준 PSI는 상당한 발전을 이루었으나, 퍼지 PSI는 효율성과 기저 가설의 강도 사이의 트레이드오프 문제에 직면해 있습니다. 일반적인 $L_p$ ( $p \in [1, \infty]$ ) 거리에 대한 기존 방식들은 대개 다음 두 가지 범주로 나뉩니다:

양방향 가설 (Two-sided assumptions): 양측의 입력이 강력한 기하학적 분리(예: 점들이 서로 $2\delta$ 또는 $4\delta$ 만큼 떨어져 있음)를 충족해야 하는 프로토콜입니다. 이는 효율적이지만, 노이즈가 있는 실제 데이터를 다루기에는 비현실적인 경우가 많습니다.
일방향 가설 (One-sided assumptions): 한쪽 당사자의 입력만이 분리 제약 조건을 충족해야 하며, 다른 쪽 당사자는 임의의 입력을 가질 수 있는 프로토콜입니다. 그러나 기존의 일방향 솔루션들은 무거운 암호화 프리미티브(예: 가산 동형 암호, AHE)에 의존하거나, 임계값 $\delta$ 에 따른 점근적 오버헤드가 매우 큽니다(예: $O(\delta)$ 또는 $O((\log \delta)^d)$ ).

본 논문이 해결하고자 하는 핵심 과제는 경량 대칭키 프리미티브만을 사용하여 일반 $L_p$ 거리에 대해 약한 일방향 가설 하에서 구체적으로 효율적인 퍼지 PSI 프로토콜을 구축하는 것입니다.

방법론

저자들은 **비밀 공유 기반의 은닉 프로그래머블 의사 난수 함수(secret-shared oblivious programmable pseudorandom functions, so-OPPRF)**와 **공간 해싱(Spatial Hashing)**을 기반으로 하고, 접두사 트라이(Prefix Trie) 기법으로 강화된 프레임워크를 제안합니다.

1. 다지점 퍼지 매칭 프리미티브 (Multi-Point Fuzzy Matching Primitives)

한쪽 당사자의 입력을 누출 없이 처리하기 위해, 저자들은 두 가지 가설 불필요(assumption-free) 다지점 퍼지 매칭 프로토콜을 도입합니다.

1-to- $n$ 매칭 (수신자가 임의의 점을 보유): 송신자는 자신의 단일 점 주변의 구간(interval)을 사용하여 so-OPPRF를 프로그래밍합니다. 합산된 쉐어(share)에서의 충돌로 인해 수신자가 송신자의 입력 분포를 추론하는 것을 방지하기 위해(이는 이전 연구에서의 누출 문제임), 저자들은 **등가 조건부 무작위화(Equality-conditional Randomization, EqRand)**를 도입합니다. 이 프리미티브는 매칭되지 않는 입력에 대해서는 비밀 쉐어를 재무작위화하면서도, 매칭되는 입력에 대해서는 올바른 합을 보존하여, 여러 수신자 점이 동일한 프로그래밍 구간에 매핑되더라도 프라이버시를 보장합니다.
$m$ -to-1 매칭 (송신자가 임의의 점을 보유): 역할이 반대입니다. 수신자는 자신의 단일 점 주변의 구간을 사용하여 so-OPPRF를 프로그래밍합니다. 송신자는 자신의 여러 점에 대해 함수를 평가합니다. 수신자가 송신자 측으로부터 합산된 값을 재구성하지 않으므로, 누출 문제는 자연스럽게 방지되며 EqRand는 필요하지 않습니다.

2. 일방향 가설 하의 퍼지 PSI

위의 프리미티브를 바탕으로, 저자들은 두 가지 특정 일방향 가설 하에서 완전한 $m$ -to- $n$ 퍼지 PSI 프로토콜을 구축합니다.

고유 셀 가설 (Unique Cell Assumption): 각 공간 셀(변의 길이가 $2\delta$ 인)에는 제약된 당사자의 점이 최대 하나만 포함됩니다.
고유 블록 가설 (Unique Block Assumption, 더 희소한 경우): 각 공간 셀은 제약된 당사자의 $L_\infty$ 볼(ball)과 최대 하나만 교차합니다.

프로토콜은 공간 해싱을 사용하여 공간을 분할합니다. 제약된 당사자는 자신의 점들과 셀 식별자로부터 유도된 키를 사용하여 so-OPPRF를 프로그래밍함으로써 충돌을 방지합니다. 제약되지 않은 당사자는 자신의 점들과 인접한 셀들에 대해 함수를 평가합니다. so-OPPRF를 사용하면 출력이 비밀 공유되므로, 어느 쪽 당사자도 상대방의 원시 데이터를 알 수 없습니다.

에는 접두사 트라이 최적화 (Prefix Trie Optimization)

이전 연구들에서 발견된 $\delta$ 에 따른 선형 또는 초선형 복잡도 문제를 해결하기 위해, 저자들은 접두사 트라이(Prefix Trie) 기 기법을 통합합니다.

메커니즘: 모든 점을 $[w - \delta, w + \delta]$ 구간 내에서 열거하는 대신( $O(\delta)$ 소요), PxTrie 알고리즘을 사용하여 구간을 $O(\log \delta)$ 개의 접두사 노드로 인코딩합니다.
차원별 필터링 (Dimension-by-Dimension Filtering): 이전 연구들은 $d$ 차원에 걸쳐 모든 접두사의 조합을 평가해야 했기에 $O((\log \delta)^d)$ 의 복잡도를 가졌습니다. 저자들은 타겟과 매칭되는 접두사가 차원당 최대 하나만 존재한다는 점을 이용하여 접두사를 차원별로 필터링하는 조건부 선택(Conditional Selection, ConSel) 프리미티브를 도입했습니다. 이를 통해 탐색 공간을 $O((\log \delta)^d)$ 에서 $O(d \cdot \log \delta)$ 로 줄였습니다.
결과: 이를 통해 일반 $L_p$ 거리에 대해 임계값 $\delta$ 에 대한 $O(\log \delta)$ 복잡도를 달성하였으며, 이는 이전의 $O((\log \delta)^d)$ 또는 $O(\delta)$ 바운드보다 크게 개선된 수치입니다.

3. 일반 $L_p$ 거리 처리

$L_p$ 거리( $p > 1$ )의 경우, 프로토콜은 차원별 거리 기여도의 $p$ 제곱( $|t|^p$ )을 so-OPPRF 값에 인코딩합니다. 당사자들은 이 쉐어들을 합산하고 전체 거리가 임계값 $\delta^p$ 이내인지 확인하기 위해 보안 다자간 계산(addition 및 multiplication)을 수행합니다.

주요 기여

일반 $L_p$ 를 위한 최초의 효율적인 일방향 퍼지 PSI: 본 논문은 경량 대칭키 프리미티브(so-OPPRF, OKVS, silent OT)만을 사용하여, 약한 일방향 가설 하에서 일반적인 $L_p \in [1, \infty]$ 거리에 대한 최초의 구체적으로 효율적인 프로토콜을 제시합니다.
$\delta$ 에 대한 로그 복잡도: 접두사 트라이 기법을 차원별 필터링 메커니즘과 결합함으로써, 임계값 $\delta$ 에 대한 지수적 의존성을 극복하고 $O(\log \delta)$ 복잡도를 달성하여 기존 연구들의 $O((\log \delta)^d)$ 또는 $O(\delta)$ 복잡도를 개선했습니다.
유연한 가설 지원: 본 프레임워크는 송신자 측(Sender-sided) 및 수신자 측(Receiver-sided) 설정을 모두 지원하며, 고유 셀(Unique Cell) 및 고유 블록(Unique Block) 가설을 지원합니다. 고유 블록 가설은 프로그래밍 비용과 평가 비용의 차이를 활용하여 역할을 반전시킴으로써 추가적인 최적화를 가능하게 합니다.
광범한 평가: 저자들은 프로토콜을 구현하여 기존의 최첨단 연구들(van Baarsen & Pu [31], Dang et al. [10], Bui et al. [6] 등)과 비교하였습니다.

실험 결과

평가는 AMD EPYC 9554 프로세서를 탑재한 서버에서 수행되었습니다. 결과는 통신 및 계산 측면에서 상당한 개선을 보여줍니다:

van Baarsen 및 Pu (EUROCRYPT'24) 대비: 계산 속도는 최대 239배 빠르며, 통신량은 최대 20배 적습니다.
Dang et al. (CCS'25) 대비: 계산 속도는 최대 518배 빠르며, 통신량은 63배 감소했습니다.
Bui et al. (ASIACRYPT'25) 대비: 계산 속도는 최대 4818배 빠르며, 통신량은 최대 282배 적습니다.

접두사 최적화 버전(Ours-Px)은 큰 $\delta$ 와 높은 차원에서 통신 측면에서 우수한 성능을 보이는 반면, 비최적화 버전(Ours)은 낮은 계산 오버헤드 덕분에 작은 임계값에서는 매우 경쟁력 있는 성능을 보입니다.

의의 및 주장

본 논문은 기하학적 가설의 강도와 퍼지 PSI 프로토콜의 효율성 사이의 오랜 트레이드오프 문제를 해결했다고 주장합니다. 일반적인 $L_p$ 퍼지 PSI가 가벼운 대칭키 프리미티브만을 사용하여 약한 일방향 가설 하에서도 달성 가능하다는 것을 입증함으로써, 본 연구는 데이터에 노이즈가 있고 엄격한 분리 가설을 보장할 수 없는 실제 시나리오에서 퍼지 PSI의 적용 가능성을 높였습니다.

저자들은 자신들의 프로토콜이 유사한 가설 하에서 기존 연구들을 크게 능가하며, 효율성 면에서 수십 배 이상의 개선을 이루었다는 점을 강조합니다. 접두사 트라이를 통한 차원별 필터링 메커니즘의 도입은 임계값에 대한 차원의 지수적 의존성을 깨뜨린 핵심적인 기술적 혁신으로 강조되며, 이를 통해 고차원 데이터와 큰 매칭 임계값에 대해서도 프로토콜이 확장 가능하도록 만들었습니다.