Demonstration of Grover’s algorithm for retrieving secret keys in a basic SPN block cipher
,
*
,
and
Article Sidebar
Full Text: 
PDF
Main Article Content
Abstract
In this study, we present in detail the application of Grover's quantum algorithm to the searching problem of the secret key of a simple SPN (Substitution–permutation network) block cipher called Yo-yo. The main goal of the paper is to clarify the construction of the quantum circuit and the operation phases of Grover's algorithm to find the secret key with the condition of knowing at least 1 pair of plaintext-ciphertext. To achieve this goal, we consider 2 cases: the case where there is a unique key that satisfies and the case where there are 2 keys that satisfy at the same time. As a result, our implementation technique, implemented in the Qiskit programming language, requires only 17 qubits to find the key of the Yo-yo block cipher correctly. This technique can be effectively applied on IBM quantum computers for large-scale SPN block ciphers, such as AES and GOST R.34.10.2015, which are widely used today.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
References
Chen, J., Liu, Q., Fan, Y., Wu, L., Li, B., & Wang, M. (2024). New Sat-based model for Quantum Circuit decision problem: Searching for low-cost quantum implementation. IACR Communications in Cryptology. https://doi.org/10.62056/anmmp-4c2h
Chung, D., Lee, S., Choi, D., & Lee, J. (2022). Alternative tower field construction for quantum implementation of the AES S-box. IEEE Transactions on Computers, 71(10), 2553–2564.
Denisenko, D. V. (2019). Quantum circuits for S-box implementation without ancilla qubits. Journal of Experimental and Theoretical Physics, 128(6), 847–855. https://doi.org/10.1134/s1063776119050108.
Grassl, M., Langenberg, B., Roetteler, M., & Steinwandt, R. (2016). Applying Grover’s algorithm to AES: Quantum Resource Estimates. Lecture Notes in Computer Science, 29–43.
Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing - STOC ’96, 212–219.
Jaques, S., Naehrig, M., Roetteler, M., & Virdia, F. (2020). Implementing Grover oracles for Quantum Key Search on AES and lowmc. Lecture Notes in Computer Science, 280–310.
Kim, P., Han, D., & Jeong, K. C. (2018). Time–space complexity of quantum search algorithms in symmetric cryptanalysis: Applying to AES and SHA-2. Quantum Information Processing, 17(12).
Lipton, R. J., & Regan, K. W. (2021). Introduction to quantum algorithms via linear algebra. The MIT Press.
Nielsen, M., & Chuang, I. (2010). Quantum Computation and Quantum Information Nielsen, Michael. Cambridge University Press.
Shannon, C. E. (1949). Communication theory of secrecy systems. The Bell system technical journal, 28(4), 656-715.