Welcome to the resource topic for 2023/918
Title:
Invertible Bloom Lookup Tables with Less Memory and Randomness
Authors: Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski, Mark Simkin
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}(n + \log(1/\delta)\log\log(1/\delta)) space and \mathcal{O}(\log(\log(n)/\delta))-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 highly non-trivial as k approaches n. We believe that the techniques used to prove this statement may be of independent interest.
ePrint: https://eprint.iacr.org/2023/918
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .