Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with multicollision resistance:
TR22-017 | 15th February 2022
Ron D. Rothblum, Prashant Nalini Vasudevan

Collision-Resistance from Multi-Collision-Resistance

Revisions: 2

Collision-resistant hash functions (CRH) are a fundamental and ubiquitous cryptographic primitive. Several recent works have studied a relaxation of CRH called t-way multi-collision-resistant hash functions (t-MCRH). These are families of functions for which it is computationally hard to find a t-way collision, even though such collisions are abundant (and even ... more >>>

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

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 >>>

ISSN 1433-8092 | Imprint