論文の概要: Efficient Fuzzy PSI under One-Sided Assumptions

• arxiv url: http://arxiv.org/abs/2608.17770v1
• Date: Tue, 18 Aug 2026 13:32:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-19 21:40:53.352353
• Title: Efficient Fuzzy PSI under One-Sided Assumptions
• Title（参考訳）: 片面推定におけるファジィPSIの有効利用
• Abstract要約: ファジィプライベートセット交差点(英語版) (PSI) は、2つのパーティが入力セット間のほぼ一致する要素を識別することを可能にする。 一般の$L_pin[1,infty]$距離に対して、一方の仮定の下で、初めて具体的かつ効率的なファジィPSIプロトコルを提示する。 当社のプロトコルは,高速計算で最大239ドル,低通信で最大20ドルを実現しています。
• 参考スコア（独自算出の注目度）: 22.833285264459548
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Fuzzy private set intersection (PSI) enables two parties to identify approximately matching elements between their input sets, where two elements are considered a match if their distance is at most a threshold $δ$ under a given metric. Although substantial progress has been made, existing constructions for general Minkowski distances either rely on strong two-sided geometric separation assumptions or incur substantial overhead under one-sided assumptions. In this work, we present the first concretely efficient fuzzy PSI protocols for general $L_{p\in[1,\infty]}$ distances under one-sided assumptions, relying solely on lightweight symmetric-key primitives. Our constructions support both sender-sided and receiver-sided settings. We further study sparser input distributions and present more efficient protocols tailored to this case. To reduce the overhead scaling with $δ$, we non-trivially incorporate prefix trie techniques into our protocols, achieving $O(\logδ)$ complexity for general $L_{p\in[1,\infty]}$ distances for the first time, improving upon $O((\logδ)^d)$ or $O(δ)$ complexities of prior works. Extensive experiments, across a wide range of parameter settings, show that our protocols significantly outperform prior works under the same assumptions. Specifically, against van Baarsen and Pu (EUROCRYPT'24), our protocols achieve up to $239\times$ faster computation and up to $20\times$ lower communication. Against Dang et al. (CCS'25), we achieve up to $518\times$ speedup and up to $63\times$ communication reduction. Against Bui et al. (ASIACRYPT'25), we achieve up to $4818\times$ faster computation and up to $282\times$ lower communication.
• Abstract（参考訳）: ファジィプライベートセット交差点(英語版) (PSI) は、2つの要素が与えられた距離が与えられた距離の下での閾値$δ$である場合、2つの要素が一致していると考えられる入力セット間のほぼ一致する要素を識別することができる。 かなりの進展があったが、ミンコフスキー距離の既存の構成は、強い両側の幾何学的分離仮定に依存するか、一方の側面の仮定の下でかなりのオーバーヘッドを発生させるかのいずれかである。 本研究では、一方の仮定の下での一般$L_{p\in[1,\infty]}$距離に対して、軽量対称鍵プリミティブにのみ依存して、初めて具体的な効率の良いファジィPSIプロトコルを示す。 私たちの構成では、送信側と受信側の両方の設定をサポートしています。 さらに、スペーサー入力分布について検討し、この場合に適したより効率的なプロトコルを提案する。 オーバーヘッドスケーリングを$δ$で削減するために、プレフィックストリエテクニックを我々のプロトコルに非自明に組み込んで、一般の$L_{p\in[1,\infty]} 距離を$O((\logδ)^d)$または$O(δ)$複雑さを初めて達成した。 幅広いパラメータ設定の広範な実験により、我々のプロトコルは、同じ仮定の下での事前動作よりも大幅に優れていたことが示される。 具体的には、van Baarsen と Pu (EUROCRYPT'24) に対して、我々のプロトコルは、より高速な計算で最大$239\times$、より低い通信で最大$20\times$を達成する。 Dang et al (CCS'25)に対して、最大518\times$スピードアップと最大63\times$通信削減を実現しています。 Bui et al (ASIACRYPT'25)に対して、最大4818\times$高速計算と最大282\times$低通信を実現しています。

関連論文リスト

• Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching [43.14972106243527]
  ファジィPSIプロトコルは[1, infty]$距離の一般$L_pに対して、低次元集合と高次元集合の両方をサポートする。 1つはロールリバースなOPRF(OPRF)から構築され、以前の作業では$O(log )d)$に対して$O(dlog )$オーバーヘッドを実現する。 2つ目は、$O(dell)$オーバヘッドでカスタマイズされたoblivious Transfer (OT)を利用し、$ell$は入力のビット長である。
  論文  参考訳（メタデータ） (2026-08-12T00:30:53Z)
• Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening [26.60272178029048]
  我々は,少なくとも$-を達成するためのプロトコルを,2$mathcal O(CC_(G))/2$の通信ビットのみを用いて示す。 本研究の結果は,マルチエージェント情報集約文学における先行研究で要求される仮定を厳格に弱めることに留意する。
  論文  参考訳（メタデータ） (2026-08-05T18:34:19Z)
• Fuzzy PSI from Symmetric Primitives with Exact Logarithmic Dependence on Distance Threshold [14.99063187700722]
  我々は、Otlivious Transfer (OT) と対称キープリミティブから完全に構築された$L_pin[1,infty]$距離のための新しいFPSIプロトコルを提案する。 当社のプロトコルは、実行時に最大43.7タイム、通信時に311.3タイム、従来の最先端よりも優れています。
  論文  参考訳（メタデータ） (2026-06-13T03:59:35Z)
• Optimizing Explicit Unit-Distance Lower-Bound Certificates [0.0]
  2026年のエルツの単位距離予想とサウィンの量的洗練の反証は、固定正の$varepsilon$に対して、n$平面点の間の単位距離の最大値$u(n)$が$n1+varepsilon$を超えることを示す。 本稿では、Sawinのパラメータ選択を非線形整数最適化問題として扱い、素集合$T$と$S_Q$を含む証明書のためのオープンソースのPythonパイプラインを開発する。
  論文  参考訳（メタデータ） (2026-06-02T10:05:23Z)
• Efficient Fuzzy Private Set Intersection from Secret-shared OPRF [41.88845480337768]
  Fuzzy PSI (FPSI) は、受信者がQ$で$qを学習するPSI変種であり、W$に約$wが存在する。 本稿では, [1, infty]$ distance における$L_p に対する効率的な FPSI プロトコルを提案する。 我々のプロトコルは、集合サイズ$m,n$、次元$d$、距離しきい値$$で線形通信と計算の複雑さを実現する。
  論文  参考訳（メタデータ） (2026-04-16T11:51:25Z)
• Reinforcement Learning from Adversarial Preferences in Tabular MDPs [62.73758165845971]
  我々は,敵対的嗜好を持つエピソードマルコフ決定プロセス(MDP)の新たな枠組みを導入する。 PbMDP では、標準的なエピソード MDP とは異なり、学習者は2つの候補アーム間の好みを観察する。 我々は、既知遷移の下で、T2/3$という残差境界を達成するアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2025-07-15T20:19:32Z)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
  論文  参考訳（メタデータ） (2025-02-11T19:54:11Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning [34.630300910399036]
  我々は、$varepsilon$ Central DPの下で最高の精度を得るために必要な基本的な通信コストを特徴付ける。 我々の結果は、$tildeOleft( min(n2varepsilon2, d) right)$ bits per client が十分かつ必要であることを示している。 これにより、最先端のSecAgg分散DPスキームに対して大幅に改善される。
  論文  参考訳（メタデータ） (2022-03-07T22:56:09Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
  我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-01T14:10:38Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。