In this paper, various types of quantum circuits for DES components are proposed to analyze the trade-offs in quantum resources for both DES and TDES block ciphers. Specifically, multiple optimized structures within the DES framework are devised, and by integrating different elements from each type, 34 possible configurations for the DES block cipher are generated. The required quantum resources for these configurations are then estimated, identifying not only qubit-optimized and depth-optimized circuits but also those achieving a balanced trade-off between qubit and circuit depth. Building on these optimized DES designs, TDES circuits are constructed, and the corresponding cost of a Grover-based attack on the TDES is estimated.
In this paper, various types of quantum circuits for DES components are proposed to analyze the trade-offs in quantum resources for both DES and TDES block ciphers. Specifically, multiple optimized structures within the DES framework are devised, and by integrating different elements from each type, 34 possible configurations for the DES block cipher are generated. The required quantum resources for these configurations are then estimated, identifying not only qubit-optimized and depth-optimized circuits but also those achieving a balanced trade-off between qubit and circuit depth. Building on these optimized DES designs, TDES circuits are constructed, and the corresponding cost of a Grover-based attack on the TDES is estimated.
Quantum computing enabled cryptanalytic techniques are able to concretely reduce the security margin of existing cryptographic primitives. While this reduction is only polynomial for symmetric cryptosystems, it still provides a reduction in their security margin. In this work, we propose a detailed quantum circuit designed to cryptanalyze both the Data Encryption Standard (DES) cryptosystem, and its successor Triple-DES (3DES), currently standardized in ISO/IEC 18033–3, and still widely employed in satellite data and bank card encryption. To do so, we introduce the first quantum circuit implementation of the 8 substitution tables (a.k.a. S-boxes), applying a bitslicing strategy, which is currently the most efficient classical combinatorial circuit design in terms of number of two inputs Boolean gates. Secondly, we present the complete quantum circuits required to attack both DES and 3DES leveraging Grover's algorithm. We provide finite regime, closed form equations, delineating the circuits complexities in terms of the number of qubits, gates, depth and number of qubits multiplied by depth. The complexity analysis is based on two distinct gate sets: a NOT-CNOT-Toffoli (NCT) extended with the Hadamard gate; and the fault-tolerant Clifford+T. Finally, akin to the classical attack to the 3DES, we introduce a meet-in-the-middle strategy relying on an exponential amount of Quantum Random Access Memory. Our findings show that the 3DES with keying option 2, the most widely employed variant of 3DES, can be attacked with a circuit depth of approximately267and less than a thousand qubits. This is close to the264value suggested by NIST for the depth achievable sequentially by a single quantum computer in a decade. Our technique can be further sped up parallelizing the approach onto multiple devices, pointing to the practicality of cryptanalyzing 3DES in such a scenario.
With the advancement of quantum computing, quantum circuit implementations of symmetric cryptographic algorithms are essential for evaluating their resistance to quantum attacks. As an ISO-standardized cipher, the efficient quantum circuit construction of Camellia is of great significance. Focusing on minimizing the DW-cost (qubits × Toffoli-depth) while balancing ancilla qubits and Toffoli-depth, this paper proposes an optimized quantum circuit design for Camellia. Specifically: (1) using a serial-multiplication and out-of-place inversion architecture under composite-field decomposition, combined with hierarchical screening for parallelizing bilinear multiplications, a compact in-place S-box quantum circuit is constructed with a DW-cost of 276, 28% lower than the state of the art; (2) a low-gate-count linear-layer circuit is obtained via heuristic search, and gate-sequence reordering then reduces the full depth from 9 to 7 without increasing the gate count; (3) Camellia-128/192/256 quantum circuits are constructed with DW-costs of 119,168, 257,664, and 257,664, achieving reductions of 48%, 52%, and 52% respectively over prior work. A pipelined Grover oracle is further designed and the total resources required for a full Grover search attacking Camellia are evaluated. For Camellia-128, the complete Grover search requires a T-depth of 2.10 × 2⁷⁶ and a total TDW-cost (qubits × T-depth) of 1.00 × 2⁸⁶, reducing T-depth by 75% and TDW-cost by 84% over prior work. The first full Grover search resource estimates for Camellia-192/256 are also presented, with T-depths of 7.20 × 2¹⁰⁸ and 8.11 × 2¹⁴⁰ and TDW-costs of 2.03 × 2¹²³ and 2.79 × 2¹⁵³, respectively. These results show that Grover's attack on Camellia requires fewer quantum resources than on AES at the 128-bit level, implying comparatively weaker post-quantum security at that key size, while the picture reverses at larger key sizes (Section 4).
ABSTRACT Quantum computing environments make block ciphers susceptible to exhaustive key search attacks utilizing Grover's algorithm. However, such quantum‐based attacks remain impractical unless the targeted cipher is directly implemented on a quantum platform. Moreover, their efficiency significantly depends on the quantum circuit design and optimization of the block cipher in question. The cost of a quantum circuit implementation is typically measured by two main metrics: the number of qubits and the circuit depth ( T ‐depth). For most block ciphers, the S‐box is the principal factor contributing to increased T ‐depth and additional qubit requirements. This paper presents a method for generating quantum circuits directly from lookup tables of S‐boxes applicable to arbitrary block ciphers. We illustrate our approach using quantum circuit implementations of the PRESENT and DES ciphers as practical examples. Our proposed method is expected to efficiently implement arbitrary S‐boxes by employing polynomial evaluation, thus balancing time–space complexity.
An efficient quantum implementation of the advanced encryption standard (AES) is crucial for reducing the complexity of implementing an exhaustive key search through Grover’s algorithm. In this paper, we study how to construct resource-efficient quantum circuits for AES. We consider the product of T-gates depth and width (TDW) and the product of full depth and width (FDW) as optimization targets. We propose a generic method, called the controlled control qubit cascade (CCQC) technique, to construct quantum circuits for nonlinear components with reduced TDW and FDW. Using this, we construct a quantum circuit for the AES S-box. Compared with recent work presented at ASIACRYPT 2023, our S-box quantum circuit achieves reductions of 2.3% in TDW and 45.2% in FDW. Additionally, we propose a new key schedule strategy to reduce the full depth of the AES quantum circuit. Finally, the trade-offs between T-gates depth and width and the parallel numbers of S-box and TDW are analyzed.
Quantum computers can model and solve several problems that have posed challenges for classical super computers, leveraging their natural quantum mechanical characteristics. A large-scale quantum computer is poised to significantly reduce security strength in cryptography. In this context, extensive research has been conducted on quantum cryptanalysis.In this paper, we present optimized quantum circuits for Korean block ciphers, HIGHT and LEA. Our quantum circuits for HIGHT and LEA demonstrate the lowest circuit depth compared to previous results. Specifically, we achieve depth reductions of 48% and 74% for HIGHT and LEA, respectively. We employ multiple novel techniques that effectively reduce the quantum circuit depth with a reasonable increase in qubit count. Based on our depth-optimized quantum circuits for HIGHT and LEA block ciphers, we estimate the lowest quantum attack complexity for Grover’s key search. Our quantum circuit can be utilized for other quantum algorithms, not only for Grover’s algorithm. Furthermore, the optimization methods gathered in this work can be adopted for generic quantum implementations in cryptography.
Grover search algorithm is the most representative quantum attack method that threatens the security of symmetric key cryptography. If the Grover search algorithm is applied to symmetric key cryptography, the security level of target symmetric key cryptography can be lowered from n-bit to n2-bit. When applying Grover’s search algorithm to the block cipher that is the target of potential quantum attacks, the target block cipher must be implemented as quantum circuits. Starting with the AES block cipher, a number of works have been conducted to optimize and implement target block ciphers into quantum circuits. Recently, many studies have been published to implement lightweight block ciphers as quantum circuits. In this paper, we present optimal quantum circuit designs of symmetric key cryptography, including PRESENT and GIFT block ciphers. The proposed method optimized PRESENT and GIFT block ciphers by minimizing qubits, quantum gates, and circuit depth. We compare proposed PRESENT and GIFT quantum circuits with other results of lightweight block cipher implementations in quantum circuits. Finally, quantum resources of PRESENT and GIFT block ciphers required for the oracle of the Grover search algorithm were estimated.