論文の概要: Fuzzy Private Set Union via Oblivious Key Homomorphic Encryption Retrieval
- arxiv url: http://arxiv.org/abs/2601.20400v1
- Date: Wed, 28 Jan 2026 09:05:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-29 15:46:06.862505
- Title: Fuzzy Private Set Union via Oblivious Key Homomorphic Encryption Retrieval
- Title（参考訳）: 鍵ホモモルフィック暗号検索によるファジィ・プライベート・セット・ユニオン
- Authors: Jean-Guillaume Dumas, Aude Maignan, Luiza Soezima,
- Abstract要約: プライベート・セット・ユニオン(英: Private Set Union、PSU)は、当事者がプライベート・セット間の交差点を計算できるようにするプロトコルである。
本稿では,ファジィPSUプロトコル(FPSU)について述べる。
- 参考スコア（独自算出の注目度）: 0.30586855806896035
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Private Set Multi-Party Computations are protocols that allow parties to jointly and securely compute functions: apart from what is deducible from the output of the function, the input sets are kept private. Then, a Private Set Union (PSU), resp. Intersection (PSI), is a protocol that allows parties to jointly compute the union, resp. the intersection, between their private sets. Now a structured PSI, is a PSI where some structure of the sets can allow for more efficient protocols. For instance in Fuzzy PSI, elements only need to be close enough, instead of equal, to be part of the intersection. We present in this paper, Fuzzy PSU protocols (FPSU), able to efficiently take into account approximations in the union. For this, we introduce a new efficient sub-protocol, called Oblivious Key Homomorphic Encryption Retrieval (OKHER), improving on Oblivious Key-Value Retrieval (OKVR) techniques in our setting. In the fuzzy context, the receiver set $X=\{x_i\}_{1..n}$ is replaced by ${\mathcal B}_δ(X)$, the union of $n$ balls of dimension $d$ with radius $δ$, centered at the $x_i$. The sender set is just its $m$ points of dimension $d$. Then the FPSU functionality corresponds to $X \sqcup \{y \in Y, y \notin {\mathcal B}_δ(X)\}$. Thus, we formally define the FPSU functionality and security properties, and propose several protocols tuned to the patterns of the balls using the $l_\infty$ distance. Using our OKHER routine and homomorphic encryption, we are for instance able to obtain a FPSU protocols with an asymptotic communication volume bound ranging from $O(dm\log(δ{n}))$ to $O(d^2m\log(δ^2n))$, depending on the receiver data set structure.
- Abstract（参考訳）: Private Set Multi-Party Computations(プライベート・セット・マルチ・パーティ・コンピュテーション)は、関数の出力から導出可能なもの以外は、入力セットはプライベートに保持されるプロトコルである。
その後、プライベート・セット・ユニオン(PSU)が結成された。
インターセクション(英: Intersection、PSI)は、連合を共同で計算するプロトコルである。
交差点、彼らのプライベートセットの間。
現在、構造化PSIは、集合のいくつかの構造がより効率的なプロトコルを可能にするPSIである。
例えば、ファジィPSIでは、要素は交叉の一部となるために、等しくではなく十分近いだけである。
本稿では,ファジィPSUプロトコル(FPSU)について述べる。
そこで我々は,Oblivious Key Homomorphic Encryption Retrieval (OKHER) と呼ばれる新しい効率的なサブプロトコルを導入し,Oblivious Key-Value Retrieval (OKVR) 技術の改良を行った。
ファジィコンテキストでは、受信機は$X=\{x_i\}_{1 をセットする。
n}$ は ${\mathcal B}_δ(X)$ に置き換わる。
送信者集合は、その$m$の次元のポイントである。
このとき FPSU 関数は $X \sqcup \{y \in Y, y \notin {\mathcal B}_δ(X)\}$ に対応する。
したがって、FPSUの機能とセキュリティ特性を正式に定義し、$l_\infty$距離を用いて球のパターンに合わせて調整されたいくつかのプロトコルを提案する。
例えば、OKHERルーチンと同型暗号化を用いて、受信データセットの構造に応じて、$O(dm\log(δ{n}))$から$O(d^2m\log(δ^2n))$までの漸近的な通信量を持つFPSUプロトコルを得ることができる。
関連論文リスト
- 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) - Private Synthetic Data Generation in Small Memory [16.298974544454754]
$mathttPrivHP$は、テキスト差分プライバシーを保証する軽量な合成データジェネレータである。
階層の深さ、ノイズの追加、低周波のプルーニングのバランスを保ちながら、頻繁なノイズを保っている。
論文 参考訳（メタデータ） (2024-12-12T23:24:05Z) - Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth [2.4487770108795393]
本稿では,新しいデータ構造に基づくスパース行列の効率的なブロック符号化プロトコルを提案する。
同じ値のゼロでない要素は、ブロックエンコーディングプロトコルの辞書で同じ分類に属する。
我々のプロトコルは、ユニタリ(LCU)とスパースアクセス入力モデル(SAIM)の線形結合に接続する。
論文 参考訳（メタデータ） (2024-05-28T09:49:58Z) - Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
本稿では,プライバシのシャッフルモデルにおけるプライベートベクトル平均推定の問題について検討する。
我々は,$tildemathcalOleft(min(nvarepsilon2,d)right)$ message per users を用いて,最適なエラーを実現する新しいマルチメッセージプロトコルを提案する。
論文 参考訳（メタデータ） (2024-04-16T00:56:36Z) - Distributed Optimization with Feasible Set Privacy [35.16231062731263]
2つのエージェントは、実行可能なセットを$mathcalP1$と$mathcalP1$を互いにプライベートに保ちながら、最適なソリューションセットを学ぶ。
エージェントの1つが$mathcalP$をプライベートにチェックする、シーケンシャルなプライベート情報検索(SPIR)フレームワークを採用しています。
SPIR-based private set intersection (PSI) プロトコルで実現可能な$mathcalP1$をプライベートに取得するのに対し、最適な方法を見つけるには、情報漏洩が少なく、ダウンロードも少ないため、我々の手法の方が優れていることを示す。
論文 参考訳（メタデータ） (2023-12-04T18:45:04Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳（メタデータ） (2022-09-04T10:01:39Z) - Reward-Free Model-Based Reinforcement Learning with Linear Function
Approximation [92.99933928528797]
エピソードマルコフ決定過程(MDP)に対する線形関数近似を用いたモデルに基づく無報酬強化学習について検討する。
計画段階では、特定の報酬関数が与えられ、探索フェーズから収集したサンプルを使用して良い政策を学ぶ。
任意の報酬関数に対して$epsilon$-optimal Policyを得るには,最大$tilde O(H4d(H + d)epsilon-2)$ episodesをサンプリングする必要がある。
論文 参考訳（メタデータ） (2021-10-12T23:03:58Z) - The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
高い利害関係のアプリケーションでは、アクティブな実験は危険すぎると考えられ、データはしばしば受動的に収集される。
バンディットやパッシブ、アクティブなデータ収集などの単純な場合も同様に効果的であるが、制御された状態のシステムからデータを集める場合、パッシブサンプリングの価格ははるかに高い。
論文 参考訳（メタデータ） (2021-06-18T07:54:23Z) - On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。
目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文 参考訳（メタデータ） (2020-09-21T04:13:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。