Abstract
Simon’s algorithm has shown a threat to block ciphers in the quantum setting, especially accelerating attacks with superposition queries. Sometimes it is difficult for attackers to make superposition queries, while an easier way is to use classical data then process them on quantum computers. At ASIACRYPT 2019, Bonnetain et al. proposed the offline Simon’s algorithm. But there is a gap between the classical queries and a quantum database in their work.
In this paper, we propose an algorithm involving polynomial qubits that can transform a classical database into a quantum superposition state without using QRAM. What’s more, we analyze the influence of two approaches called pre- and post-distinguisher methods for Simon’s algorithm attack. Then we run a quantum key recovery attack on Feistel structure in the Q1 model. For attacking r-round Feistel structure with n-bit block size and n/2-bit subkey, the time complexity of our attack is \(O(l\cdot 2^{n/2+2}+2^{(r-3)n/4})\) (where l is a constant), and the classical data complexity is always \(O(2^{n/2+1})\), which is much better than the classical attacks especially for \(r>5\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: FOCS 1994, pp. 124–134. IEEE Computer Society (1994). https://dblp.org/rec/conf/focs/Shor94.bib
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Miller, G.L. (eds.) STOC 1996, pp. 212–219. ACM (1996). https://doi.acm.org/10.1145/237814.237866
Simon, D.R.: On the power of quantum computation. In: FOCS 1994, pp. 116–123. IEEE Computer Society (1994). https://dblp.org/rec/conf/focs/Simon94.bib
Leander, G., May, A.: Grover meets Simon – quantumly attacking the FX-construction. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 161–178. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_6
Kaplan, M., Leurent, G., Leverrier, A., et al.: Quantum differential and linear cryptanalysis. IACR Trans. Symmetric Cryptol. 2016(1), 71–94 (2016). https://tosc.iacr.org/index.php/ToSC/article/view/536
Dong, X., Wang, X.: Quantum key-recovery attack on Feistel structures. Sci. China Inf. Sci. 61(10), 102501 (2018)
Ito, G., Hosoyamada, A., Matsumoto, R., Sasaki, Yu., Iwata, T.: Quantum chosen-ciphertext attacks against Feistel ciphers. In: Matsui, M. (ed.) CT-RSA 2019. LNCS, vol. 11405, pp. 391–411. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-12612-4_20
Kuwakado, H., Morii, M.: Quantum distinguisher between the 3-round Feistel cipher and the random permutation. In: Proceedings of 2010 International Symposium on Information Theory, pp. 2682–2685. IEEE, Austin, Texas, USA (2010)
Kuwakado, H., Morii, M.: Security on the quantum-type Even-Mansour cipher. In: Proceedings of 2012 International Symposium on Information Theory and Its Applications, pp. 312–316. IEEE, Honolulu, HI, USA (2012)
Zhandry, M.: How to construct quantum random functions. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, pp. 679–687. IEEE Computer Society, New Brunswick, NJ, USA (2012)
Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: New attacks on Feistel structures with improved memory complexities. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 433–454. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_21
Hosoyamada, A., Sasaki, Yu.: Quantum Demiric-Selçuk meet-in-the-middle attacks: applications to 6-round generic Feistel constructions. In: Catalano, D., De Prisco, R. (eds.) SCN 2018. LNCS, vol. 11035, pp. 386–403. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98113-0_21
Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17(2), 373–386 (1988)
Bonnetain, X., Hosoyamada, A., Naya-Plasencia, M., Sasaki, Yu., Schrottenloher, A.: Quantum attacks without superposition queries: the offline Simon’s algorithm. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11921, pp. 552–583. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34578-5_20
Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Breaking symmetric cryptosystems using quantum period finding. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 207–237. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_8
Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 41–69. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_3
Hosoyamada, A., Sasaki, Yu.: Cryptanalysis against symmetric-key schemes with online classical queries and offline quantum computations. In: Smart, N.P. (ed.) CT-RSA 2018. LNCS, vol. 10808, pp. 198–218. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76953-0_11
Acknowledgements
The authors would like to thank the anonymous reviewers for their helpful comments and suggestions. This work was supported by National Natural Science Foundation of China (Grant No. 62202493, 61772545, 62072207) and Scientific Research Plan of National University of Defense Technology (No. ZK21-36) and Guangdong Basic and Applied Basic Research Foundation (No. 2022A1515140090).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Yu, B., Shi, T., Dong, X., Shen, X., Luo, Y., Sun, B. (2024). Quantum Attacks: A View of Data Complexity on Offline Simon’s Algorithm. In: Ge, C., Yung, M. (eds) Information Security and Cryptology. Inscrypt 2023. Lecture Notes in Computer Science, vol 14527. Springer, Singapore. https://doi.org/10.1007/978-981-97-0945-8_19
Download citation
DOI: https://doi.org/10.1007/978-981-97-0945-8_19
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-97-0944-1
Online ISBN: 978-981-97-0945-8
eBook Packages: Computer ScienceComputer Science (R0)