DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2026.28

Bounded Linear Probing Hashing

Authors: Ahmed Alharbi, Cyril Banderier, and Charles Bouillaguet

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract

We introduce a process that inserts elements into a hash table with a bounded number of probes, motivated by an application in cryptography. The cost of this algorithm is the number of insertion trials, whether successful or failed, until the table gets completely filled. This gives an interpolation between linear probing hashing and the coupon collector problem. We show that the process is related to a non-linear differential equation, which allows us to obtain the generating function of full tables. The proofs involve a full algebra of operators, which are themselves of independent interest. Then, we obtain the asymptotic behaviour of the expected number of insertion trials to get a full table.

Cite as

Ahmed Alharbi, Cyril Banderier, and Charles Bouillaguet. Bounded Linear Probing Hashing. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alharbi_et_al:LIPIcs.AofA.2026.28,
  author =	{Alharbi, Ahmed and Banderier, Cyril and Bouillaguet, Charles},
  title =	{{Bounded Linear Probing Hashing}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.28},
  URN =		{urn:nbn:de:0030-drops-262995},
  doi =		{10.4230/LIPIcs.AofA.2026.28},
  annote =	{Keywords: Linear probing hashing, analytic combinatorics, cryptography}
}

Document

DOI: 10.4230/LIPIcs.FUN.2026.9

MIDTERM Is a Deterministic Technique to Exit Recursive Mazes

Authors: Charles Bouillaguet and Orel Cosseron

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

A recursive maze is a maze that contains copies of itself (that themselves contain copies of themselves, etc.). To exit the maze or reach the goal, each recursive block that has been entered must be exited. These once-popular puzzles are difficult to solve by hand, and this begs for an algorithmic solution. It has been observed many times in the past that a recursive maze can be represented by a deterministic pushdown automaton. Finding a path, possibly the shortest, that leads to an exit therefore reduces to finding a word in a context-free language described by such an automaton. The problem is well-known to be decidable, and there is a classical algorithm for this task. We present a new algorithm, Midterm, with improved complexity compared to existing solutions. Midterm improves on a previous attempt called Longterm (Obviously Not a Good Technique to Exit Recursive Mazes).

Cite as

Charles Bouillaguet and Orel Cosseron. MIDTERM Is a Deterministic Technique to Exit Recursive Mazes. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bouillaguet_et_al:LIPIcs.FUN.2026.9,
  author =	{Bouillaguet, Charles and Cosseron, Orel},
  title =	{{MIDTERM Is a Deterministic Technique to Exit Recursive Mazes}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.9},
  URN =		{urn:nbn:de:0030-drops-257280},
  doi =		{10.4230/LIPIcs.FUN.2026.9},
  annote =	{Keywords: Recursive maze, pushdown automaton, reachability, context-free grammar, graph rewriting}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2023.23

Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator

Authors: Charles Bouillaguet, Florette Martinez, and Damien Vergnaud

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract

We present attacks on a generalized subset-sum pseudorandom generator, which was proposed by von zur Gathen and Shparlinski in 2004. Our attacks rely on a sub-quadratic algorithm for solving a vectorial variant of the 3SUM problem, which is of independent interest. The attacks presented have complexities well below the brute-force attack, making the generators vulnerable. We provide a thorough analysis of the attacks and their complexities and demonstrate their practicality through implementations and experiments.

Cite as

Charles Bouillaguet, Florette Martinez, and Damien Vergnaud. Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bouillaguet_et_al:LIPIcs.MFCS.2023.23,
  author =	{Bouillaguet, Charles and Martinez, Florette and Vergnaud, Damien},
  title =	{{Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.23},
  URN =		{urn:nbn:de:0030-drops-185579},
  doi =		{10.4230/LIPIcs.MFCS.2023.23},
  annote =	{Keywords: Cryptography, pseudo-random generator, subset-sum problem, 3SUM problem, cryptanalysis}
}

Search Results

Documents authored by Bouillaguet, Charles

Bounded Linear Probing Hashing

Abstract

Cite as

MIDTERM Is a Deterministic Technique to Exit Recursive Mazes

Abstract

Cite as

Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator

Abstract

Cite as

Thanks for your feedback!

Could not send message