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.
Grover’s search algorithm allows a quantum adversary to find a
k-bit secret key of a block cipher by making O(
2k/2) block cipher queries. Resistance of a block cipher to such an attack is evaluated by quantum resources required to implement Grover’s oracle for the target cipher. The quantum resources are typically estimated by the
T-depth of its circuit implementation and the number of qubits used by the circuit (width). Since the AES S-box is the only component which requires
T-gates in a quantum implementation of AES, recent research has put its focus on efficient implementation of the AES S-box. However, any efficient implementation with low
T-depth will not be practical in the real world without considering qubit consumption of the implementation. In this work, we propose three methods of trade-off between time and space for the quantum implementation of the AES S-box. In particular, one of our methods turns out to use the smallest number of qubits among the existing methods, significantly reducing its
T-depth.