💻 computer science

Efficient Fuzzy PSI under One-Sided Assumptions

本論文は、片側仮定の下での一般的な $L_p$ 距離に対する、初の具体的に効率的なファジー・プライベート集合積（fuzzy private set intersection）プロトコルを導入するものであり、軽量な対称鍵プリミティブと接頭辞トライ木（prefix trie）の手法を活用することで $O(\log \delta)$ の計算量を実現し、計算速度と通信オーバーヘッドの両面において従来の最先端研究を大幅に上回る性能を実現している。

原著者： Xinpeng Yang, Meng Hao, Yanxue Jia, Chenkai Weng, Yonggang Wen, Tianwei Zhang

公開日 2026-08-19

📖 1 分で読めます☕ さくっと読める

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」であった場合、標準的なシステムは一致なしと判断しますが、実際には同一人物です。ここで、「ファジー（曖昧な）」マッチングの出番となります。これは、こうした近似的なつながりを見つけ出すために設計された手法です。しかし、これを安全に行うことは非常に困難です。もしシステムが、あらゆる名前のあらゆるバリエーションをあらゆる他のバリエーションに対して比較しようとすれば、交換されるデータ量は膨大になり、プロセスが停止してしまうか、あるいは非常に重厚な数学的仕組みが必要となり、日常的な使用には不向きなものになってしまいます。

研究チームは、このファジーマッチングを高速かつ軽量に実行する新しい方法を開発しました。彼らの研究は、二者のうち一方の側だけがデータの配置に関する厳格なルールに従う必要があり、もう一方はどのような混沌とした順序のデータであっても構わないというシナラリオに焦点を当てています。このような緩和された条件下でこの問題を解決しようとするこれまでの試みは、重くて遅い暗号技術に依存していたか、あるいは両者が完璧に整理されたデータを持っていることを要求していましたが、それは現実には滅多にないことです。シンガポールと米国の機関に所属するXinpeng Yang氏とその同僚らによって作成されたこの新手法は、単純で高速な構成要素のみを使用して同じ目標を達成しています。彼らは、これらの比較に要する時間とデータ量を大幅に削減することに成功し、多くの実世界の環境において、安全な近似照合を初めて実行可能なものにしました。

この成果の核心は、データポイント間の「距離」をどのように扱うかにあります。この文脈における距離とは、情報の違いの尺度であり、例えば名前の文字がいくつ異なるか、あるいはGPS座標がどれくらい離れているかといったものです。目標は、距離が特定の閾値よりも小さいペアを見つけることです。研究者たちは、従来のメソッドがデータポイントのあらゆる可能なバリエーションをチェックしようとしていたため、許容される差異が増えるにつれて探索空間が爆発的に増大していたことに気づきました。これを解決するために、彼らは「スマートなフィルター」として機能するテクニックを導入しました。すべての可能性を一つずつチェックする代わりに、システムはデータをツリー状の構造に整理することで、無関係な情報の巨大な塊を瞬時にスキップできるようにしました。この変更により、計算量は探索のサイズに対して指数関数的に増大するレベルから、対数関数的にしか増大しないレベルへと減少しました。実用的な観点から言えば、これはデータポイント間の許容される差異が2倍、3倍になったとしても、チェックを実行する時間はほとんど増えないことを意味します。

チームは、現在利用可能な最高水準の既存手法と比較して、新しいプロトコルのテストを行いました。その結果は劇的なものでした。2024年の最近のプロトコルと比較した場合、新システムは最大239倍速く、通信帯域幅を最大20分の1に抑えました。2025年の手法に対しては、速度向上は518倍に達し、データ転送量は63分の1に減少しました。また、別の2025年の構成との特定の比較においては、新システムは5,000倍近く速く、通信量は282分の1となりました。これらの数字は単なる理論値ではありませんでした。研究者たちはフルシステムを実装し、幅広いデータサイズと設定を用いて広範な実験を行いました。彼らは、送信者または受信者のどちらが整理されたデータを持っている場合でも、このアプローチが機能すること、そして単純な距離測定だけでなく様々な種類の距離測定をサポートしていることを確認しました。

彼らの研究における主要な革新は、「片側（ワンサイド）」の仮定を扱える能力にありました。多くの従来の安全なシステムでは、混乱を避けるためにデータポイントが十分に離れていることを保証するなど、両者が厳格なルールに同意する必要がありました。しかし、データがクラスター化したりランダムなパターンで発生したりする現実の世界では、これはしばしば不可能です。新メソッドは、一方の側がいくらか整理されたデータセットを持っていることさえ求め、もう一方は完全に恣意的で乱れたデータであっても構いません。この柔軟性により、一方が既知の場所の構造化されたデータベースを持ち、他方が非構造化されたユーザー入力をストリームとして送ってくるような、コンタクトトレーシングや位置情報ベースのサービスといったシナリオへの適用が可能になります。高速で効率的な標準的な共通鍵暗号技術のみに頼ることで、研究者たちは、同様の取り組みを停滞させてきた重くて遅い数学的操作を回避しました。

研究者たちはまた、データが疎である場合（つまり、ポイントが密集せず分散している場合）に、システムをさらに効率化する方法についても探求しました。これらのケースでは、マッチングプロセスにおける二者の役割を入れ替えることで、ワークロードをさらにバランスさせ、パフォーマンスを向上させられることを見出しました。この適応性は、システムが完全な再設計を必要とせずに、異なる種類のアプリケーションに合わせてチューニングできることを示唆しています。この研究は、理論的に健全であるだけでなく、実世界の展開に十分に速い、プライバシー保護型のシステムを構築することが可能であることを証明しています。

この研究の影響は、単なる速度の向上にとどまりません。ファジーマッチングを効率化することで、研究者たちは、より高度なプライバシー保護アプリケーションへの扉を開きました。プライバシー漏洩を恐れたり、マッチングプロセスが遅すぎたりするために、データの共有を避けてきた組織が、今や安全なコラボレーションを検討できるようになりました。医療研究のために患者記録を照合する場合でも、生体テンプレートを公開せずにユーザーの身元を確認する場合でも、あるいはカタログの内容を明かすことなく大規模なカタログ内の類似アイテムを見つける場合でも、参入障壁は大幅に下がりました。この研究は、適切なアルゴリズム的アプローチがあれば、プライバシーとパフォーマンスのトレードオフを解決できることを証明しており、データが不完全であったりノイズを含んでいたりする場合でも、安全にデータが流れることを可能にします。

結局のところ、この論文は、長年続いてきた問題、すなわち「速度を犠牲にしたり非現実的な条件を要求したりすることなく、プライベートなデータの中で近似的な一致を見つけるにはどうすればよいか」に対する具体的な解決策を提示しています。研究者たちは単に新しいアイデアを提案しただけではありません。彼らはそれを構築し、テストし、それが以前のあらゆるものよりも桁違いに優れていることを示しました。彼らの仕事は、単に計算能力を投入するのではなく、問題の根底にある論理を洗練させることの力を示す証左となっています。好奇心旺盛な観察者にとって、その結果は、重くて使いにくい機械というよりも、精密で効率的なツールであり、不完全で雑然とした現実のデータの世界で使用される準備ができていると感じられるはずです。

技術要約：片側仮定下における効率的なファジーPSI

問題定義

ファジーPrivate Set Intersection (PSI) は、送信者（sender）と受信者（receiver）の二者が、それぞれの入力セットに含まれる、近似的に一致する要素を特定することを可能にする。具体的には、距離閾値 $\delta$ と距離関数 $dist(\cdot, \cdot)$ が与えられたとき、受信者は、受信側の要素 $\mathbf{w}$ に対して $dist(\mathbf{q}, \mathbf{w}) \le \delta$ を満たす送信側の全要素 $\mathbf{q}$ を学習する。

標準的なPSIは大きな進展を遂げてきたが、ファジーPSIは効率性と基礎となる仮定の強さとの間でトレードオフに直面している。一般的な $L_p$ ( $p \in [1, \infty]$ ) 距離に関する既存の構成法は、通常、以下の2つのカテゴリに分類される：

両側仮定 (Two-sided assumptions): 両者の入力が強い幾何学的分離（例：点同士が $2\delta$ または $4\delta$ 離れていること）を満たす必要があるプロトコル。これらは効率的であるが、現実世界のノイズを含むデータには不適切な場合が多い。
片側仮定 (One-sided assumptions): 片方の当事者の入力のみが分離制約を満たす必要があり、もう一方の当事者は任意の入力を保持できるプロトコル。しかし、既存の片側解法は、重量級の暗号プリミティブ（例：加法準同型暗号）に依存しているか、あるいは閾値 $\delta$ に対して大幅な漸近的オーバーヘッド（例： $O(\delta)$ または $O((\log \delta)^d)$ ）を伴う。

本研究が取り組む核心的な課題は、軽量な対称鍵プリミティブのみを用いて、一般的な $L_p$ 距離における、弱弱な片側仮定下での、具体的かつ効率的なファジーPSIプロトコルを構築することである。

手法

著者らは、秘密分散型オブリービアス・プログラマブル疑似乱数関数 (so-OPPRF) と 空間ハッシング (Spatial Hashing) をベースとし、Prefix Trie 技術によって強化されたフレームワークを提案している。

1. 多点ファジーマッチング・プリミティブ

一方の当事者の入力をリークなしで扱うために、著者らは2つの仮定なし多点ファジーマッチング・プロトコルを導入している：

1-to- $n$ マッチング (受信者が任意の点を保持する場合): 送信者は、単一の点を中心とした区間を用いてso-OPPRFをプログラムする。集約されたシェアにおける衝突によるリーク（先行研究における問題）を防ぐため、著者らは Equality-conditional Randomization (EqRand) を導入している。このプリミティブは、一致しない入力に対してシェアを再ランダム化しつつ、一致する入力に対しては正しい和を保持することで、複数の受信者ポイントが同じプログラムされた区間にマップされる場合でもプライバシーを確保する。
$m$ -to-1 マッチング (送信者が任意の点を保持する場合): 役割が逆転する。受信者は、単一の点を中心とした区間を用いてso-OPPRFをプログラムする。送信者はその関数を自身の複数の点に対して評価する。受信者は送信者側の集約された値を再構成しないため、リークの問題は自然に回避され、EqRandは不要となる。

2. 片側仮定下のファジーPSI

上記のプリミティブに基づき、著者らは以下の2つの特定の片側仮定の下で、完全な $m$ -to- $n$ ファジーPSIプロトコルを構築する：

Unique Cell 仮定: 各空間セル（辺の長さ $2\delta$ ）には、制約を受ける当事者の点が最大1つ含まれる。
Unique Block 仮定 (より疎な条件): 各空間セルは、制約を受ける当事者の $L_\infty$ ボールと高々1つしか交差しない。

プロトコルは空間ハッシングを利用して空間を分割する。制約を受ける当事者は、自身の点とセルの識別子から導出されたキーを用いてso-OPPRFをプログラムし、衝突フリーを保証する。制約を受けない当事者は、自身の点と隣接するセルを用いて関数を評価する。so-OPPRFの使用により出力は秘密分散されるため、いずれの当事者も相手の生のデータを学習することはできない。

3. Prefix Trie による最適化

先行研究で見られる $\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) プリミティブを導入した。各次元においてターゲットに一致するプレフィックスは高々1つであるため、探索空間を $O((\log \delta)^d)$ から $O(d \cdot \log \delta)$ へと削減できる。
結果: これにより、一般的な $L_p$ 距離において、閾値 $\delta$ に対して $O(\log \delta)$ の複雑度を達成し、先行研究の $O((\log \delta)^d)$ や $O(\delta)$ という境界を大幅に改善した。

4. 一般的な $L_p$ 距離の扱い

$L_p$ 距離 ( $p > 1$ ) の場合、プロトコルは次元ごとの距離寄与の $p$ 乗 ( $|t|^p$ ) をso-OPPRFの値にエンコードする。当事者は、これらのシェアを集約し、総距離が閾値 $\delta^p$ 以内であるかを確認するために、秘密計算（加算および乗算）を実行する。

主な貢献

一般的な $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 仮定の両方をサポートしている。Unique Block 仮定を用いることで、so-OPPRFのプログラミングと評価のコスト差を利用して、役割を反転させることによるさらなる最適化が可能となる。
広範な評価: 著者らはプロトコルを実装し、最先端の研究（van Baarsen & Pu [31], Dang et al. [10], Bui et al. [6] など）と比較を行った。

実験結果

評価は AMD EPYC 9554 プロセッサを搭載したサーバー上で実施された。結果は、通信量と計算量の両面で大幅な改善を示している：

van Baarsen and 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の適用可能性を高めている。

著者らは、提案するプロトコルが同等の仮定の下で先行研究を大幅に上回る性能を発揮することを強調しており、次元パラメータに対する指数関数的な依存関係を打破する技術的革新として、プレフィックス・トライを用いた次元ごとのフィルタリング・メカニズムを挙げている。これにより、高次元データや大きなマッチング閾値に対してもスケーラブルなプロトコルとなっている。