Access Restriction

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

   Open content in new tab
Source: ACM Digital Library