3 Search Results for "Fleischhacker, Nils"

Document
DOI: 10.4230/LIPIcs.SEA.2026.19
Breaking 2-Cores for Invertible Bloom Lookup Tables by Structure Prediction

Authors: Vojtěch Gaďurek and Pavel Veselý

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Invertible Bloom Lookup Tables (IBLTs) provide a highly space-efficient way to reconstruct small sets resulting from a large number of insertions and deletions of elements, such as in streaming or distributed computation of the symmetric difference of similar sets. The set recovery process succeeds if the IBLT size is at least 1.22 times the size of the encoded set; otherwise, a 2-core occurs with high probability in the corresponding random hypergraph. However, the sets in practice often exhibit structure that allows for performance beyond worst-case bounds. Here, we demonstrate that structured sets - such as the k-mers in the symmetric difference of two closely related genomes - can be recovered with an IBLT of significantly smaller size. We achieve this by employing structure-aware predictors to break the 2-core whenever the recovery process gets stuck. Importantly, this approach modifies only the decoding procedure, leaving the IBLT data structure unchanged. We prove that even a weak matching-based predictor enables the recovery of 27% more elements than the nominal IBLT size. Equipped with simple predictors for k-mers of genomic datasets, we demonstrate that recovering a symmetric difference with high probability can be done with an IBLT of size only 66% of the encoded set size for k = 31, improving the space efficiency by almost a factor of two. Moreover, we design an improved method for k-mers with large k that combines subsampling with nearly perfect prediction via fingerprinting and achieves a scaling property, requiring only O(M log M) bits for recovering M k-mers, instead of Θ(k⋅M) bits of the standard IBLT. Overall, our results highlight the possibility of significant space-efficiency improvements for IBLTs on datasets with predictable structure.
Cite as

Vojtěch Gaďurek and Pavel Veselý. Breaking 2-Cores for Invertible Bloom Lookup Tables by Structure Prediction. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gadurek_et_al:LIPIcs.SEA.2026.19,
  author =	{Ga\v{d}urek, Vojt\v{e}ch and Vesel\'{y}, Pavel},
  title =	{{Breaking 2-Cores for Invertible Bloom Lookup Tables by Structure Prediction}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{19:1--19:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.19},
  URN =		{urn:nbn:de:0030-drops-260237},
  doi =		{10.4230/LIPIcs.SEA.2026.19},
  annote =	{Keywords: Invertible Bloom Lookup Table, symmetric difference, k-mer sets}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.54
Invertible Bloom Lookup Tables with Less Memory and Randomness

Authors: Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski, and Mark Simkin

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

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 - δ, 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.
Cite as

Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski, and Mark Simkin. Invertible Bloom Lookup Tables with Less Memory and Randomness. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fleischhacker_et_al:LIPIcs.ESA.2024.54,
  author =	{Fleischhacker, Nils and Larsen, Kasper Green and Obremski, Maciej and Simkin, Mark},
  title =	{{Invertible Bloom Lookup Tables with Less Memory and Randomness}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{54:1--54:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.54},
  URN =		{urn:nbn:de:0030-drops-211252},
  doi =		{10.4230/LIPIcs.ESA.2024.54},
  annote =	{Keywords: Invertible Bloom Lookup Tables}
}
Document
DOI: 10.4230/LIPIcs.ITC.2023.5
Interactive Non-Malleable Codes Against Desynchronizing Attacks in the Multi-Party Setting

Authors: Nils Fleischhacker, Suparno Ghoshal, and Mark Simkin

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)

Abstract
Interactive Non-Malleable Codes were introduced by Fleischhacker et al. (TCC 2019) in the two party setting with synchronous tampering. The idea of this type of non-malleable code is that it "encodes" an interactive protocol in such a way that, even if the messages are tampered with according to some class F of tampering functions, the result of the execution will either be correct, or completely unrelated to the inputs of the participating parties. In the synchronous setting the adversary is able to modify the messages being exchanged but cannot drop messages nor desynchronize the two parties by first running the protocol with the first party and then with the second party. In this work, we define interactive non-malleable codes in the non-synchronous multi-party setting and construct such interactive non-malleable codes for the class F^s_bounded of bounded-state tampering functions.
Cite as

Nils Fleischhacker, Suparno Ghoshal, and Mark Simkin. Interactive Non-Malleable Codes Against Desynchronizing Attacks in the Multi-Party Setting. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 5:1-5:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fleischhacker_et_al:LIPIcs.ITC.2023.5,
  author =	{Fleischhacker, Nils and Ghoshal, Suparno and Simkin, Mark},
  title =	{{Interactive Non-Malleable Codes Against Desynchronizing Attacks in the Multi-Party Setting}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{5:1--5:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.5},
  URN =		{urn:nbn:de:0030-drops-183331},
  doi =		{10.4230/LIPIcs.ITC.2023.5},
  annote =	{Keywords: non-malleability, multi-party protocols}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2024
  • 1 2023

  • Refine by Author
  • 2 Fleischhacker, Nils
  • 2 Simkin, Mark
  • 1 Gaďurek, Vojtěch
  • 1 Ghoshal, Suparno
  • 1 Larsen, Kasper Green
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Bloom filters and hashing
  • 1 Applied computing → Bioinformatics
  • 1 Mathematics of computing → Coding theory
  • 1 Theory of computation → Cryptographic protocols
  • 1 Theory of computation → Data structures design and analysis

  • Refine by Keyword
  • 1 Invertible Bloom Lookup Table
  • 1 Invertible Bloom Lookup Tables
  • 1 k-mer sets
  • 1 multi-party protocols
  • 1 non-malleability
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact