論文の概要: Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

• arxiv url: http://arxiv.org/abs/2608.11526v1
• Date: Wed, 12 Aug 2026 00:30:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-13 19:07:54.407773
• Title: Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching
• Title（参考訳）: 高速ファジィマッチングによるスケーラブルファジィPSIの実現に向けて
• Abstract要約: ファジィPSIプロトコルは[1, infty]$距離の一般$L_pに対して、低次元集合と高次元集合の両方をサポートする。 1つはロールリバースなOPRF(OPRF)から構築され、以前の作業では$O(log )d)$に対して$O(dlog )$オーバーヘッドを実現する。 2つ目は、$O(dell)$オーバヘッドでカスタマイズされたoblivious Transfer (OT)を利用し、$ell$は入力のビット長である。
• 参考スコア（独自算出の注目度）: 43.14972106243527
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we present scalable fuzzy PSI protocols for general $L_{p \in [1, \infty]}$ distance, supporting both low- and high-dimensional sets. The core technique is two efficient fuzzy matching protocols. The first is built from a role-reversed oblivious PRF (OPRF) and realizes $O(d\log δ)$ overhead, compared to $O((\log δ)^d)$ in previous works. The second leverages customized oblivious transfer (OT) with $O(d\ell)$ overhead, where $\ell$ is the bit length of inputs, which is particularly suitable for short inputs. With these new techniques, we further propose a new dual-layer hashing framework for fuzzy PSI over low-dimensional sets, instantiated with our OT-based fuzzy matching and enhanced with a domain reduction optimization. The protocols achieve an overhead linear with $n, m, \log δ, 2^d$, without the $O((\log δ)^d)$ or $O(δ)$ factors present in prior works. {For high-dimensional sets, we construct fuzzy PSI protocols based on our OPRF- and OT-based fuzzy matching, which achieve an asymptotic overhead linear with $n, m, d$, and $\log δ$ but rely on the strong globally disjoint assumption.} Extensive evaluations demonstrate that our protocols achieve up to a $145\times$ speedup in running time and a $20\times$ reduction in communication cost compared to van Baarsen and Pu~(ASIACRYPT'25), and achieve up to a $25\times$ speedup in running time and up to a $17\times$ reduction in communication cost compared to Piske et al.~(CCS'25).
• Abstract（参考訳）: 本稿では,L_{p \in [1, \infty]} 距離に対する拡張性のあるファジィPSIプロトコルを提案し,低次元および高次元の集合をサポートする。 コア技術は2つの効率的なファジィマッチングプロトコルである。 1つはロールリバースなOPRF(OPRF)から構築され、以前の作業では$O((\log δ)^d)$に対して$O(d\log δ)$オーバーヘッドを実現する。 2つ目は、$O(d\ell)$オーバーヘッドでカスタマイズされたoblivious Transfer (OT)を利用し、$\ell$は入力のビット長であり、特に短い入力に適している。 これらの新しい手法により、低次元集合上のファジィPSIのための新しい二重層ハッシュフレームワークが提案され、OTベースのファジィマッチングによりインスタンス化され、ドメインの縮小最適化により拡張される。 このプロトコルは、$O((\log δ)^d)$ または $O(δ)$ を使わずに、$n, m, \log δ, 2^d$ でオーバーヘッド線型を達成する。 高次元集合に対しては、OPRF および OT ベースのファジィマッチングに基づいてファジィPSI プロトコルを構築し、これは、$n, m, d$, $\log δ$ の漸近的オーバーヘッド線型を達成するが、強い大域的不整合仮定に依存する。 以上の結果から,当社のプロトコルは,Van BaarsenやPu~(ASIACRYPT'25)と比較して,実行時間で最大145ドル,通信コストで最大20ドル,ランニング時間で最大25ドル,通信コストで最大17ドルを実現していることがわかった。

関連論文リスト

• Efficient Fuzzy PSI under One-Sided Assumptions [22.833285264459548]
  ファジィプライベートセット交差点(英語版) (PSI) は、2つのパーティが入力セット間のほぼ一致する要素を識別することを可能にする。 一般の$L_pin[1,infty]$距離に対して、一方の仮定の下で、初めて具体的かつ効率的なファジィPSIプロトコルを提示する。 当社のプロトコルは,高速計算で最大239ドル,低通信で最大20ドルを実現しています。
  論文  参考訳（メタデータ） (2026-08-18T13:32:33Z)
• 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)
• 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)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
  論文  参考訳（メタデータ） (2025-06-30T13:27:39Z)
• 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)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Transfer Q Star: Principled Decoding for LLM Alignment [105.89114186982972]
  Transfer $Q*$は、ベースラインモデルを通してターゲット報酬$r$の最適値関数を推定する。 提案手法は, 従来のSoTA法で観測された準最適差を著しく低減する。
  論文  参考訳（メタデータ） (2024-05-30T21:36:12Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• A general approximation lower bound in $L^p$ norm, with applications to feed-forward neural networks [0.0]
  ニューラルネットワークの表現力に対する基本的な限界について検討する。 まず最初に、$F$ の函数が $Lp(mu)$ ノルムでどれだけよく近似できるかの一般的な下界を証明します。 すると、これを$G$が多項式フィードフォワードニューラルネットワークに対応するケースに初期化する。
  論文  参考訳（メタデータ） (2022-06-09T09:01:05Z)
• On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error [18.19398247972205]
  我々は、少なくとも$n$の成分を持つ、おそらく異なる質量の2つの測度の間の不均衡最適輸送(UOT)について研究する。 UOT問題に対する$varepsilon$-approximateの解を求めるために,GEM-UOT(Gradient Extrapolation Method)に基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-02-08T03:22:39Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)

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

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