Quantum key-recovery attack on Feistel structures
|
摘要
Post-quantum cryptography has drawn considerable attention from cryptologists on a global scale. At Asiacrypt 2017, Leander and May combined Grover's and Simon's quantum algorithms to break the FX-based block ciphers, which were introduced by Kilian and Rogaway to strengthen DES. In this study,we investigate the Feistel constructions using Grover's and Simon's algorithms to generate new quantum key-recovery attacks on different rounds of Feistel constructions. Our attacks require 2~(0.25nr-0.75n) quantum queries to break an r-round Feistel construction. The time complexity of our attacks is less than that observed for quantum brute-force search by a factor of 2~(0.75n). When compared with the best classical attacks, i.e.,Dinur et al.'s attacks at CRYPTO 2015, the time complexity is reduced by a factor of 2~(0.5n) without incurring any memory cost.
Post-quantum cryptography has drawn considerable attention from cryptologists on a global scale. At Asiacrypt 2017, Leander and May combined Grover's and Simon's quantum algorithms to break the FX-based block ciphers, which were introduced by Kilian and Rogaway to strengthen DES. In this study,we investigate the Feistel constructions using Grover's and Simon's algorithms to generate new quantum key-recovery attacks on different rounds of Feistel constructions. Our attacks require 2~(0.25nr-0.75n) quantum queries to break an r-round Feistel construction. The time complexity of our attacks is less than that observed for quantum brute-force search by a factor of 2~(0.75n). When compared with the best classical attacks, i.e.,Dinur et al.'s attacks at CRYPTO 2015, the time complexity is reduced by a factor of 2~(0.5n) without incurring any memory cost.
Post-quantum cryptography has drawn considerable attention from cryptologists on a global scale. At Asiacrypt 2017, Leander and May combined Grover's and Simon's quantum algorithms to break the FX-based block ciphers, which were introduced by Kilian and Rogaway to strengthen DES. In this study,we investigate the Feistel constructions using Grover's and Simon's algorithms to generate new quantum key-recovery attacks on different rounds of Feistel constructions. Our attacks require 2~(0.25nr-0.75n) quantum queries to break an r-round Feistel construction. The time complexity of our attacks is less than that observed for quantum brute-force search by a factor of 2~(0.75n). When compared with the best classical attacks, i.e.,Dinur et al.'s attacks at CRYPTO 2015, the time complexity is reduced by a factor of 2~(0.5n) without incurring any memory cost.
引文
1 Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput, 1997, 26:1484–1509
2 Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Commun ACM, 1978, 21:120–126
3 Even S, Mansour Y. A construction of a cipher from a single pseudorandom permutation. J Cryptol, 1997, 10:151–161
4 Kuwakado H, Morii M. Security on the quantum-type even-mansour cipher. In:Proceedings of International Symposium on Information Theory and Its Applications, Honolulu, 2012. 312–316
5 Kaplan M, Leurent G, Leverrier A, et al. Breaking symmetric cryptosystems using quantum period finding. In:Advances in Cryptology-CRYPTO 2016. Berlin:Springer-Verlag, 2016. 207–237
6 Moody D. The ship has sailed:the NIST post-quantum cryptography“competition”(invited talk). In:Advances in Cryptology-ASIACRYPT 2017. Berlin:Springer, 2017
7 Boneh D, Zhandry M. Secure signatures and chosen ciphertext security in a quantum computing world. In:Advances in Cryptology-CRYPTO 2013. Berlin:Springer, 2013. 361–379
8 Grover L K. A fast quantum mechanical algorithm for database search. In:Proceedings of the 28th Annual ACM Symposium on Theory of Computing, Philadelphia, 1996. 212–219
9 Simon D R. On the power of quantum computation. SIAM J Comput, 1997, 26:1474–1483
10 Feistel H, Notz W A, Smith J L. Some cryptographic techniques for machine-to-machine data communications. Proc IEEE, 1975, 63:1545–1554
11 International Organization for Standardization(ISO). Information Technology-Security TechniquesEncryption Algorithms-Part 3:Block Ciphers. International Standard-ISO/IEC 18033-3. 2010.https://www.iso.org/standard/54531.html
12 Luby M G, Rackoff C. How to construct pseudorandom permutations from pseudorandom functions. SIAM J Comput,1988, 17:373–386
13 Kuwakado H, Morii M. Quantum distinguisher between the 3-round Feistel cipher and the random permutation. In:Proceedings of International Symposium on Information Theory, Austin, 2010. 2682–2685
14 Dinur I, Dunkelman O, Keller N, et al. New attacks on Feistel structures with improved memory complexities. In:Advances in Cryptology-CRYPTO 2015, Part I. Berlin:Springer, 2015. 433–454
15 Brassard G, Hoyer P, Mosca M, et al. Quantum amplitude amplification and estimation. 2000.Ar Xiv:quant-ph/0005055
16 Leander G, May A. Grover meets simon-quantumly attacking the FX-construction. In:Advances in CryptologyASIACRYPT 2017, Part II. Berlin:Springer, 2017. 161–178
17 Kilian J, Rogaway P. How to protect DES against exhaustive key search. In:Advances in Cryptology-CRYPTO1996. Berlin:Springer, 1996. 252–267
18 Borghoff J, Canteaut A, G¨uneysu T, et al. PRINCE—a low-latency block cipher for pervasive computing applications—extended abstract. In:Advances in Cryptology-ASIACRYPT 2012. Berlin:Springer, 2012. 208–225
19 Albrecht M R, Driessen B, Kavun E B, et al. Block ciphers-focus on the linear layer(feat. PRIDE). In:Advances in Cryptology-CRYPTO 2014. Berlin:Springer, 2014. 57–76
2 Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Commun ACM, 1978, 21:120–126
3 Even S, Mansour Y. A construction of a cipher from a single pseudorandom permutation. J Cryptol, 1997, 10:151–161
4 Kuwakado H, Morii M. Security on the quantum-type even-mansour cipher. In:Proceedings of International Symposium on Information Theory and Its Applications, Honolulu, 2012. 312–316
5 Kaplan M, Leurent G, Leverrier A, et al. Breaking symmetric cryptosystems using quantum period finding. In:Advances in Cryptology-CRYPTO 2016. Berlin:Springer-Verlag, 2016. 207–237
6 Moody D. The ship has sailed:the NIST post-quantum cryptography“competition”(invited talk). In:Advances in Cryptology-ASIACRYPT 2017. Berlin:Springer, 2017
7 Boneh D, Zhandry M. Secure signatures and chosen ciphertext security in a quantum computing world. In:Advances in Cryptology-CRYPTO 2013. Berlin:Springer, 2013. 361–379
8 Grover L K. A fast quantum mechanical algorithm for database search. In:Proceedings of the 28th Annual ACM Symposium on Theory of Computing, Philadelphia, 1996. 212–219
9 Simon D R. On the power of quantum computation. SIAM J Comput, 1997, 26:1474–1483
10 Feistel H, Notz W A, Smith J L. Some cryptographic techniques for machine-to-machine data communications. Proc IEEE, 1975, 63:1545–1554
11 International Organization for Standardization(ISO). Information Technology-Security TechniquesEncryption Algorithms-Part 3:Block Ciphers. International Standard-ISO/IEC 18033-3. 2010.https://www.iso.org/standard/54531.html
12 Luby M G, Rackoff C. How to construct pseudorandom permutations from pseudorandom functions. SIAM J Comput,1988, 17:373–386
13 Kuwakado H, Morii M. Quantum distinguisher between the 3-round Feistel cipher and the random permutation. In:Proceedings of International Symposium on Information Theory, Austin, 2010. 2682–2685
14 Dinur I, Dunkelman O, Keller N, et al. New attacks on Feistel structures with improved memory complexities. In:Advances in Cryptology-CRYPTO 2015, Part I. Berlin:Springer, 2015. 433–454
15 Brassard G, Hoyer P, Mosca M, et al. Quantum amplitude amplification and estimation. 2000.Ar Xiv:quant-ph/0005055
16 Leander G, May A. Grover meets simon-quantumly attacking the FX-construction. In:Advances in CryptologyASIACRYPT 2017, Part II. Berlin:Springer, 2017. 161–178
17 Kilian J, Rogaway P. How to protect DES against exhaustive key search. In:Advances in Cryptology-CRYPTO1996. Berlin:Springer, 1996. 252–267
18 Borghoff J, Canteaut A, G¨uneysu T, et al. PRINCE—a low-latency block cipher for pervasive computing applications—extended abstract. In:Advances in Cryptology-ASIACRYPT 2012. Berlin:Springer, 2012. 208–225
19 Albrecht M R, Driessen B, Kavun E B, et al. Block ciphers-focus on the linear layer(feat. PRIDE). In:Advances in Cryptology-CRYPTO 2014. Berlin:Springer, 2014. 57–76