Fugu-MT 論文翻訳(概要): Invertible Bloom Lookup Tables with Less Memory and Randomness

論文の概要: Invertible Bloom Lookup Tables with Less Memory and Randomness

arxiv url: http://arxiv.org/abs/2306.07583v3
Date: Tue, 26 Nov 2024 17:05:11 GMT
ステータス: 翻訳完了
システム内更新日: 2024-11-28 15:21:57.345001
Title: Invertible Bloom Lookup Tables with Less Memory and Randomness
Title（参考訳）: 記憶量とランダム性の少ない可逆ブルームルックアップテーブル
Authors: Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski, Mark Simkin,
Abstract要約: Invertible Bloom Lookup Tables (IBLT) は、セット和解プロトコル、エラー訂正符号、高度な暗号プリミティブの設計に応用されている。 IBLTは同時に空間効率が良く、ランダム性が低い新しい構成を提案する。 k$ の独立ハッシュ関数 $h:U to [Cn]$ for some enough large constant $C$ guarantees with probability $1 - 2-Omega(k)$ that least $n/2$ key will have a unique hash value。
参考スコア（独自算出の注目度）: 23.724300017513574
License:
Abstract: In this work we study Invertible Bloom Lookup Tables (IBLTs) with small failure probabilities. IBLTs are highly versatile data structures that have found applications in set reconciliation protocols, error-correcting codes, and even the design of advanced cryptographic primitives. For storing $n$ elements and ensuring correctness with probability at least $1 - \delta$, existing IBLT constructions require $\Omega(n(\frac{\log(1/\delta)}{\log(n)}+1))$ space and they crucially rely on fully random hash functions. We present new constructions of IBLTs that are simultaneously more space efficient and require less randomness. For storing $n$ elements with a failure probability of at most $\delta$, our data structure only requires $\mathcal{O}\left(n + \log(1/\delta)\log\log(1/\delta)\right)$ space and $\mathcal{O}\left(\log(\log(n)/\delta)\right)$-wise independent hash functions. As a key technical ingredient we show that hashing $n$ keys with any $k$-wise independent hash function $h:U \to [Cn]$ for some sufficiently large constant $C$ guarantees with probability $1 - 2^{-\Omega(k)}$ that at least $n/2$ keys will have a unique hash value. Proving this is non-trivial as $k$ approaches $n$. We believe that the techniques used to prove this statement may be of independent interest. We apply our new IBLTs to the encrypted compression problem, recently studied by Fleischhacker, Larsen, Simkin (Eurocrypt 2023). We extend their approach to work for a more general class of encryption schemes and using our new IBLT we achieve an asymptotically better compression rate.
Abstract（参考訳）: Invertible Bloom Lookup Tables (IBLT) with small failure probability。 IBLTは、セット和解プロトコル、エラー訂正符号、さらには高度な暗号プリミティブの設計にも応用できる、非常に汎用的なデータ構造である。 n$要素を保存し、少なくとも1 - \delta$の確率で正しさを保証するために、既存のIBLT構成は$\Omega(n(\frac{\log(1/\delta)}{\log(n)}+1))$空間を必要とし、それらは完全にランダムなハッシュ関数に依存している。 IBLTは同時に空間効率が良く、ランダム性が低い新しい構成を提案する。最大$\delta$の失敗確率を持つ$n$要素を保存するには、データ構造は$\mathcal{O}\left(n + \log(1/\delta)\log(1/\delta)\right)$ spaceと$\mathcal{O}\left(\log(\log(n)/\delta)\right)$-wise独立ハッシュ関数のみを必要とする。重要な技術的要素として、$n$キーを$k$の独立ハッシュ関数$h:U \to [Cn]$でハッシュすると、確率1 - 2^{-\Omega(k)}$で保証される。 k$ approach $n$ であることを証明するのは簡単ではない。私たちは、この主張を証明するために使われたテクニックは、独立した関心事であるかもしれないと信じています。我々は、最近Fleischhacker, Larsen, Simkin (Eurocrypt 2023) によって研究された暗号化圧縮問題に、新しいIBLTを適用した。我々は、より一般的な暗号化方式のために彼らのアプローチを拡張し、新しいIBLTを使って漸近的により良い圧縮率を達成する。

関連論文リスト

Differentially Private Set Representations [13.576656322669098]
本研究では,大宇宙からの大きさの集合を$k$で表すために,差分プライベート(DP)機構の問題を考察する。最初の構成では、$(epsilon,delta)$-DP表現を生成し、エラー確率は1/(eepsilon + 1)$で、少なくとも1.05 k epsilon cdot log(e)$ bitsで空間を使用する。また、最大$k epsilon cdot log(e)$ bitsの空間を用いて、同じエラーを持つ純粋な$epsilon$-DP表現のための第2のアルゴリズムも提示する。
論文参考訳（メタデータ） (2025-01-28T03:29:00Z)
Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文参考訳（メタデータ） (2024-06-07T12:07:16Z)
Pb-Hash: Partitioned b-bit Hashing [21.607059258448594]
我々は、$B$ビットを$m$チャンク、例えば$btimes m =B$に分割することでハッシュを再使用することを提案する。我々の理論的分析により、ハッシュ値を$m$チャンクに分割することで、精度が低下することが明らかとなった。一部のリージョンでは、Pb-Hashは4.9ドルよりもずっと大きい$m$でもうまく機能している。
論文参考訳（メタデータ） (2023-06-28T06:05:47Z)
Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
論文参考訳（メタデータ） (2023-02-20T19:11:44Z)
Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom [1.0323063834827415]
安定度が低い」量子状態は、Haar-randomと効率的に区別できることを示す。我々は、計算的に擬似ランダムな量子状態を作成するためには、任意のクリフォード+$T$回路に対して$omega(log(n))$$T$-gatesが必要であることを証明した。
論文参考訳（メタデータ） (2022-09-29T03:34:03Z)
Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文参考訳（メタデータ） (2022-06-07T18:00:01Z)
On Avoiding the Union Bound When Answering Multiple Differentially Private Queries [49.453751858361265]
このタスクのアルゴリズムは、$o(frac1epsilonsqrtk log frac1delta)$の期待値$ell_infty$エラーバウンドを達成する。一方、DaganとKurkのアルゴリズムは、$O(frac1epsilonsqrtk log frac1delta)$の$ell_infty$エラー境界が期待だけでなく常に保持するという驚くべき利点を持っています。
論文参考訳（メタデータ） (2020-12-16T17:58:45Z)
An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文参考訳（メタデータ） (2020-08-24T06:50:57Z)
A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文参考訳（メタデータ） (2020-06-02T16:38:36Z)
Fast digital methods for adiabatic state preparation [0.0]
ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-04-08T18:00:01Z)
Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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