Abstract
We give a quantum algorithm that finds collisions in arbitrary r-to-one functions after only O(3√N/r) expected evaluations of the function, where N is the cardinality of the domain. Assuming the function is given by a black box, this is more efficient than the best possible classical algorithm, even allowing probabilism. We also give a similar algorithm for finding claws in pairs of functions. Further, we exhibit a space-time tradeoff for our technique. Our approach uses Grover's quantum searching algorithm in a novel way.
Supported in part by Canada's nserc, Quebec's fcar, and the Canada Council.
Supported in part by the esprit Long Term Research Programme of the EU under project number 20244 (alcom-it). Research carried out while this author was at the Université de Montréal.
Supported in part by postgraduate fellowships from nserc and fcar
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
Michel Boyer, Gilles Brassard, Peter HØyer and Alain Tapp, “Tight bounds on quantum searching”, Proceedings of Fourth Workshop on Physics and Computation — PhysComp '96, November 1996, pp. 36–43. Final version to appear in Fortschritte Der Physik.
Gilles Brassard, David Chaum and Claude Crépeau, “Minimum disclosure proofs of knowledge”, Journal of Computer and System Sciences, Vol. 37, no. 2, October 1988, pp. 156–189.
Gilles Brassard and Peter HØyer, “An exact quantum polynomial-time algorithm for Simon's problem”, Proceedings of Fifth Israeli Symposium on Theory of Computing and Systems — ISTCS '97, June 1997, IEEE Computer Society Press, pp. 12–23.
J. Larry Carter and Mark N. Wegman, “Universal classes of hash functions”, Journal of Computer and System Sciences, Vol. 18, no. 2, 1979, pp. 143–154.
Shafi Goldwasser, Silvio Micali and Ronald L. Rivest, “A digital signature scheme secure against adaptive chosen-message attacks”, SIAM Journal on Computing, Vol. 17, 1988, pp. 281–308.
Lov K. Grover, “A fast quantum mechanical algorithm for database search”, Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 212–219.
Lov K. Grover, “Quantum mechanics helps in searching for a needle in a haystack”, Physical Review Letters, Vol. 79, no. 2, 14 July 1997, pp. 325–328.
Eric Rains, talk given at AT&T, Murray Hill, New Jersey, 12 March 1997.
Daniel R. Simon, “On the power of quantum computation”, SI AM Journal on Computing, Vol. 26, no. 5, October 1997, pp. 1474–1483.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brassard, G., HØyer, P., Tapp, A. (1998). Quantum cryptanalysis of hash and claw-free functions. In: Lucchesi, C.L., Moura, A.V. (eds) LATIN'98: Theoretical Informatics. LATIN 1998. Lecture Notes in Computer Science, vol 1380. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054319
Download citation
DOI: https://doi.org/10.1007/BFb0054319
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64275-6
Online ISBN: 978-3-540-69715-2
eBook Packages: Springer Book Archive