Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

EPJ Quantum Technology

Quantum reversible circuits for $\mathrm{GF}(2^{8})$ multiplicative inverse

Qing-bin Luo, Guowu Yang, Xiaoyu Li, Qiang Li

Published Oct 7, 2022• 10 citations
Publisher

Abstract

Abstract The synthesis of quantum circuits for multiplicative inverse over $\operatorname{GF}(2^{8})$ GF ( 2 8 ) are discussed in this paper. We first convert the multiplicative inverse operation in $\operatorname{GF}(2^{8})$ GF ( 2 8 ) to arithmetic operations in the composite field $\operatorname{GF}((2^{4})^{2})$ GF ( ( 2 4 ) 2 ) , and then discuss the expressions of the square calculation, the inversion calculation and the multiplication calculation separately in the finite field $\operatorname{GF}(2^{4})$ GF ( 2 4 ) , where the expressions of multiplication calculation in $\operatorname{GF}(2^{4})$ GF ( 2 4 ) are given directly in $\operatorname{GF}(2^{4})$ GF ( 2 4 ) and given through being transformed into the composite field $\operatorname{GF}((2^{2})^{2})$ GF ( ( 2 2 ) 2 ) . Then the quantum circuits of these calculations are realized one by one. Finally, two quantum circuits for multiplicative inverse over $\operatorname{GF}(2^{8})$ GF ( 2 8 ) are synthesized. They both use 21 qubits, the first quantum circuit uses 55 Toffoli gates and 107 CNOT gates and the second one uses 37 Toffoli gates and 209 CNOT gates. As an example of the application of multiplication inverse, we apply these quantum circuits to the implementations of the S-box quantum circuit of the AES cryptographic algorithm. Two quantum circuits for implementing the S-box of the AES cryptographic algorithm are presented. The first quantum circuit uses 21 qubits, 55 Toffoli gates, 131 CNOT gates and 4 NOT gates and the second one uses 21 qubits, 37 Toffoli gates, 233 CNOT gates and 4 NOT gates. Through the evaluation of quantum cost, the two quantum circuits of the S-box of AES cryptographic algorithm use less quantum resources than the existing schemes.

DOI
10.1140/epjqt/s40507-022-00144-z

Related papers

Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations

Noureldin Yosri, Dmytro Gavinsky, Dmitri Maslov

We present optimized quantum circuits for GF$(2^m)$ multiplication and division operations, which are essential computing primitives in various quantum algorithms. Our ancilla-free GF multiplication circuit has the gate count complexity of $O(m^{\log_2{3}})$, an improvement over the previous best bound of $O(m^2)$. This was achieved by developing an efficient $O(m)$ circuit for multiplication by the constant polynomial $1+x^{\lceil{m/2}\rceil}$, a key component of Van Hoof's construction. This asymptotic reduction translates to a factor of 100+ improvement of the CNOT gate counts in the implementation of the multiplication by the constant for parameters $m$ of practical importance. For the GF division, we reduce gate count complexity from $O(m^2 \log(m))$ to $O(m^2 \log \log(m)/\log(m))$ by selecting irreducible polynomials that enable efficient implementation of both the constant polynomial multiplication and field squaring operations. We demonstrate practical advantages for cryptographically relevant values of $m$, including reductions in both CNOT and Toffoli gate counts. Additionally, we explore the complexity of implementing square roots of linear reversible unitaries and demonstrate that a root, although itself still a linear reversible transformation, can require asymptotically deeper circuit implementations than the original unitary.

quant-pharXiv:2511.20618•Nov 26, 2025•0 citations

Analysis of converting $\mathfrak{C^{0}}$-circuit into $\mathfrak{C^{*}}$-circuit

Qing-bin Luo, Lang Ding, Guowu Yang +1 more

A $\mathfrak{C^{*}}$ -circuit, which was proposed in Asiacypt 2022 by Huang and Sun (Advances in cryptology – ASIACRYPT 2022, pp. 614–644, 2022), can directly perform calculations with the existing quantum states, thereby reducing the use of quantum resources in quantum logic synthesis. We theoretically prove how to convert a $\mathfrak{C^{0}}$ -circuit into the corresponding $\mathfrak{C^{*}}$ -circuit through two lemmas and one theorem. The first lemma proves the interchangeability of CNOT gates and NOT gates by using the equivalence of quantum circuits. The second lemma proves that adding CNOT gates to the front of a quantum circuit whose initial states are all $|0\rangle $ s will not change the output states of the circuit. The theorem is used to describe what kind of $\mathfrak{C^{0}}$ -circuit can be transformed into $\mathfrak{C^{*}}$ -circuit, and the correctness of this transformation is proved. Our work will provide a theoretical basis for converting $\mathfrak{C^{0}}$ -circuit to $\mathfrak{C^{*}}$ -circuit. Then applying the theoretical analysis results to the multiplication over $\text{GF}(2^{8})$ , the constructed quantum circuit needs 27 Toffoli gates and 118 CNOT gates, which is 15 fewer Toffoli gates and 43 CNOT gates than the current best result. This shows that the method of constructing quantum circuits by using the conversion of $\mathfrak{C^{0}}$ -circuit to $\mathfrak{C^{*}}$ -circuit is very efficient.

EPJ Quantum Technology•Jan 28, 2025•3 citations

Constructing quantum circuits for Grover key search in MK-3 featuring 16-bit S-boxes

Haoyu Liao, Qing-bin Luo, Yuanmeng Zheng +2 more

Abstract Quantum computing poses a significant threat to modern cryptosystems, prompting nations to initiate the development of next-generation cryptographic algorithms where quantum security assessment constitutes a critical task. In this work, we present the first complete quantum attack circuit construction and security evaluation of quantum resistance for the authenticated encryption algorithm MK-3, which features 16-bit S-boxes. Firstly, we achieve breakthroughs in finite field arithmetic. The arrangement method of Toffoli gates in the subfield $$F_{2^4}$$ F 2 4 enables two types of optimized $$F_{2^8}$$ F 2 8 multiplication circuits to reduce DW-cost by at least 50%. For $$F_{2^8}$$ F 2 8 inversion, by proposing a new intermediate state uncomputing technique, the DW-cost of the inversion circuit is reduced by at least 40% compared with existing solutions. This can also be used to optimize the quantum circuits of block ciphers such as AES and SM4. Secondly, we propose three types of quantum circuits for MK-3’s 16-bit S-box. The basic circuit reduces multiplicative bit operations to 115, representing at least 20% reduction. We propose a more compact S-box structure, reducing the number of circuit qubits for two types of S-boxes from 52 to 40. Finally, we implement full-algorithm quantum attacks and conduct security evaluations for MK-3. Complete quantum circuits supporting 128-bit and 256-bit keys are constructed, enabling Grover key search attacks. Security assessments confirm the 128-bit version meets NIST Security Category 1 (with reasonable inference of achieving Category 2), while the 256-bit version satisfies the highest Category 5 standards, demonstrating resistance against large-scale quantum computing attacks. This work achieves the first quantum circuit implementation for 16-bit S-boxes and provides critical evaluation benchmarks for post-quantum cryptography standardization.

Cybersecurity•Jun 17, 2026•0 citations

Quantum circuit for implementing Camellia S-box with low costs

ZhenQiang Li, Gao Fei, Qin Su-Juan +1 more

Camellia, after AES, is one of the most competitive block cipher algorithms. It has been widely used in many fields of information security. Camellia's distinctive nonlinear component is the S-box. This paper studies how to build the quantum circuit of the Camellia S-box at lower costs. First, the multiplicative inversion in F_2^8can be obtained by the multiplicative inversion (and multiplication) in F_2^4via a mapping matrix, and the latter can be implemented by the automation tool LIGHTER-R. The affine transformation of the S-box is then implemented with CNOT and NOT gates using the PLU decomposition and elimination approach. Finally, the Camellia S-box quantum circuit is built with 20 qubits, 54 Toffoli gates, 196 CNOT gates, 13 NOT gates, and a Toffoli depth of 42. In comparison with the previous study, which required 23 qubits, 67 Toffoli, and 38 CNOT gates, and a Toffoli depth of 53, the S-box quantum circuit in this paper requires fewer resources. Furthermore, the S-box quantum circuit used in the study can reduce the quantum resources in implementing Camellia, reducing the quantum circuit scale required to attack Camellia by the Grover algorithm.

Zhongguo kexue. Wulixue Lixue Tianwenxue•Mar 2, 2023•5 citations

New record in the number of qubits for a quantum implementation of AES

Zhenqiang Li, Fei Gao, Su‐Juan Qin +1 more

Optimizing the quantum circuit for implementing Advanced Encryption Standard (AES) is crucial for estimating the necessary resources in attacking AES by the Grover algorithm. Previous studies have reduced the number of qubits required for the quantum circuits of AES-128/-192/-256 from 984/1112/1336 to 270/334/398, which is close to the optimal value of 256/320/384. It becomes a challenging task to further optimize them. AimTaking aim at this task, we find a method for how the quantum circuit of AES S-box can be designed with the help of the automation tool LIGHTER-R. Particularly, the multiplicative inversion in F28 , which is the main part of the S-box, is converted into the multiplicative inversion (and multiplication) in F24 , then the latter can be implemented by LIGHTER-R because its search space is small enough. By this method, we construct the quantum circuits of S-box for mapping |a⟩|0⟩ to |a⟩|S(a)⟩ and |a⟩|b⟩ to |a⟩|b ⊕ S(a)⟩ with 20 qubits instead of 22 in the previous studies. In addition, we introduce new techniques to reduce the number of qubits required by the S-box circuit for mapping |a⟩ to |S(a)⟩ from 22 in the previous studies to 16. Accordingly, we synthesize the quantum circuits of AES-128/-192/-256 with 264/328/392 qubits, which implies a new record.

Frontiers in Physics•Mar 24, 2023•20 citations

Efficient quantum circuit research and implementation for 16-bit S-boxes based on composite field

Lei Zhang, Guoyuan Li, Jingchen Dai +4 more

With the development of quantum computing technology, efficiently implementing the core component S-box of block ciphers in quantum environments has become an important research direction in the field of cryptographic engineering. Due to the limitations of the no-cloning theorem of quantum states, the implementation of S-boxes in quantum circuits faces the dual challenges of exponential growth in space complexity and excessive consumption of quantum resources, especially in 16-bit and larger S-boxes. To address these problems, this paper proposes a construction framework for 16-bit S-box quantum circuits based on composite fields. This method relies on normal bases representation to construct composite field structures, decomposing high-dimensional multiplicative inverse into low-dimensional subdomain operations through isomorphic mapping, thereby significantly reducing the quantum cost of nonlinear component. In the linear component, a dynamic optimal pivot selection strategy is proposed to effectively optimize the Gaussian elimination process while maintaining the row echelon form of the matrix, thereby reducing the number of CNOT gates. Taking the 16-bit S-box in the MK-3 algorithm as an example, experimental results show that the proposed method maintains correct circuit structure while reducing CNOT gate consumption in the linear component by more than 32.8%, and the utilization of quantum resources in the nonlinear component is more advantageous. This study provides theoretical support and an implementation path for the high-performance implementation of block ciphers in practical quantum computing environments.

Journal of King Saud University - Computer and Information Sciences•Jun 1, 2025•2 citations
Quantum reversible circuits for GF(28)\mathrm{GF}(2^{8})GF(28) multiplicative inverse
Abstract The synthesis of quantum circuits for multiplicative inverse over GF⁡(28)\operatorname{GF}(2^{8})GF(28) GF ( 2 8 ) are discussed in this paper. We first convert the multiplicative inverse operation in GF⁡(28)\operatorname{GF}(2^{8})GF(28) GF ( 2 8 ) to arithmetic operations in the composite field GF⁡((24)2)\operatorname{GF}((2^{4})^{2})GF((24)2) GF ( ( 2 4 ) 2 ) , and then discuss the expressions of the square calculation, the inversion calculation and the multiplication calculation separately in the finite field GF⁡(24)\operatorname{GF}(2^{4})GF(24) GF ( 2 4 ) , where the expressions of multiplication calculation in GF⁡(24)\operatorname{GF}(2^{4})GF(24) GF ( 2 4 ) are given directly in GF⁡(24)\operatorname{GF}(2^{4})GF(24) GF ( 2 4 ) and given through being transformed into the composite field GF⁡((22)2)\operatorname{GF}((2^{2})^{2})GF((22)2) GF ( ( 2 2 ) 2 ) . Then the quantum circuits of these calculations are realized one by one. Finally, two quantum circuits for multiplicative inverse over GF⁡(28)\operatorname{GF}(2^{8})GF(28) GF ( 2 8 ) are synthesized. They both use 21 qubits, the first quantum circuit uses 55 Toffoli gates and 107 CNOT gates and the second one uses 37 Toffoli gates and 209 CNOT gates. As an example of the application of multiplication inverse, we apply these quantum circuits to the implementations of the S-box quantum circuit of the AES cryptographic algorithm. Two quantum circuits for implementing the S-box of the AES cryptographic algorithm are presented. The first quantum circuit uses 21 qubits, 55 Toffoli gates, 131 CNOT gates and 4 NOT gates and the second one uses 21 qubits, 37 Toffoli gates, 233 CNOT gates and 4 NOT gates. Through the evaluation of quantum cost, the two quantum circuits of the S-box of AES cryptographic algorithm use less quantum resources than the existing schemes.
Asymptotic yet practical optimization of quantum circuits implementing GF(2m2^m2m) multiplication and division operations
We present optimized quantum circuits for GF(2m)(2^m)(2m) multiplication and division operations, which are essential computing primitives in various quantum algorithms. Our ancilla-free GF multiplication circuit has the gate count complexity of O(mlog⁡23)O(m^{\log_2{3}})O(mlog2​3), an improvement over the previous best bound of O(m2)O(m^2)O(m2). This was achieved by developing an efficient O(m)O(m)O(m) circuit for multiplication by the constant polynomial 1+x⌈m/2⌉1+x^{\lceil{m/2}\rceil}1+x⌈m/2⌉, a key component of Van Hoof's construction. This asymptotic reduction translates to a factor of 100+ improvement of the CNOT gate counts in the implementation of the multiplication by the constant for parameters mmm of practical importance. For the GF division, we reduce gate count complexity from O(m2log⁡(m))O(m^2 \log(m))O(m2log(m)) to O(m2log⁡log⁡(m)/log⁡(m))O(m^2 \log \log(m)/\log(m))O(m2loglog(m)/log(m)) by selecting irreducible polynomials that enable efficient implementation of both the constant polynomial multiplication and field squaring operations. We demonstrate practical advantages for cryptographically relevant values of mmm, including reductions in both CNOT and Toffoli gate counts. Additionally, we explore the complexity of implementing square roots of linear reversible unitaries and demonstrate that a root, although itself still a linear reversible transformation, can require asymptotically deeper circuit implementations than the original unitary.
Analysis of converting C0\mathfrak{C^{0}}C0-circuit into C∗\mathfrak{C^{*}}C∗-circuit
A C∗\mathfrak{C^{*}}C∗ -circuit, which was proposed in Asiacypt 2022 by Huang and Sun (Advances in cryptology – ASIACRYPT 2022, pp. 614–644, 2022), can directly perform calculations with the existing quantum states, thereby reducing the use of quantum resources in quantum logic synthesis. We theoretically prove how to convert a C0\mathfrak{C^{0}}C0 -circuit into the corresponding C∗\mathfrak{C^{*}}C∗ -circuit through two lemmas and one theorem. The first lemma proves the interchangeability of CNOT gates and NOT gates by using the equivalence of quantum circuits. The second lemma proves that adding CNOT gates to the front of a quantum circuit whose initial states are all $|0\rangle $ s will not change the output states of the circuit. The theorem is used to describe what kind of C0\mathfrak{C^{0}}C0 -circuit can be transformed into C∗\mathfrak{C^{*}}C∗ -circuit, and the correctness of this transformation is proved. Our work will provide a theoretical basis for converting C0\mathfrak{C^{0}}C0 -circuit to C∗\mathfrak{C^{*}}C∗ -circuit. Then applying the theoretical analysis results to the multiplication over GF(28)\text{GF}(2^{8})GF(28) , the constructed quantum circuit needs 27 Toffoli gates and 118 CNOT gates, which is 15 fewer Toffoli gates and 43 CNOT gates than the current best result. This shows that the method of constructing quantum circuits by using the conversion of C0\mathfrak{C^{0}}C0 -circuit to C∗\mathfrak{C^{*}}C∗ -circuit is very efficient.
Abstract Quantum computing poses a significant threat to modern cryptosystems, prompting nations to initiate the development of next-generation cryptographic algorithms where quantum security assessment constitutes a critical task. In this work, we present the first complete quantum attack circuit construction and security evaluation of quantum resistance for the authenticated encryption algorithm MK-3, which features 16-bit S-boxes. Firstly, we achieve breakthroughs in finite field arithmetic. The arrangement method of Toffoli gates in the subfield F24F_{2^4}F24​ F 2 4 enables two types of optimized F28F_{2^8}F28​ F 2 8 multiplication circuits to reduce DW-cost by at least 50%. For F28F_{2^8}F28​ F 2 8 inversion, by proposing a new intermediate state uncomputing technique, the DW-cost of the inversion circuit is reduced by at least 40% compared with existing solutions. This can also be used to optimize the quantum circuits of block ciphers such as AES and SM4. Secondly, we propose three types of quantum circuits for MK-3’s 16-bit S-box. The basic circuit reduces multiplicative bit operations to 115, representing at least 20% reduction. We propose a more compact S-box structure, reducing the number of circuit qubits for two types of S-boxes from 52 to 40. Finally, we implement full-algorithm quantum attacks and conduct security evaluations for MK-3. Complete quantum circuits supporting 128-bit and 256-bit keys are constructed, enabling Grover key search attacks. Security assessments confirm the 128-bit version meets NIST Security Category 1 (with reasonable inference of achieving Category 2), while the 256-bit version satisfies the highest Category 5 standards, demonstrating resistance against large-scale quantum computing attacks. This work achieves the first quantum circuit implementation for 16-bit S-boxes and provides critical evaluation benchmarks for post-quantum cryptography standardization.
Camellia, after AES, is one of the most competitive block cipher algorithms. It has been widely used in many fields of information security. Camellia's distinctive nonlinear component is the S-box. This paper studies how to build the quantum circuit of the Camellia S-box at lower costs. First, the multiplicative inversion in F_2^8can be obtained by the multiplicative inversion (and multiplication) in F_2^4via a mapping matrix, and the latter can be implemented by the automation tool LIGHTER-R. The affine transformation of the S-box is then implemented with CNOT and NOT gates using the PLU decomposition and elimination approach. Finally, the Camellia S-box quantum circuit is built with 20 qubits, 54 Toffoli gates, 196 CNOT gates, 13 NOT gates, and a Toffoli depth of 42. In comparison with the previous study, which required 23 qubits, 67 Toffoli, and 38 CNOT gates, and a Toffoli depth of 53, the S-box quantum circuit in this paper requires fewer resources. Furthermore, the S-box quantum circuit used in the study can reduce the quantum resources in implementing Camellia, reducing the quantum circuit scale required to attack Camellia by the Grover algorithm.
Optimizing the quantum circuit for implementing Advanced Encryption Standard (AES) is crucial for estimating the necessary resources in attacking AES by the Grover algorithm. Previous studies have reduced the number of qubits required for the quantum circuits of AES-128/-192/-256 from 984/1112/1336 to 270/334/398, which is close to the optimal value of 256/320/384. It becomes a challenging task to further optimize them. AimTaking aim at this task, we find a method for how the quantum circuit of AES S-box can be designed with the help of the automation tool LIGHTER-R. Particularly, the multiplicative inversion in F28 , which is the main part of the S-box, is converted into the multiplicative inversion (and multiplication) in F24 , then the latter can be implemented by LIGHTER-R because its search space is small enough. By this method, we construct the quantum circuits of S-box for mapping |a⟩|0⟩ to |a⟩|S(a)⟩ and |a⟩|b⟩ to |a⟩|b ⊕ S(a)⟩ with 20 qubits instead of 22 in the previous studies. In addition, we introduce new techniques to reduce the number of qubits required by the S-box circuit for mapping |a⟩ to |S(a)⟩ from 22 in the previous studies to 16. Accordingly, we synthesize the quantum circuits of AES-128/-192/-256 with 264/328/392 qubits, which implies a new record.
With the development of quantum computing technology, efficiently implementing the core component S-box of block ciphers in quantum environments has become an important research direction in the field of cryptographic engineering. Due to the limitations of the no-cloning theorem of quantum states, the implementation of S-boxes in quantum circuits faces the dual challenges of exponential growth in space complexity and excessive consumption of quantum resources, especially in 16-bit and larger S-boxes. To address these problems, this paper proposes a construction framework for 16-bit S-box quantum circuits based on composite fields. This method relies on normal bases representation to construct composite field structures, decomposing high-dimensional multiplicative inverse into low-dimensional subdomain operations through isomorphic mapping, thereby significantly reducing the quantum cost of nonlinear component. In the linear component, a dynamic optimal pivot selection strategy is proposed to effectively optimize the Gaussian elimination process while maintaining the row echelon form of the matrix, thereby reducing the number of CNOT gates. Taking the 16-bit S-box in the MK-3 algorithm as an example, experimental results show that the proposed method maintains correct circuit structure while reducing CNOT gate consumption in the linear component by more than 32.8%, and the utilization of quantum resources in the nonlinear component is more advantageous. This study provides theoretical support and an implementation path for the high-performance implementation of block ciphers in practical quantum computing environments.