© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

IEEE International System-on-Chip Conference (SOCC)

Quantum Implementation of Linear and Non-Linear Layers

Anubhab Baksi, Sumanta Chakraborty, Anupam Chattopadhyay, Matthew Chun, SK Hafizul Islam, Kyungbae Jang, Hyunji Kim, Yujin Oh, Soham Roy, Hwajeong Seo, Siyi Wang

Published Sep 16, 2024• 8 citations

Abstract

In this paper, we consider the problem of quantum implementation of the symmetric-key ciphers. The typical ciphers in this category have two main components, the linear and the non-linear layers, we consider both. The linear layer can be described as a non-singular matrix over binary operations. The in-place implementation is one of the main considerations for implementing such layer to minimize the number of qubits. We discuss the research works that have been done to this point on this subject matter and report the improved implementation of some of the matrices. Lists of our modifications include; making it more efficient (specially for the larger matrices), consideration for quantum depth (along with a randomized algorithm for optimization), etc. We report benchmarks for the ASCON and SHA-2 linear matrices. As for the non-linear layer, the constituent block is called an substitution box (an S-box, for short). Our “DORCIS” tool presented in this paper, finds a quantum circuit with an optimized depth for given S-boxes of size 3- and 4-bit. It is a follow-up work on LIGHTER-R (which is applicable for 4-bit S-boxes only) with multiple extensions. Unlike LIGHTER-R, our DORCIS takes a quantum decomposition based on Clifford and T gates. Also, both the full quantum depth and the T depth can be optimized by DORCIS. We compare our implementation with other optimized quantum circuits shown in the other research works and show that we find an implementation with the same cost metric, or find an implementation with lower cost metric, compared other tools proposed in the literature, apart from being simpler and more efficient.

DOI: 10.1109/socc62300.2024.10737862

Related papers

Quantum Implementation of S-Boxes: A Memory Optimized Approach

Özcan Tilki, Ayşe Nurdan Saran, Hasan Özgür Çıldıroğlu +1 more

Substitution boxes (S-boxes) serve as fundamental non-linear components in symmetric cryptography, and their quantum circuit implementation is critical for quantum security. This work addresses the dual challenges of quantum circuit depth optimization and computational intractability in S-box synthesis. We introduce memory-optimized data structures, a pointer-efficient RandomAccessSet and a dynamic devector, that reduce memory overhead by 12 times per element, thereby mitigating the computational complexity associated with Pauli representation. Our enhanced Meet-in-the-Middle framework achieves exhaustive depth optimization for standardized S-boxes, demonstrating up to 8.5% depth reduction over DORCIS baselines at equivalent T-depth. The approach scales to 5-8-bit primitives, establishing memory efficiency as an independent resource dimension in quantum circuit synthesis. Comparative analysis under varied cost parameters provides new insights for resource-efficient cryptographic implementations on quantum hardware.

•Oct 22, 2025•1 citation

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 Implementation of S‐Boxes Based on Polynomial Evaluation

Doyoung Chung, Seungkwang Lee

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.

Electronics Letters•Jan 1, 2025•2 citations

A Framework to Improve the Implementations of Linear Layers

Yufei Yuan, Wenling Wu, Tairong Shi +2 more

This paper presents a novel approach to optimizing the linear layer of block ciphers using the matrix decomposition framework. It is observed that the reduction properties proposed by Xiang et al. (in FSE 2020) need to be improved. To address these limitations, we propose a new reduction framework with a complete reduction algorithm and swapping algorithm. Our approach formulates matrix decomposition as a new framework with an adaptive objective function and converts the problem to a Graph Isomorphism problem (GI problem). Using the new reduction algorithm, we were able to achieve lower XOR counts and depths of quantum implementations under the s-XOR metric. Our results outperform previous works for many linear layers of block ciphers and hash functions; some of them are better than the current g-XOR implementation. For the AES MixColumn operation, we get two implementations with 91 XOR counts and depth 13 of in-place quantum implementation, respectively.

IACR Transactions on Symmetric Cryptology•Jun 18, 2024•10 citations

Alternative Tower Field Construction for Quantum Implementation of the AES S-Box

Doyoung Chung, Seungkwang Lee, Dooho Choi +1 more

Grover’s search algorithm allows a quantum adversary to find a$k$-bit secret key of a block cipher by making O($2^{k/2}$) block cipher queries. Resistance of a block cipher to such an attack is evaluated by quantum resources required to implement Grover’s oracle for the target cipher. The quantum resources are typically estimated by the$\textit {T}$-depth of its circuit implementation and the number of qubits used by the circuit (width). Since the AES S-box is the only component which requires$\textit {T}$-gates in a quantum implementation of AES, recent research has put its focus on efficient implementation of the AES S-box. However, any efficient implementation with low$\textit {T}$-depth will not be practical in the real world without considering qubit consumption of the implementation. In this work, we propose three methods of trade-off between time and space for the quantum implementation of the AES S-box. In particular, one of our methods turns out to use the smallest number of qubits among the existing methods, significantly reducing its$\textit {T}$-depth.

IEEE Transactions on Computers•Dec 15, 2021•22 citations

A Novel Framework to Construct Quantum Circuits of S-Boxes: Applications to 4-bit S-boxes

Yongjin Jeon, Seungjun Baek, Jongsung Kim

Abstract In this paper, we present a new framework to construct a quantum circuit of S-boxes.We first model the quantum circuits of S-boxes based on the Toffoli and linear layers. We generate vector spaces with the values of qubits used in the linear layers and apply them to find quantum circuits.Our technique find the quantum circuit by matching the vector space's elements to the S-box's input and output, based on the meet-in-the-middle strategy.We applied our technique to 4-bit S-boxes.While existing LIGHTER-R tools only find 4-bit S-boxes circuits that can be implemented with 4 qubits, our tool accomplishes the same with 5 qubits.Our tool also finds reversible quantum circuits of 4-bit S-boxes, which are odd permutations that LIGHTER-R cannot.We expect our technique will become an important step towards finding optimized S-box quantum circuits.

•Mar 27, 2023•3 citations

In this paper, we consider the problem of quantum implementation of the symmetric-key ciphers. The typical ciphers in this category have two main components, the linear and the non-linear layers, we consider both. The linear layer can be described as a non-singular matrix over binary operations. The in-place implementation is one of the main considerations for implementing such layer to minimize the number of qubits. We discuss the research works that have been done to this point on this subject matter and report the improved implementation of some of the matrices. Lists of our modifications include; making it more efficient (specially for the larger matrices), consideration for quantum depth (along with a randomized algorithm for optimization), etc. We report benchmarks for the ASCON and SHA-2 linear matrices. As for the non-linear layer, the constituent block is called an substitution box (an S-box, for short). Our “DORCIS” tool presented in this paper, finds a quantum circuit with an optimized depth for given S-boxes of size 3- and 4-bit. It is a follow-up work on LIGHTER-R (which is applicable for 4-bit S-boxes only) with multiple extensions. Unlike LIGHTER-R, our DORCIS takes a quantum decomposition based on Clifford and T gates. Also, both the full quantum depth and the T depth can be optimized by DORCIS. We compare our implementation with other optimized quantum circuits shown in the other research works and show that we find an implementation with the same cost metric, or find an implementation with lower cost metric, compared other tools proposed in the literature, apart from being simpler and more efficient.

Substitution boxes (S-boxes) serve as fundamental non-linear components in symmetric cryptography, and their quantum circuit implementation is critical for quantum security. This work addresses the dual challenges of quantum circuit depth optimization and computational intractability in S-box synthesis. We introduce memory-optimized data structures, a pointer-efficient RandomAccessSet and a dynamic devector, that reduce memory overhead by 12 times per element, thereby mitigating the computational complexity associated with Pauli representation. Our enhanced Meet-in-the-Middle framework achieves exhaustive depth optimization for standardized S-boxes, demonstrating up to 8.5% depth reduction over DORCIS baselines at equivalent T-depth. The approach scales to 5-8-bit primitives, establishing memory efficiency as an independent resource dimension in quantum circuit synthesis. Comparative analysis under varied cost parameters provides new insights for resource-efficient cryptographic implementations on quantum hardware.

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.

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.

This paper presents a novel approach to optimizing the linear layer of block ciphers using the matrix decomposition framework. It is observed that the reduction properties proposed by Xiang et al. (in FSE 2020) need to be improved. To address these limitations, we propose a new reduction framework with a complete reduction algorithm and swapping algorithm. Our approach formulates matrix decomposition as a new framework with an adaptive objective function and converts the problem to a Graph Isomorphism problem (GI problem). Using the new reduction algorithm, we were able to achieve lower XOR counts and depths of quantum implementations under the s-XOR metric. Our results outperform previous works for many linear layers of block ciphers and hash functions; some of them are better than the current g-XOR implementation. For the AES MixColumn operation, we get two implementations with 91 XOR counts and depth 13 of in-place quantum implementation, respectively.

Grover’s search algorithm allows a quantum adversary to find a

k

-bit secret key of a block cipher by making O(

2^{k/2}

) block cipher queries. Resistance of a block cipher to such an attack is evaluated by quantum resources required to implement Grover’s oracle for the target cipher. The quantum resources are typically estimated by the

\textit {T}

-depth of its circuit implementation and the number of qubits used by the circuit (width). Since the AES S-box is the only component which requires

\textit {T}

-gates in a quantum implementation of AES, recent research has put its focus on efficient implementation of the AES S-box. However, any efficient implementation with low

\textit {T}

-depth will not be practical in the real world without considering qubit consumption of the implementation. In this work, we propose three methods of trade-off between time and space for the quantum implementation of the AES S-box. In particular, one of our methods turns out to use the smallest number of qubits among the existing methods, significantly reducing its

\textit {T}

-depth.

Abstract In this paper, we present a new framework to construct a quantum circuit of S-boxes.We first model the quantum circuits of S-boxes based on the Toffoli and linear layers. We generate vector spaces with the values of qubits used in the linear layers and apply them to find quantum circuits.Our technique find the quantum circuit by matching the vector space's elements to the S-box's input and output, based on the meet-in-the-middle strategy.We applied our technique to 4-bit S-boxes.While existing LIGHTER-R tools only find 4-bit S-boxes circuits that can be implemented with 4 qubits, our tool accomplishes the same with 5 qubits.Our tool also finds reversible quantum circuits of 4-bit S-boxes, which are odd permutations that LIGHTER-R cannot.We expect our technique will become an important step towards finding optimized S-box quantum circuits.