Abstract
Quantum computers that take advantage of quantum mechanics efficiently model and solve certain hard problems. In particular, quantum computers are considered a major threat to cryptography in the near future. In this current situation, analysis of quantum computer attacks on ciphers is a major way to evaluate the security of ciphers. Several studies of quantum circuits for block ciphers have been presented. However, quantum implementations for Authenticated Encryption with Associated Data (AEAD) are not actively studied.
In this paper, we present a quantum implementation for authenticated ciphers of SPARKLE, a finalist candidate of the National Institute of Standards and Technology (NIST) Lightweight Cryptography (LWC) project. We apply various techniques for optimization by considering trade-off between qubits and gates/depth in quantum computers. Based on proposed quantum circuit, we estimate the cost of applying key search using Grover’s algorithm, which degrades the security of symmetric key ciphers. Afterward, we further explore the expected level of post-quantum security for SPARKLE on the basis of post-quantum security requirements of NIST.
This work was partly supported by Institute for Information & communications Technology Promotion (IITP) grant funded by the Korea government (MSIT) (No.2018-0-00264, Research on Blockchain Security Technology for IoT Services, 50%) and this work was partly supported by Institute for Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (<Q|Crypton>, No. 2019-0-00033, Study on Quantum Security Evaluation of Cryptography based on Computational Quantum Complexity, 50%).
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
Similar content being viewed by others
References
Abrams, D.S., Lloyd, S.: Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems. Phys. Rev. Lett. 81(18), 3992 (1998)
Tsai, K.-L., Leu, F.-Y., Wu, T.-H., Chiou, S.S., Liu, Y.-W., Liu, H.-Y.: A secure ECC-based electronic medical record system. J. Internet Serv. Inf. Secur. (JISIS) 4, 47–57 (2014)
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999)
Singh, K., Rangan, C.P., Banerjee, A.: Lattice based efficient threshold public key encryption scheme. J. Wirel. Mob. Netw. Ubiquit. Comput. Dependable Appl. (JoWUA) 4, 93–107 (2013)
Grassl, M., Langenberg, B., Roetteler, M., Steinwandt, R.: Applying Grover’s algorithm to AES: quantum resource estimates. In: Takagi, T. (ed.) PQCrypto 2016. LNCS, vol. 9606, pp. 29–43. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29360-8_3
Langenberg, B., Pham, H., Steinwandt, R.: Reducing the cost of implementing the advanced encryption standard as a quantum circuit. IEEE Trans. Quantum Eng. 1, 1–12 (2020)
Jaques, S., Naehrig, M., Roetteler, M., Virdia, F.: Implementing Grover oracles for quantum key search on AES and LowMC. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 280–310. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_10
Zou, J., Wei, Z., Sun, S., Liu, X., Wu, W.: Quantum circuit implementations of AES with fewer qubits. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12492, pp. 697–726. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64834-3_24
Jang, K., Choi, S., Kwon, H., Kim, H., Park, J., Seo, H.: Grover on Korean block ciphers. Appl. Sci. 10(18), 6407 (2020)
Jang, K., Song, G., Kim, H., Kwon, H., Kim, H., Seo, H.: Efficient implementation of PRESENT and GIFT on quantum computers. Appl. Sci. 11(11), 4776 (2021)
Jang, K., Choi, S., Kwon, H., Seo, H.: Grover on speck: quantum resource estimates. Cryptology ePrint Archive (2020)
Jang, K., et al.: Grover on PIPO. Electronics 10(10), 1194 (2021)
Bijwe, S., Chauhan, A.K., Sanadhya, S.K.: Quantum search for lightweight block ciphers: GIFT, SKINNY, SATURNIN. Cryptology ePrint Archive (2020)
Baksi, A., Jang, K., Song, G., Seo, H., Xiang, Z.: Quantum implementation and resource estimates for rectangle and knot. Quantum Inf. Process. 20(12), 1–24 (2021). https://doi.org/10.1007/s11128-021-03307-6
Beierle, C., et al.: Schwaemm and Esch: lightweight authenticated encryption and hashing using the sparkle permutation family. NIST Round, vol. 2 (2019)
Draper, T.G., Kutin, S.A., Rains, E.M., Svore, K.M.: A logarithmic-depth quantum carry-lookahead adder. arXiv preprint quant-ph/0406142 (2004)
Takahashi, Y., Tani, S., Kunihiro, N.: Quantum addition circuits and unbounded fan-out. arXiv preprint arXiv:0910.2530 (2009)
Draper, T.G.: Addition on a quantum computer. arXiv preprint quant-ph/0008033 (2000)
Cuccaro, S.A., Draper, T.G., Kutin, S.A., Moulton, D.P.: A new quantum ripple-carry addition circuit. arXiv preprint quant-ph/0410184 (2004)
Amy, M., Maslov, D., Mosca, M., Roetteler, M., Roetteler, M.: A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 32, 818–830 (2013)
Fedorov, A., Steffen, L., Baur, M., da Silva, M.P., Wallraff, A.: Implementation of a Toffoli gate with superconducting circuits. Nature 481(7380), 170–172 (2012)
Ralph, T., Resch, K., Gilchrist, A.: Efficient Toffoli gates using qudits. Phys. Rev. A 75(2), 022313 (2007)
Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschr. Phys. 46, 493–505 (1998)
NIST. Submission requirements and evaluation criteria for the post-quantum cryptography standardization process (2016). https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf
Almazrooie, M., Samsudin, A., Abdullah, R., Mutter, K.N.: Quantum reversible circuit of AES-128. Quantum Inf. Process. 17, 1–30 (2018)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 Springer Nature Switzerland AG
About this paper
Cite this paper
Yang, Y., Jang, K., Kim, H., Song, G., Seo, H. (2023). Grover on SPARKLE. In: You, I., Youn, TY. (eds) Information Security Applications. WISA 2022. Lecture Notes in Computer Science, vol 13720. Springer, Cham. https://doi.org/10.1007/978-3-031-25659-2_4
Download citation
DOI: https://doi.org/10.1007/978-3-031-25659-2_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-25658-5
Online ISBN: 978-3-031-25659-2
eBook Packages: Computer ScienceComputer Science (R0)