2026-07-31T01:00:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21125 2024-09-23T09:13:17Z ddc:004 open_access

Invertible Bloom Lookup Tables with Less Memory and Randomness Fleischhacker, Nils Larsen, Kasper Green Obremski, Maciej Simkin, Mark Invertible Bloom Lookup Tables 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((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 O{n + log(1/δ)log log(1/δ)} space and O{log(log(n)/δ)}-wise independent hash functions. As a key technical ingredient we show that hashing n keys with any k-wise independent hash function h:U → [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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nils Fleischhacker and Kasper Green Larsen and Maciej Obremski and Mark Simkin 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.54 urn:nbn:de:0030-drops-211252 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.54 eng https://creativecommons.org/licenses/by/4.0/legalcode