論文の概要: Efficient Fuzzy Private Set Intersection from Secret-shared OPRF

• arxiv url: http://arxiv.org/abs/2604.14909v1
• Date: Thu, 16 Apr 2026 11:51:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-17 21:29:31.878068
• Title: Efficient Fuzzy Private Set Intersection from Secret-shared OPRF
• Title（参考訳）: シークレットシェードOPRFからのファジィ・プライベート・セット・インターフェクトの高効率化
• Authors: Xinpeng Yang, Meng Hao, Chenkai Weng, Robert H. Deng, Yonggang Wen, Tianwei Zhang,
• Abstract要約: Fuzzy PSI (FPSI) は、受信者がQ$で$qを学習するPSI変種であり、W$に約$wが存在する。 本稿では, [1, infty]$ distance における$L_p に対する効率的な FPSI プロトコルを提案する。 我々のプロトコルは、集合サイズ$m,n$、次元$d$、距離しきい値$$で線形通信と計算の複雑さを実現する。
• 参考スコア（独自算出の注目度）: 41.88845480337768
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Private set intersection (PSI) enables a sender holding a set $Q$ of size $m$ and a receiver holding a set $W$ of size $n$ to securely compute the intersection $Q \cap W$. Fuzzy PSI (FPSI) is a PSI variant where the receiver learns the items $q \in Q$ for which there exists some $w \in W$ satisfying $\mathsf{dist}(q, w) \le δ$ under a given distance metric. Although several FPSI works are proposed for $L_{p}$ distance metrics with $p \in [1, \infty]$, they either heavily rely on expensive homomorphic encryptions, or incur undesirable complexity, e.g., exponential to the element dimension, both of which lead to poor practical efficiency. In this work, we propose efficient FPSI protocols for $L_{p \in [1, \infty]}$ distance metrics, primarily leveraging significantly cheaper symmetric-key operations. Our protocols achieve linear communication and computation complexity in the set sizes $m,n$, the dimension $d$, and the distance threshold $δ$. Our core building block is an oblivious programmable PRF with secret-shared outputs, which may be of independent interest. Furthermore, we incorporate a prefix technique that reduces the dependence on the distance threshold $δ$ to logarithmic, which is particularly suitable for large $δ$. We implement our FPSI protocols and compare them with state-of-the-art constructions. Experimental results demonstrate that our protocols consistently and significantly outperform existing works across all settings. Specifically, our protocols achieve a speedup of $12{\sim}145\times$ in running time and a reduction of $3{\sim}8\times$ in communication cost compared to Gao et al.~(ASIACRYPT'24) and a speedup of $9{\sim}80\times$ in running time and a reduction of $5{\sim}19\times$ in communication cost compared to Dang et al.~(CCS'25).
• Abstract（参考訳）: プライベート・セット・交差点(PSI)は、セットの$Q$ of size $m$とセットの$W$ of size $n$を保持している受信機を持ち、その交差点の$Q \cap W$を安全に計算することができる。 ファジィPSI (Fuzzy PSI, FPSI) は、受信者が与えられた距離距離の計量の下で、$$q \in Q$ を満たす$w \in W$ の項目を学習する PSI 変種である。 L_{p}$ 距離測度と$p \in [1, \infty]$に対していくつかの FPSI の研究が提案されているが、それらは高価な同型暗号に大きく依存するか、あるいは望ましくない複雑さ(例えば、要素次元への指数関数)に大きく依存している。 本研究では,より安価な対称鍵演算を主に活用する,$L_{p \in [1, \infty]}$距離測定のための効率的なFPSIプロトコルを提案する。 このプロトコルは,集合サイズ$m,n$,次元$d$,距離しきい値$δ$で線形通信と計算複雑性を実現する。 私たちの中核的なビルディングブロックは、秘密の共有出力を持つ、難解なプログラマブルPRFであり、それは独立した関心事であるかもしれない。 さらに,距離閾値$δ$から対数への依存性を低減するプレフィックス手法を導入し,特に大きな$δ$に適合することを示す。 我々は、FPSIプロトコルを実装し、それらを最先端の構造と比較する。 実験の結果、我々のプロトコルは、すべての設定で既存の作業よりも一貫して、大幅に優れています。 具体的には、実行時の12{\sim}145\times$と通信コストの3{\sim}8\times$をGao et al ~(ASIACRYPT'24)と比較して達成し、実行時の9{\sim}80\times$と通信コストの5{\sim}19\times$をDang et al ~(CCS'25)と比較した。

関連論文リスト

• Fuzzy Private Set Union via Oblivious Key Homomorphic Encryption Retrieval [0.30586855806896035]
  プライベート・セット・ユニオン(英: Private Set Union、PSU)は、当事者がプライベート・セット間の交差点を計算できるようにするプロトコルである。 本稿では,ファジィPSUプロトコル(FPSU)について述べる。
  論文  参考訳（メタデータ） (2026-01-28T09:05:35Z)
• Efficient and High-Accuracy Secure Two-Party Protocols for a Class of Functions with Real-number Inputs [8.447031280935965]
  二次元秘密共有方式では、値は符号なし整数 $mathsfuint(x)$ でエンコードされるが、現実のアプリケーションは符号付き実数 $mathsfReal(x)$ で計算を必要とすることが多い。 本研究では、この制約を任意の$B leq fracL2$に対して$|x| B$に緩和する。
  論文  参考訳（メタデータ） (2025-09-01T06:56:29Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
  論文  参考訳（メタデータ） (2025-06-30T13:27:39Z)
• Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
  次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。 また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
  論文  参考訳（メタデータ） (2023-05-12T08:43:28Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Sampling from Log-Concave Distributions with Infinity-Distance Guarantees and Applications to Differentially Private Optimization [33.38289436686841]
  本稿では,dis distributionO(varepsilon)$close から$ infinity-distance に点を出力するアルゴリズムを提案する。 また、ディキンウォークの「ソフトパイ」バージョンも提示する。
  論文  参考訳（メタデータ） (2021-11-07T13:44:50Z)
• Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
  本稿では、特にバッチ強化学習に適した報酬不要強化学習フレームワークと、複数の報酬関数に対するポリシーを必要とするシナリオについて検討する。 textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname) という新しい効率的なアルゴリズムを提供しています。
  論文  参考訳（メタデータ） (2020-10-12T17:51:19Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)

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

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