### Quantum lower bounds for the collision and the element distinctness problemsQuantum lower bounds for the collision and the element distinctness problems

Access Restriction
Subscribed

 Author Aaronson, Scott ♦ Shi, Yaoyun Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2004 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Collision ♦ Element distinctness ♦ Polynomial method ♦ Quantum computing ♦ Quantum lower bounds Abstract Given a function $\textit{f}$ as an oracle, the collision problem is to find two distinct indexes $\textit{i}$ and $\textit{j}$ such that $\textit{f}(\textit{i})$ = $\textit{f}(\textit{j}),$ under the promise that such indexes exist. Since the security of many fundamental cryptographic primitives depends on the hardness of finding collisions, our lower bounds provide evidence for the existence of cryptographic primitives that are immune to quantum cryptanalysis. We prove that any quantum algorithm for finding a collision in an $\textit{r}-to-one$ function must evaluate the function $Ω((n/r)^{1/3})$ times, where $\textit{n}$ is the size of the domain and $\textit{r}|\textit{n}.$ This matches an upper bound of Brassard, Høyer, and Tapp. No lower bound better than constant was previously known. Our result also implies a quantum lower bound of $Ω(n^{2/3})$ queries for the element distinctness problem, which is to determine whether $\textit{n}$ integers are all distinct. The best previous lower bound was $Ω(&sqrt;\textit{n})$ queries. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2004-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 51 Issue Number 4 Page Count 11 Starting Page 595 Ending Page 605

#### Open content in new tab

Source: ACM Digital Library