In this study, the authors explore Invertible Bloom Lookup Tables (IBLTs) with low failure probabilities. IBLTs are versatile data structures used in various applications such as set reconciliation, error correction, and cryptography. Existing IBLT constructions require a significant amount of space and rely on random hash functions to ensure correctness. However, the authors introduce new IBLT constructions that are more space efficient and require less randomness. Their data structure only needs “n + log(1/δ)loglog(1/δ)” space and log(log(n)/δ)-wise independent hash functions to store n elements with a failure probability of at most δ. A key technical aspect of their work is proving that when hashing n keys with a k-wise independent hash function, at least n/2 keys will have a unique hash value with a high probability. This proof is challenging as k approaches n. The authors believe that the techniques used to prove this statement may have independent interest.
https://arxiv.org/abs/2306.07583