The security level of a cipher is a key parameter. While general-purpose quantum computers significantly threaten modern symmetric ciphers, other quantum approaches like quantum annealing have been less concerning. However, this paper argues that a quantum annealer specifically designed to attack Grain 128 and Grain 128a ciphers could soon be technologically feasible. Such an annealer would require 5,751 (6,761) qubits and 77,496 (94,865) couplers, with a qubit connectivity of 225 (245). This work also shows that modern stream ciphers like Grain 128 and Grain 128a may be vulnerable to quantum annealing attacks. Although the exact complexity of quantum annealing is unknown, heuristic estimates suggest that for many problems with$N$variables, a$\sqrt{N}$exponential advantage over simulated annealing may hold. We detail how to transform algebraic attacks on Grain ciphers into the QUBO problem, making our attack potentially more efficient than classical brute-force methods. We demonstrate that applying our attack to rescaled Grain cipher versions, Grain$l$and Grain$la$, overtakes brute-force and Grover’s attacks for sufficiently large$l$, assuming quantum annealing’s exponential benefit over simulated annealing.
The security level of a cipher is a key parameter. While general-purpose quantum computers significantly threaten modern symmetric ciphers, other quantum approaches like quantum annealing have been less concerning. However, this paper argues that a quantum annealer specifically designed to attack Grain 128 and Grain 128a ciphers could soon be technologically feasible. Such an annealer would require 5,751 (6,761) qubits and 77,496 (94,865) couplers, with a qubit connectivity of 225 (245). This work also shows that modern stream ciphers like Grain 128 and Grain 128a may be vulnerable to quantum annealing attacks. Although the exact complexity of quantum annealing is unknown, heuristic estimates suggest that for many problems withNvariables, aNexponential advantage over simulated annealing may hold. We detail how to transform algebraic attacks on Grain ciphers into the QUBO problem, making our attack potentially more efficient than classical brute-force methods. We demonstrate that applying our attack to rescaled Grain cipher versions, Grainland Grainla, overtakes brute-force and Grover’s attacks for sufficiently largel, assuming quantum annealing’s exponential benefit over simulated annealing.
In this paper, we proposed a simplified version of the Grain-128 stream cipher and developed a corresponding quantum circuit. Leveraging Grover's algorithm, we demonstrate the ability to recover a key given plaintext, initialization vector (IV), and corresponding ciphertext through various methods, including single pair, double pair series, and double pair parallel approaches. Using the Qiskit Quantum Development Kit (QDK), we conduct these attacks and estimate the required quantum resources. Our research reveals that the simplified grain cipher is vulnerable to quantum attacks, showing how quantum computing could affect cryptographic systems.
Abstract A significant amount of study is being done to review the security promises made for the various ciphers now in use as a result of the development of quantum computing technology. A general attack against symmetric key cryptography primitives that can reduce search costs to the square root is Grover's search algorithm. To implement Grover's algorithm, it is necessary that the target cipher be implemented as a quantum circuit. Despite being relatively new, this area of study has received significant attention from the research community. The authors have estimated the cost of Grover's key search attack against the stream cipher Atom, for the first time, under circuit depth restrictions defined in National Institute of Standards and Technology (NIST) PQC standardisation process. The authors implement the quantum circuit of Atom in QISKIT, (open‐source software development kit for working with quantum computers running on IBM Quantum Experience). The results are also compared with other existing literature on LFSR‐based stream ciphers, such as Grain‐v1, Grain‐128‐AEAD, and Lizard. The authors also find that, to the best of their knowledge, in the existing literature on estimating the cost of Grover's attack on symmetric ciphers, Atom is the only 128‐bit key cipher that meets the threshold of ≈2 170 set by NIST for quantum security of 128‐bit key ciphers. The authors also analyse the security of Atom against quantum TMDTO attacks.
This paper presents the transformation method of the system of algebraic equations describing the symmetric cipher into the QUBO problem. After transformation of given equationsf0,f1,…,fn−1f0,f1,...,fn-1to equations over integersf0′,f1′,…,fn−1′f0',f1',...,fn-1', one can linearize each, obtainingflini′=lin(fi′)flini'=lin(fi'), fori=0,n−1i=0,n-1¯, wherelinlindenotes linearization operation. Finally, one can obtain problem in the QUBO form as(flin0′)2+⋯+(flinn−1′)2+Pen−C(flin0')2+⋯+(flinn-1')2+Pen-C, wherePenPendenotes penalties obtained during linearization of equations,nnis the number of equations andCCis constant appearing in the polynomial(flin0′)2+⋯+(flinn−1′)2+Pen(flin0')2+⋯+(flinn-1')2+Pen. This paper presents the transformation method of SPN block ciphers to the QUBO problem. What is more, we present the results of the transformation of the complete AES-128 cipher to the QUBO problem, where the number of variables of the equivalent QUBO problem equals approximately 30,026. It is worth noting that AES-128 is much easier to solve using quantum annealing than the factorization problem and the discrete logarithm problem of a similar level of security. For example, factorizing a 3072 bit long RSA integer using quantum annealing requires a QUBO problem of about 2,360,000 variables.
“Grover's Algorithm: Quantum Search” explores Grover's Algorithm in the context of quantum search, beginning with an overview of its mechanics. The section includes a literature survey that covers Grover's algorithm, stream ciphers, and the Grover attack, as well as quantum resource estimation. The section then introduces a simplified 4-bit Grain cipher (with a 4-bit key and 4-bit IV), detailing its design, initialization, and key stream generation. Following this, the chapter discusses about key recovery using Grover's algorithm, with an emphasis on quantum circuit development for the simplified Grain 4-bit cipher. It outlines key steps in the circuit, such as executing the Boolean function and XORing the NFSR's fourth bit. Further, the section details the development of a Grover attack quantum circuit, describing both single and double pair methods. Experimental results are provided across multiple cases, with a summary of test cases and classical computation times. Quantum resource estimation, including the costs associated with the simplified Grain 4-bit cipher and the Grover oracle, is analyzed. The section concludes with a discussion on the results, classical and quantum resource estimations, and the potential for future enhancements to the approach.
The application in cryptography of quantum algorithms for prime factorization fostered the interest in quantum computing. However, quantum computers, and particularly quantum annealers, can also be helpful to construct secure cryptographic keys. Indeed, finding robust Boolean functions for cryptography is an important problem in sequence ciphers, block ciphers, and hash functions, among others. Due to the superexponential size O(22n) of the associated space, finding n-variable Boolean functions with global cryptographic constraints is computationally hard. This problem has already been addressed employing generic low-connected incoherent D-Wave quantum annealers. However, the limited connectivity of the Chimera graph, together with the exponential growth in the complexity of the Boolean-function design problem, limit the problem scalability. Here, we propose a special-purpose coherent quantum-annealing architecture with three couplers per qubit, designed to optimally encode the bent-function design problem. A coherent quantum annealer with this tree-type architecture has the potential to solve the eight-variable bent-function design problem, which is classically unsolved, with only 127 physical qubits and 126 couplers. This paves the way to reach useful quantum supremacy within the framework of quantum annealing for cryptographic purposes.
The application in cryptography of quantum algorithms for prime factorization fostered the interest in quantum computing. However, quantum computers, and particularly quantum annealers, can also be helpful to construct secure cryptographic keys. Indeed, finding robust Boolean functions for cryptography is an important problem in sequence ciphers, block ciphers, and hash functions, among others. Due to the super-exponential size O(22n) of the associated space, finding n-variable Boolean functions with global cryptographic constraints is computationally hard. This problem has already been addressed employing generic low-connected incoherent D-Wave quantum annealers. However, the limited connectivity of the Chimera graph, together with the exponential growth in the complexity of the Boolean function design problem, limit the problem scalability. Here, we propose a special-purpose coherent quantum annealing architecture with three couplers per qubit, designed to optimally encode the bent function design problem. A coherent quantum annealer with this tree-type architecture has the potential to solve the 8-variable bent function design problem, which is classically unsolved, with only 127 physical qubits and 126 couplers. This paves the way to reach useful quantum supremacy within the framework of quantum annealing for cryptographic purposes.