Open Access
ARTICLE
A Novel Framework to Construct S-Box Quantum Circuits Using System Modeling: Application to 4-Bit S-Boxes
Department of Financial Information Security, Kookmin University, Seoul, 02707, Republic of Korea
* Corresponding Author: Jongsung Kim. Email:
(This article belongs to the Special Issue: Advanced Security for Future Mobile Internet: A Key Challenge for the Digital Transformation)
Computer Modeling in Engineering & Sciences 2024, 141(1), 545-561. https://doi.org/10.32604/cmes.2024.052374
Received 31 March 2024; Accepted 06 June 2024; Issue published 20 August 2024
Abstract
Quantum computers accelerate many algorithms based on the superposition principle of quantum mechanics. The Grover algorithm provides significant performance to malicious users attacking symmetric key systems. Since the performance of attacks using quantum computers depends on the efficiency of the quantum circuit of the encryption algorithms, research research on the implementation of quantum circuits is essential. This paper presents a new framework to construct quantum circuits of substitution boxes (S-boxes) using system modeling. We model the quantum circuits of S-boxes using two layers: Toffoli and linear layers. We generate vector spaces based on the values of qubits used in the linear layers and apply them to find quantum circuits. The framework finds the circuit by matching elements of vector spaces generated from the input and output of a given S-box, using the forward search or the meet-in-the-middle strategy. We developed a tool to apply this framework to 4-bit S-boxes. While the 4-bit S-box quantum circuit construction tool LIGHTER-R only finds circuits that can be implemented with four qubits, the proposed tool achieves the circuits with five qubits. The proposed tool can find quantum circuits of 4-bit odd permutations based on the controlled NOT, NOT, and Toffoli gates, whereas LIGHTER-R is unable to perform this task in the same environment. We expect this technique to become a critical step toward optimizing S-box quantum circuits.Keywords
Quantum computers accelerate many algorithms based on the superposition principle of quantum mechanics. Shor’s algorithm [1] exponentially reduces the complexity of attacking public-key schemes on quantum computers. Since 2016, the National Institute of Standards and Technology (NIST) has been conducting the post-quantum cryptography standardization process [2]. For symmetric-key schemes, Grover’s and Simon’s algorithms [3,4] offer attackers significant performance to attack the schemes, but these algorithms do not entirely compromise the security such systems’. However, in a quantum computing environment, symmetric-key cryptography may have weak properties not yet studied for each algorithm. Most cryptanalysis, including attacks targeting these vulnerabilities and generic attacks, requires the implementation of cipher’s quantum circuits, and its performance depends on the efficiency of the circuit. For future security, research on the implementation of the quantum circuits must be conducted, and it is necessary to know what performance bounds there are.
The substitution box (S-box) is a crucial component that provides confusion in symmetric-key schemes. When implementing a cipher as a quantum circuit, the linear layer can be implemented with only NOT and controlled-NOT (CNOT) gates. However, highly structured nonlinear layers, such as the S-box, must employ relatively expensive Toffoli gates and numerous qubits. In quantum circuits for symmetric-key schemes, the S-box incurs the highest cost.
The complexity of a quantum circuit is evaluated by the number of qubits and the Toffoli-depth defined by the number of non-parallelizable Toffoli gates. Optimizing these two parameters increases the implementation efficiency of quantum computers. This approach improves the attackers’ ability to perform exhaustive search and dedicated attacks using Grover’s algorithm in quantum computer. Hence, optimizing the quantum circuits of S-boxes is critical to assess the security of symmetric-key schemes against quantum computer-based attacks.
Extensive recent research has been conducted on finding efficient quantum circuits for the Advanced Encryption Standard (AES). Grassl et al. [5] initially proposed a quantum circuit for the AES and introduced a zig-zag structure to reduce the number of qubits required for its implementation. Subsequently, several studies have been conducted to reduce the number of qubits to implement the AES [6–9]. However, in NIST’s post-quantum cryptography standardization process, the Toffoli-depth represents a critical parameter. In response, Jaques et al. [8] attempted to construct an AES quantum circuit with a shallow Toffoli-depth. Recently, Huang et al. [10] proposed an AES quantum circuit with the shallowest depth.
The terms and notations used in this paper are explained as follows:
• CNOT, NOT, Toffoli gates: Gates used in quantum circuit
• CNT-circuit: Quantum circuit using only CNOT, NOT, and Toffoli gates
• CT-circuit: Quantum circuit using only CNOT and Toffoli gates
•
•
•
•
•
•
Contributions. This paper provides a new framework to construct quantum circuits
To verify the effectiveness of the framework, we propose a technique and tool for applying the framework to a 4-bit S-box. These components are currently used as essential elements in many Authenticated Encryption with Associated Data (AEAD) schemes and block ciphers [11–15]. In addition, LIGHTER-R [16] provides Toffoli-depth optimized quantum circuits of 4-bit S-boxes with a 4-qubit restriction. However, this approach fails if the target 4-bit S-boxes are odd permutations. This result occurs due to the theorem that odd permutations cannot be implemented with 4 qubits in CNT-circuits and requiress at least 5 qubits [17]. The algorithms offer a wider range of quantum circuits compared to LIGHTER-R in terms of the Toffoli-depth and number of qubits (up to 5). This improvement allows the algorithms to produce the quantum circuits of the 4-bit S-boxes of odd permutations. Given that half of 4-bit S-boxes are odd permutations, this result enables researchers to implement quantum circuits for all 4-bit S-boxes.
Paper Organization. Section 2 describes quantum computation and quantum circuits. Section 3 describes the properties of the CNT-circuit and the model in the quantum circuit. Section 4 describes the framework for finding quantum circuits of 4-bit S-boxes according to a limited number of qubits. Section 5 presents the results of the proposed algorithm in Section 4. Section 6 presents the conclusions and provides a discussion.
2 Quantum Computation and Quantum Circuits
A fundamental concept in classical computing involves a bit, characterized as either 0 or 1. Conversely, the qubit plays a role as a bit in quantum computing, holding 0 and 1 at the same time according to the superposition principle of quantum mechanics. The values
This work primarily concerns with quantum circuits consisting of CNOT, NOT, and Toffoli gates. A CNOT gate is the two-qubit gate defined by
Figure 1: CNOT (left), NOT (middle), and Toffoli (right) gates
A quantum circuit using only CNOT, NOT, and Toffoli gates is defined as a CNT-circuit. In the CNT-circuit, the NOT gates can be moved to the circuit’s last operation without changing the Toffoli-depth, using the properties in Fig. 2. The NOT gates gathered in the last operation are equivalent to using an XORing on a constant value in the S-box. All S-boxes can be implemented with CNT-circuits; thus CT-circuits (without NOT gates) can implement all S-boxes satisfying
Figure 2: Properties of NOT gates
3 Modeling the Quantum Circuits of S-Boxes
We considered the
We modeled CT-circuits for
To facilitate finding the circuit, we arranged the Toffoli gates in order within the Toffoli layers. We assumed that the control and target qubit positions of the Toffoli gates are fixed, and the exchange of wires that occurs while fixing them is absorbed by the linear layers. In detail, the control qubits of the
Figure 3: Toffoli layer in the proposed model
Implementing linear layers is equivalent to knowing their input and output values. When Toffoli layers are implemented, the input value of the following linear layer can be determined through the output values of the previous linear layer. If the output values of
The qubit values at each point represent the input and output of the linear layer. We treated the qubit values as Boolean functions, and considered the vector space spanned by them. The vector spaces spanned at the input and output points of the linear layer are identical. We defined the vector space generated by
4 Exploring 4-Bit S-Box Quantum Circuits with the Meet-in-the-Middle Strategy: Up to 5 Qubits
4.1 Properties between Neighboring Vector Spaces
Let
Of the three qubits included in one Toffoli gate, only the target qubit changes in value. There are invariant qubit values; hence the intersection of two consecutive spaces,
Figure 4: Depiction of Theorem 1
Theorem 1. Define the CT-circuit of S-box S as
Proof. There are
According to the above theorem, the lower bound of the Toffoli-depth is found for the quantum circuit
Theorem 2. For
Proof. This situation is a special case where
■
We consider both forward and backward directions. The proposed algorithms confirm how many values of the newly constructed vector space belong to the opposite vector space. For example, we consider that
4.2 Exploring 4-Bit S-Box Quantum Circuits in the Forward Direction
We describe the process of implementing the 4-bit S-box
Definition 1. The pair of vector spaces in the forward and backward directions are denoted as
•
•
We defined the vector space corresponding to the
Algorithm 1 finds the vector space pairs only in the forward direction. If we generate a set
We consider quantum circuits with
There can be several combinations of
1. When
2. When
3. When
Let
4.3 Exploring 4-Bit S-Box Quantum Circuits Using Meet-in-the-Middle Strategy
We describe Algorithm 2 based on the meet-in-the-middle strategy in the same environment as the previous section. When constructing a circuit, if Algorithm 1 outputs an empty set, we proceed with Algorithm 2, which generates
For each
Figure 5: Description of the meet-in-the-middle strategy
The process of constructing
Searching two linear layers is possible only using the forward search, not the meet-in-the-middle strategy. However, the forward search requires a complexity of
5 Results for Some 4-bit S-Boxes
We applied the proposed algorithms to various 4-bit S-boxes. First, we considered all 4-bit optimal S-boxes classified by Leander and Poschmann [19,20] to demonstrate the validity of the proposed algorithms (see Table 1). Moreover, LIGHTER-R could not find the circuits of odd permutations (i.e.,
Second, we consider the 4-bit S-boxes of GIFT [15], SKINNY [14] and Saturnin [21] (see Table 2). The proposed algorithms and LIGHTER-R output identical Toffoli-depths in the circuit implementation when using 4 qubits. We executed the proposed algorithm using 5 qubits but outputted the same Toffoli-depths. To compare the results of this study with those of existing circuits, we checked the AND-depth, which relates closely to the Toffoli-depth. Quantum circuits with the Toffoli-depth at the same value as the AND-depth always exist, so comparison is possible [10]. These values represented the same AND-depths of the classical implementation, as claimed by the designers of GIFT and SKINNY. The GIFT quantum circuit with 4 qubits was written in Algorithm 3. In the algorithm,
In the case of Saturnin, we found a more efficient circuit with an AND-depth of 5, rather than a circuit with an AND-depth of 6 that the designers found. Fig. 6 is the circuit of Saturnin’s S-box
Figure 6: Circuit of Saturnin S-box
Discussion of the Results Based on the Algorithms. For each
Discussion on 6 Qubits. In this case, the method of this paper can be applied as is, and only the number of available Toffoli gates in a Toffoli layer increases. The proposed algorithm uses only one Toffoli gate in a Toffoli layer, so the algorithm selects three qubits. When using 6 qubits, two Toffoli gates must be found; therefore all 6 qubits are selected. Accordingly, the computational cost for the forward direction becomes
Discussion on Other Methods. There are tools for creating quantum circuits, including LIGHTER-R and DORCIS [22]. The LIGHTER-R tool is based on the breadth-frist search algorithm and evaluates paths based on the cost entered by the user. In addition, DORCIS is based on LIGHTER-R, but the difference is that it evaluates the path based on the depth of the circuit. In the proposed framework, the vector space pairs corresponding to the forward and backward linear layers become the nodes, and the patterns for selecting the vector space pairs become the paths. In addition, the proposed method evaluates the path based on the intersection of a vector space pair. In the breadth-frist search based algorithm, all CNOT gates become nodes, but this proposed method ignores the CNOT gates, so the search is reduced.
The authors of DORCIS used GIFT’s S-box to compare its performance with LIGHTER-R. Both algorithms achieved Toffoli-depth 4 using 4 qubits, and we obtained the same result using the same number of qubits. This implies that our tool can handle all the tasks that existing tools are capable of.
This paper presents a new framework to construct quantum circuits of S-boxes according to a limited number of qubits. To construct such circuits, we analyzed the dimension and basis before and after the Toffoli layer to find qubits for which the equations match based on the forward search or the meet-in-the-middle strategy. We employed the proposed tool to find the circuits of 4-bit S-boxes and verified its effectiveness in practice. Through the proposed framework, we discovered all quantum circuits of odd permutations among all 4-bit optimal S-boxes classified by Leander and Poschmann. We also implemented quantum circuits of S-boxes for several well-known block ciphers, in which a more efficient quantum circuit of Saturnin’s S-box was found. The proposed technique can be applied to find circuits for S-boxes larger than 4 bits, which is left for future work. This technique contributes to the research field regarding finding optimized quantum circuits of S-boxes.
Acknowledgement: None.
Funding Statement: This research was supported by the MSIT (Ministry of Science and ICT), Republic of Korea, under the ITRC (Information Technology Research Center) support program (IITP-2024-RS-2022-00164800) supervised by the IITP (Institute for Information & Communications Technology Planning & Evaluation).
Author Contributions: All authors contributed to the entire process from theoretical design to paper writing. All authors reviewed the results and approved the final version of the manuscript.
Availability of Data and Materials: The results of the proposed framework for optimal 4-bit S-boxes have been added to the appendix.
Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.
References
1. Shor, P. W. Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of 35th Annual Symposium on Foundations of Computer Science; 20–22 Nov 1994; IEEE Computer Society. [Google Scholar]
2. NIST. Post-quantum cryptography standardization; 2016. Available from: https://csrc.nist.gov/projects/post-quantum-cryptography. [Accessed 2024]. [Google Scholar]
3. Grover LK. A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing; 1996; New York, NY, USA: Association for Computing Machinery. p. 212–9. [Google Scholar]
4. Simon DR. On the power of quantum computation. SIAM J Comput. 1997;26(5):1474–83. doi:10.1137/S0097539796298637. [Google Scholar] [CrossRef]
5. Grassl M, Langenberg B, Roetteler M, Steinwandt R. Applying grover’s algorithm to AES: quantum resource estimates. In: Takagi T, editor. Post-Quantum Cryptography—7th International Workshop. Cham: Springer; 2016. [Google Scholar]
6. Langenberg B, Pham H, Steinwandt R. Reducing the cost of implementing the advanced encryption standard as a quantum circuit. IEEE Trans Quantum Eng. 2020;1:1–12. doi:10.1109/TQE.2020.2965697. [Google Scholar] [CrossRef]
7. Zou J, Wei Z, Sun S, Liu X, Wu W. Quantum circuit implementations of AES with fewer qubits. In: Moriai S, Wang H, editors. Advances in Cryptology—ASIACRYPT 2020—26th International Conference on the Theory and Application of Cryptology and Information Security; 2020; Daejeon, Republic of Korea: Springer. [Google Scholar]
8. Jaques S, Naehrig M, Roetteler M, Virdia F. Implementing grover oracles for quantum key search on AES and lowmc. In: Canteaut A, Ishai Y, editors. Advances in Cryptology-EUROCRYPT 2020—39th Annual International Conference on the Theory and Applications of Cryptographic Techniques; 2020; Zagreb, Croatia: Springer. [Google Scholar]
9. Lin D, Xiang Z, Xu R, Zhang S, Zeng X. Optimized quantum implementation of AES. Quant Inf Process. 2023;22(9):352. doi:10.1007/s11128-023-04043-9. [Google Scholar] [CrossRef]
10. Huang Z, Sun S. Synthesizing quantum circuits of AES with lower t-depth and less qubits. In: Agrawal S, Lin D, editors. Advances in Cryptology—ASIACRYPT 2022—28th International Conference on the Theory and Application of Cryptology and Information Security; 2022; Taipei, Taiwan: Springer. doi: 10.1007/978-3-031-22969-5. [Google Scholar] [CrossRef]
11. Bogdanov A, Knudsen LR, Leander G, Paar C, Poschmann A, Robshaw MJB, et al. PRESENT: an ultra-lightweight block cipher. In: Paillier P, Verbauwhede I, editors. Cryptographic Hardware and Embedded Systems—CHES 2007, 9th International Workshop; 2007; Vienna, Austria: Springer. [Google Scholar]
12. Albrecht MR, Driessen B, Kavun EB, Leander G, Paar C, Yalçin T. Block ciphers—focus on the linear layer (feat. PRIDE). In: Garay JA, Gennaro R, editors. Advances in Cryptology—CRYPTO 2014—34th Annual Cryptology Conference; 2014; Santa Barbara, CA, USA: Springer. [Google Scholar]
13. Zhang WT, Bao ZZ, Lin DD, Rijmen V, Yang BH, Verbauwhede I. RECTANGLE: a bit-slice lightweight block cipher suitable for multiple platforms. Sci China Inf Sci. 2015;58(12):1–15. doi:10.1007/s11432-015-5459-7. [Google Scholar] [CrossRef]
14. Beierle C, Jean J, Kölbl S, Leander G, Moradi A, Peyrin T, et al. The SKINNY family of block ciphers and its low-latency variant MANTIS. In: Robshaw M, Katz J, editors. Advances in Cryptology—CRYPTO 2016—36th Annual International Cryptology Conference; 2016; Santa Barbara, CA, USA: Springer. [Google Scholar]
15. Banik S, Pandey SK, Peyrin T, Sasaki Y, Sim SM, Todo Y. GIFT: a small present - towards reaching the limit of lightweight encryption. In: Fischer W, Homma N, editors. Cryptographic Hardware and Embedded Systems—CHES 2017—19th International Conference; 2017; Taipei, Taiwan: Springer. [Google Scholar]
16. Dasu VA, Baksi A, Sarkar S, Chattopadhyay A. LIGHTER-R: optimized reversible circuit implementation for sboxes. In: 32nd IEEE International System-on-Chip Conference; 2019; Singapore: IEEE. [Google Scholar]
17. Shende VV, Prasad AK, Markov IL, Hayes JP. Synthesis of reversible logic circuits. IEEE Trans Comput Aided Des Integr Circuits Syst. 2003;22(6):710–22. [Google Scholar]
18. Jiang J, Sun X, Teng S, Wu B, Wu K, Zhang J. Optimal space-depth trade-off of CNOT circuits in quantum logic synthesis. In: Chawla S, editor. Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020; 2020; Salt Lake City, UT, USA: SIAM. [Google Scholar]
19. Leander G, Poschmann A. On the classification of 4 bit s-boxes. In: Carlet C, Sunar B, editors. Arithmetic of Finite Fields, First International Workshop, WAIFI 2007; 2007; Madrid, Spain: Springer. [Google Scholar]
20. Zhang W, Bao Z, Rijmen V, Liu M. A new classification of 4-bit optimal s-boxes and its application to present, rectangle and spongent. In: Fast Software Encryption: 22nd International Workshop, FSE 2015; 2015; Istanbul, Turkey: Springer. [Google Scholar]
21. Canteaut A, Duval S, Leurent G, Naya-Plasencia M, Perrin L, et al. Saturnin: a suite of lightweight symmetric algorithms for post-quantum security. IACR Trans Symmetric Cryptol. 2020;2020(S1):160–207. [Google Scholar]
22. Chun M, Baksi A, Chattopadhyay A. DORCIS: depth optimized quantum implementation of substitution boxes. Available from: https://eprint.iacr.org/2023/286. [Accessed 2023]. [Google Scholar]
Appendix A: Results for the 4-Bit Optimal S-Boxes
Algorithms 4–11 are the results of the proposed framework for the optimal S-boxes
All lines except the Toffoli layers refer to linear layers.
Cite This Article
![cc](https://www.techscience.com/static/images/cc.jpg?t=20230215)
This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.