All reports by Author Surendra Ghentiyala:

__
TR24-018
| 28th January 2024
__

Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz#### The more the merrier! On the complexity of finding multicollisions, with connections to codes and lattices

Revisions: 2

Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz

We study the problem of finding multicollisions, that is, the total search problem in which the input is a function $\mathcal{C} : [A] \to [B]$ (represented as a circuit) and the goal is to find $L \leq \lceil A/B \rceil$ distinct elements $x_1,\ldots, x_L \in A$ such that $\mathcal{C}(x_1) = ... more >>>