Abstract
In this paper, we consider a special problem. “Given a function \(f\): \(\{0, 1\}^{n}\rightarrow \{0, 1\}^{m}\). Suppose there exists a n-bit string \(\alpha \in \{0, 1\}^{n}\) subject to \(f(x\oplus \alpha )=f(x)\) for \(\forall x\in \{0, 1\}^{n}\). We only know the Hamming weight \(W(\alpha )=1\), and find this \(\alpha \).” We present a quantum algorithm with “Oracle” to solve this problem. The successful probability of the quantum algorithm is \((\frac{2^{l}-1}{2^{l}})^{n-1}\), and the time complexity of the quantum algorithm is \(O(\log (n-1))\) for the given Hamming weight \(W(\alpha )=1\). As an application, we present a quantum algorithm to decide whether there exists such an invariant linear structure of the \(MD\) hash function family as a kind of collision. Then, we provide some consumptions of the quantum algorithms using the time–space trade-off.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Simon, D.R.: On the power of quantum computation. SIAM J. Comput. 26(5), 1474–1483 (1997)
Aaronson, S.: Quantum lower bound for the collision problem. In: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, pp. 635–642. ACM, New York (2002)
Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, pp. 513–519. IEEE (2002)
Kutin, S.: Quantum lower bound for the collision problem with small range. Theory Comput. 1(1), 29–36 (2005)
Ambainis, A.: Polynomial degree and lower bounds in quantum complexity: collision and element distinctness with small range. Theory Comput. 1(1), 37–46 (2005)
Wang, X., Yu, H.: How to Break MD5 and Other Hash Functions. Advances in Cryptology-EUROCRYPT. Springer, Berlin (2005)
Wang, X., Yin, Y.L., Yu, H.: Finding Collisions in the Full SHA-1. Advances in Cryptology-CRYPTO. Springer, Berlin (2005)
Wang, X., Lai, X., Feng, D., et al.: Cryptanalysis of the Hash Functions MD4 and RIPEMD. Advances in Cryptology-EUROCRYPT. Springer, Berlin (2005)
Wang, X., Yu, H., Yin, Y.L.: Efficient Collision Search Attacks on SHA-0. Advances in Cryptology-CRYPTO, 1st edn. Springer, Berlin (2005)
Kashefi, E., Kent, A., Vedral, V., et al.: Comparison of quantum oracles. Phys. Rev. A 65(5), 050304 (2002)
Vedral, V., Barenco, A., Ekert, A.: Quantum networks for elementary arithmetic operations. Phys. Rev. A 54(1), 147 (1996)
Rivest, R.L.: The MD4 Message-Digest Algorithm. Advances in Cryptology, Crypto’90. Springer, Berlin (1991)
Rivest, R.L.: The MD5 Message-Digest Algorithm, Request for Comments (RFC 1320), Internet Activities Board, Internet Privacy Task Force (1992)
Secure Hash Standard. Federal Information Processing Standard Publication 180, U.S. Department of Commerce, National Institute of Standards and Technology (1993)
National Institute of Standards and Technology (NIST) FIPS Publication 180-1: secure Hash Standard (1994)
National Institute of Standards and Technology (NIST), FIPS 180–2(2002). http://csrc.nist.gov/encryption/tkhash.html
Cleve, R.: An introduction to quantum complexity theory. In: Collected Papers on Quantum Computation and Quantum Information Theory, pp. 103–127 (2000)
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999)
Proos, J., Zalka, C.: Shor’s discrete logarithm quantum algorithm for elliptic curves. Quantum Inf. Comput. 3, 317–344 (2003)
Darrel, H., Alfrend, M., Scott, V.: Guide to Elliptic Curve Cryptography. Springer, Berlin (2004)
Acknowledgments
WanQing Wu: Supported by the Fundamental Research Funds for the Central Universities (No. 2012211020213). HuanGuo Zhang: Supported by the Major Research Plan of the National Natural Science Foundation of China (No. 91018008), the National Natural Science Foundation of China (No. 61303212, 61202386), and Major State Basic Research Development Program of china (No. 2014CB340600). E-mail: liss@whu.edu.cn
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wu, W., Zhang, H., Mao, S. et al. Quantum algorithm to find invariant linear structure of MD hash functions. Quantum Inf Process 14, 813–829 (2015). https://doi.org/10.1007/s11128-014-0909-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11128-014-0909-5