REVIEW 1 cited by
On Finding Quantum Multi-collisions
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
On Finding Quantum Multi-collisions
read the original abstract
A $k$-collision for a compressing hash function $H$ is a set of $k$ distinct inputs that all map to the same output. In this work, we show that for any constant $k$, $\Theta\left(N^{\frac{1}{2}(1-\frac{1}{2^k-1})}\right)$ quantum queries are both necessary and sufficient to achieve a $k$-collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first non-trivial lower bound, completely resolving the problem.
Forward citations
Cited by 1 Pith paper
-
Tight Quantum Lower Bound for k-Distinctness
A new quantum lower bound framework proves a tight bound for k-Distinctness.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.