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• 11 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

Design of Quantum Circuits for Cryptanalysis and Image Processing Applications

Edgard Muñoz‐Coreas, Himanshu Thapliyal

Quantum circuits for arithmetic functions over Galois fields such as squaring are required to implement quantum cryptanalysis algorithms. Quantum circuits for integer arithmetic such as multiplication are required to implement scientific computing algorithms and quantum image processing algorithms on quantum computers. Reliable quantum circuits require error correcting codes and gates that are fault tolerant in nature. Quantum circuits of many qubits are challenging to implement making designs with low qubit cost desirable. In this work, we present quantum arithmetic circuits for applications in quantum cryptanalysis and quantum image processing. We present a proposed algorithm for synthesizing gate cost, qubit cost and depth optimized Galois field (GF(2m)) squaring circuits for quantum cryptanalysis applications. In addition, these squaring circuits are incorporated into a proposed quantum circuit for inversion in GF(2m). This work also presents a proposed quantum integer conditional addition circuit and a quantum integer multiplication circuit optimized for T-count and qubit cost. The quantum conditional addition circuit and quantum multiplier are incorporated into proposed quantum circuits for bilinear interpolation optimized for T-count cost that can be used in quantum image processing applications.

IEEE Computer Society Annual Symposium on VLSI•Jul 1, 2019•2 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•1 citation

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•7 citations

Design of Quantum Circuits for Galois Field Squaring and Exponentiation

Edgard Muñoz‐Coreas, Himanshu Thapliyal

This work presents an algorithm to generate depth, quantum gate and qubit optimized circuits for GF(2m) squaring in the polynomial basis. Further, to the best of our knowledge the proposed quantum squaring circuit algorithm is the only work that considers depth as a metric to be optimized. We compared circuits generated by our proposed algorithm against the state of the art and determine that they require 50% fewer qubits and offer gates savings that range from 37% to 68%. Further, existing quantum exponentiation are based on either modular or integer arithmetic. However, Galois arithmetic is a useful tool to design resource efficient quantum exponentiation circuit applicable in quantum cryptanalysis. Therefore, we present the quantum circuit implementation of Galois field exponentiation based on the proposed quantum Galois field squaring circuit. We calculated a qubit savings ranging between 44% to 50% and quantum gate savings ranging between 37% to 68% compared to identical quantum exponentiation circuit based on existing squaring circuits.

arXiv:1706.05114•IEEE Computer Society Annual Symposium on VLSI•Jul 1, 2017•7 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.
Quantum circuits for arithmetic functions over Galois fields such as squaring are required to implement quantum cryptanalysis algorithms. Quantum circuits for integer arithmetic such as multiplication are required to implement scientific computing algorithms and quantum image processing algorithms on quantum computers. Reliable quantum circuits require error correcting codes and gates that are fault tolerant in nature. Quantum circuits of many qubits are challenging to implement making designs with low qubit cost desirable. In this work, we present quantum arithmetic circuits for applications in quantum cryptanalysis and quantum image processing. We present a proposed algorithm for synthesizing gate cost, qubit cost and depth optimized Galois field (GF(2m)) squaring circuits for quantum cryptanalysis applications. In addition, these squaring circuits are incorporated into a proposed quantum circuit for inversion in GF(2m). This work also presents a proposed quantum integer conditional addition circuit and a quantum integer multiplication circuit optimized for T-count and qubit cost. The quantum conditional addition circuit and quantum multiplier are incorporated into proposed quantum circuits for bilinear interpolation optimized for T-count cost that can be used in quantum image processing applications.
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.
This work presents an algorithm to generate depth, quantum gate and qubit optimized circuits for GF(2m) squaring in the polynomial basis. Further, to the best of our knowledge the proposed quantum squaring circuit algorithm is the only work that considers depth as a metric to be optimized. We compared circuits generated by our proposed algorithm against the state of the art and determine that they require 50% fewer qubits and offer gates savings that range from 37% to 68%. Further, existing quantum exponentiation are based on either modular or integer arithmetic. However, Galois arithmetic is a useful tool to design resource efficient quantum exponentiation circuit applicable in quantum cryptanalysis. Therefore, we present the quantum circuit implementation of Galois field exponentiation based on the proposed quantum Galois field squaring circuit. We calculated a qubit savings ranging between 44% to 50% and quantum gate savings ranging between 37% to 68% compared to identical quantum exponentiation circuit based on existing squaring circuits.