論文の概要: Fuzzy PSI from Symmetric Primitives with Exact Logarithmic Dependence on Distance Threshold

• arxiv url: http://arxiv.org/abs/2606.15093v1
• Date: Sat, 13 Jun 2026 03:59:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-16 16:21:32.840457
• Title: Fuzzy PSI from Symmetric Primitives with Exact Logarithmic Dependence on Distance Threshold
• Title（参考訳）: 距離閾値に特異的な対数依存性を有する対称プリミティブからのファジィPSI
• Authors: Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang,
• Abstract要約: 我々は、Otlivious Transfer (OT) と対称キープリミティブから完全に構築された$L_pin[1,infty]$距離のための新しいFPSIプロトコルを提案する。 当社のプロトコルは、実行時に最大43.7タイム、通信時に311.3タイム、従来の最先端よりも優れています。
• 参考スコア（独自算出の注目度）: 14.99063187700722
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Previous FPSI works have demonstrated a linear scaling with the distance threshold $δ$, while some recent works have achieved a poly-logarithmic dependence on $δ$. However, these protocols either support only the $L_\infty$ distance, or they support general $L_{p\in[1,\infty]}$ distances but rely on expensive additive homomorphic encryption (AHE). Achieving exact logarithmic dependence on $δ$ for general $L_{p\in[1,\infty]}$ distances without relying on costly AHE would constitute a theoretical breakthrough in optimal threshold scaling and a practical advance toward scalable FPSI applications. In this work, we present new FPSI protocols for $L_{p\in[1,\infty]}$ distances that are entirely built from oblivious transfer (OT) and symmetric-key primitives. We propose FPSI protocols based on both the apart and the separate assumptions, which are applicable to low- and high-dimensional settings, respectively. Our constructions achieve strictly logarithmic complexity in $δ$, which is optimal in the sense that distinguishing all values in an interval of length $O(δ)$ necessarily requires $Ω(\log δ)$ bits of information. Our core idea is to perform fuzzy matching via prefix representation and interactively determine the correct prefix using equality conditions. To this end, we propose a suite of new components that can be implemented efficiently using only OT and symmetric-key operations. We implement our FPSI protocols and compare them with the state-of-the-art FPSI protocols for $L_{p\in[1,\infty]}$ distance. Experiments show that our protocols outperform the prior state-of-the-art by up to $43.7\times$ in runtime and $31.3\times$ in communication.
• Abstract（参考訳）: 以前のFPSI研究は距離閾値が$δ$の線形スケーリングを実証しているが、最近のいくつかの研究は$δ$に対する多対数依存を達成している。 しかし、これらのプロトコルは$L_\infty$距離のみをサポートするか、一般的な$L_{p\in[1,\infty]}$距離をサポートするが、高価な加法的同型暗号(AHE)に依存している。 一般的な$L_{p\in[1,\infty]} の$δ$に対する正確な対数依存を得ることは、AHE のコストに依存することなく、最適しきい値スケーリングの理論的なブレークスルーとなり、スケーラブルな FPSI アプリケーションへの実践的な進歩をもたらす。 本研究では、Otlivious Transfer (OT) と対称キープリミティブから完全に構築された$L_{p\in[1,\infty]}$距離に対する新しいFPSIプロトコルを提案する。 低次元および高次元の設定にそれぞれ適用可能な、分離された仮定と分離された仮定の両方に基づくFPSIプロトコルを提案する。 我々の構成は$δ$で厳密な対数複雑性を達成しており、これは長さ$O(δ)$の間隔で全ての値を区別するには必ずしも$Ω(\log δ)$ビットの情報を必要とするという意味で最適である。 我々の中核となる考え方は、接頭辞表現によるファジィマッチングを行い、同値条件を用いて正しい接頭辞を対話的に決定することである。 そこで本研究では,OTと対称キーのみを用いて効率的に実装できる新しいコンポーネント群を提案する。 我々は、FPSIプロトコルを実装し、その距離を$L_{p\in[1,\infty]}の最先端FPSIプロトコルと比較する。 実験により、我々のプロトコルは、実行時に43.7\times$、通信時に31.3\times$よりも優れていた。

関連論文リスト

• 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)
• Fuzzy Private Set Union via Oblivious Key Homomorphic Encryption Retrieval [0.30586855806896035]
  プライベート・セット・ユニオン(英: Private Set Union、PSU)は、当事者がプライベート・セット間の交差点を計算できるようにするプロトコルである。 本稿では,ファジィPSUプロトコル(FPSU)について述べる。
  論文  参考訳（メタデータ） (2026-01-28T09:05:35Z)
• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  距離の新しい族、相対翻訳不変ワッサーシュタイン距離(RW_p$)を導入する。 我々は、$RW_p 距離もまた、分布変換に不変な商集合 $mathcalP_p(mathbbRn)/sim$ 上で定義される実距離測度であることを示す。
  論文  参考訳（メタデータ） (2024-09-04T03:41:44Z)
• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。 ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。 あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
  論文  参考訳（メタデータ） (2024-06-17T20:54:11Z)
• Transfer Q Star: Principled Decoding for LLM Alignment [105.89114186982972]
  Transfer $Q*$は、ベースラインモデルを通してターゲット報酬$r$の最適値関数を推定する。 提案手法は, 従来のSoTA法で観測された準最適差を著しく低減する。
  論文  参考訳（メタデータ） (2024-05-30T21:36:12Z)
• Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learning [2.2984209387877628]
  無限水平平均逆強化学習(RL)におけるリプシッツ MDP について検討した。 for $d_texteff. = dPhi_z+2$ for model-free algorithmtextitPZRL-MF and $d_texteff. = 2d_mathcalS + dPhi_z + 3$ for
  論文  参考訳（メタデータ） (2024-05-29T06:18:09Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。 我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
  論文  参考訳（メタデータ） (2023-03-03T18:23:20Z)
• 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)
• 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)

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

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