Quantum algorithm to find invariant linear structure of \(MD\) hash functions. (English) Zbl 1311.81089
Summary: In this paper, we consider a special problem. “Given a function \(f\): \(\{0, 1\}^{n}\to \{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.
MSC:
| 81P68 | Quantum computation |
| 81P45 | Quantum information, communication, networks (quantum-theoretic aspects) |
| 68Q12 | Quantum algorithms and complexity in the theory of computing |
References:
| [1] | Simon, D.R.: On the power of quantum computation. SIAM J. Comput. 26(5), 1474-1483 (1997) · Zbl 0883.03024 |
| [2] | 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) · Zbl 1192.68255 |
| [3] | 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) |
| [4] | Kutin, S.: Quantum lower bound for the collision problem with small range. Theory Comput. 1(1), 29-36 (2005) · Zbl 1213.68286 · doi:10.4086/toc.2005.v001a002 |
| [5] | Ambainis, A.: Polynomial degree and lower bounds in quantum complexity: collision and element distinctness with small range. Theory Comput. 1(1), 37-46 (2005) · Zbl 1213.68281 · doi:10.4086/toc.2005.v001a003 |
| [6] | Wang, X., Yu, H.: How to Break MD5 and Other Hash Functions. Advances in Cryptology-EUROCRYPT. Springer, Berlin (2005) · Zbl 1137.94359 |
| [7] | Wang, X., Yin, Y.L., Yu, H.: Finding Collisions in the Full SHA-1. Advances in Cryptology-CRYPTO. Springer, Berlin (2005) · Zbl 1145.94454 |
| [8] | Wang, X., Lai, X., Feng, D., et al.: Cryptanalysis of the Hash Functions MD4 and RIPEMD. Advances in Cryptology-EUROCRYPT. Springer, Berlin (2005) |
| [9] | Wang, X., Yu, H., Yin, Y.L.: Efficient Collision Search Attacks on SHA-0. Advances in Cryptology-CRYPTO, 1st edn. Springer, Berlin (2005) · Zbl 1145.94455 |
| [10] | Kashefi, E., Kent, A., Vedral, V., et al.: Comparison of quantum oracles. Phys. Rev. A 65(5), 050304 (2002) · Zbl 1005.11507 |
| [11] | Vedral, V., Barenco, A., Ekert, A.: Quantum networks for elementary arithmetic operations. Phys. Rev. A 54(1), 147 (1996) · doi:10.1103/PhysRevA.54.147 |
| [12] | Rivest, R.L.: The MD4 Message-Digest Algorithm. Advances in Cryptology, Crypto’90. Springer, Berlin (1991) · Zbl 0800.68418 |
| [13] | Rivest, R.L.: The MD5 Message-Digest Algorithm, Request for Comments (RFC 1320), Internet Activities Board, Internet Privacy Task Force (1992) |
| [14] | Secure Hash Standard. Federal Information Processing Standard Publication 180, U.S. Department of Commerce, National Institute of Standards and Technology (1993) |
| [15] | National Institute of Standards and Technology (NIST) FIPS Publication 180-1: secure Hash Standard (1994) |
| [16] | National Institute of Standards and Technology (NIST), FIPS 180-2(2002). http://csrc.nist.gov/encryption/tkhash.html |
| [17] | Cleve, R.: An introduction to quantum complexity theory. In: Collected Papers on Quantum Computation and Quantum Information Theory, pp. 103-127 (2000) · Zbl 1213.68286 |
| [18] | Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303-332 (1999) · Zbl 1005.11507 · doi:10.1137/S0036144598347011 |
| [19] | Proos, J., Zalka, C.: Shor’s discrete logarithm quantum algorithm for elliptic curves. Quantum Inf. Comput. 3, 317-344 (2003) · Zbl 1152.81800 |
| [20] | Darrel, H., Alfrend, M., Scott, V.: Guide to Elliptic Curve Cryptography. Springer, Berlin (2004) · Zbl 1059.94016 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
