Invertible Bloom Lookup Tables with Less Memory and Randomness
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929604336287744 |
|---|---|
| author | Fleischhacker, Nils Larsen, Kasper Green Obremski, Maciej Simkin, Mark |
| author_facet | Fleischhacker, Nils Larsen, Kasper Green Obremski, Maciej Simkin, Mark |
| contents | 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 - δ$, existing IBLT constructions require $Ω(n(\frac{\log(1/δ)}{\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 $δ$, our data structure only requires $\mathcal{O}\left(n + \log(1/δ)\log\log(1/δ)\right)$ space and $\mathcal{O}\left(\log(\log(n)/δ)\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^{-Ω(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_07583 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Invertible Bloom Lookup Tables with Less Memory and Randomness Fleischhacker, Nils Larsen, Kasper Green Obremski, Maciej Simkin, Mark Data Structures and Algorithms Cryptography and Security 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 - δ$, existing IBLT constructions require $Ω(n(\frac{\log(1/δ)}{\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 $δ$, our data structure only requires $\mathcal{O}\left(n + \log(1/δ)\log\log(1/δ)\right)$ space and $\mathcal{O}\left(\log(\log(n)/δ)\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^{-Ω(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. |
| title | Invertible Bloom Lookup Tables with Less Memory and Randomness |
| topic | Data Structures and Algorithms Cryptography and Security |
| url | https://arxiv.org/abs/2306.07583 |