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

Journal of Science and Technology on Information security

A comprehensive view on quantum circuit construction for S-boxes without ancilla qubits

Nguyễn Văn Long, Hoang Dinh Linh, Le Quoc Dat

Published Jun 28, 2024• 0 citations
Publisher

Abstract

Abstract— This article presents a comprehensive analysis of Denisenko's method for constructing quantum circuits for S-boxes without using ancilla qubits. We elaborate on this methodology in terms of practical aspects that can be applied to S-boxes or permutations of arbitrary sizes. In addition, we created an automatic tool in C++ language that allows to construction of quantum circuits for any S-box without ancilla qubits. Furthermore, a quantum circuit for an 8-bit S-box of the MKV block cipher standard in the civilian sector of Vietnam is also provided using this tool.

DOI
10.54654/isj.v1i21.1031

Related papers

Quantum Circuits for S-Box Implementation without Ancilla Qubits

Д. Денисенко

Abstract A method is presented for implementing substitutions (S-boxes) in the form of quantum circuits without ancilla qubits. Quantum circuits are presented that implement substitutions in the GOST R 34.12-2015 block cipher “Magma” on four logical qubits, and the descriptions of quantum circuits implementing AES and GOST R 34.12-2015 “Kuznechik” S-boxes on 8 logical qubits—quantum circuits with minimum number of logical qubits—are given.

Journal of Experimental and Theoretical Physics•Jun 1, 2019•8 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

New SAT-based Model for Quantum Circuit Decision Problem: Searching for Low-Cost Quantum Implementation

Jingwen Chen, Qun Liu, Yanhong Fan +3 more

In recent years, quantum technology has been rapidly developed. As security analyses for symmetric ciphers continue to emerge, many require an evaluation of the resources needed for the quantum circuit implementation of the encryption algorithm. In this regard, we propose the quantum circuit decision problem, which requires us to determine whether there exists a quantum circuit for a given permutation f using M ancilla qubits and no more than K quantum gates within the circuit depth D. Firstly, we investigate heuristic algorithms and classical SAT-based models in previous works, revealing their limitations in solving the problem. Hence, we innovatively propose an improved SAT-based model incorporating three metrics of quantum circuits. The model enables us to find the optimal quantum circuit of an arbitrary 3 or 4-bit S-box under a given optimization goal based on SAT solvers, which has proved the optimality of circuits constructed by the tool, LIGHTER-R. Then, by combining different criteria in the model, we find more compact quantum circuit implementations of S-boxes such as RECTANGLE and GIFT. For GIFT S-box, our model provides the optimal quantum circuit that only requires 8 gates with a depth of 31. Furthermore, our model can be generalized to linear layers and improve the previous SAT-based model proposed by Huang et al. in ASIACRYPT 2022 by adding the criteria on the number of qubits and the circuit depth.

IACR Communications in Cryptology•Apr 9, 2024•9 citations

Quantum circuits for permutation matrices

Jason Hanson

Two different algorithms are presented for generating a quantum circuit realization of a matrix representing a permutation on $2^n$ letters. All circuits involve $n$ qubits and only use multi--controlled Toffoli gates. The first algorithm constructs a circuit from any decomposition of the permutation into a product of transpositions, but uses one ancilla line. The second, which uses no ancillae, constructs a circuit from a decomposition into a product of transpositions that have a Hamming distance of one. We show that any permutation admits such a decomposition, and we give a strategy for reducing the number of transpositions involved.

quant-pharXiv:2512.11938•Dec 15, 2025•0 citations

Efficient quantum circuit implementation of the SM4 S-box

LIU JiaHong, Xiaoqing Tan, LI Ming +1 more

In recent years, the quantum circuit implementation in symmetric cryptography has attracted widespread attention. The SM4 block cipher algorithm is China's first commercial cipher standard and was accepted as an ISO/IEC international standard in 2021. S-box is the most complex component in the SM4 block cipher algorithm. This study investigates the quantum circuit implementation of the SM4 S-box. Based on the algebraic structure, using tower filed decomposition technology, the quantum circuit of the SM4 S-box is built. Based on the number of NCT gate sets, our quantum circuit requires 20 qubits, 52 Toffoli gates, 196 CNOT gates, and 13 X gates. The Toffoli depth of our circuit is 36. Compared with previous literature, the quantum circuit proposed herein requires fewer quantum resources.

Zhongguo kexue. Wulixue Lixue Tianwenxue•Dec 8, 2023•4 citations

Quantum Implementation of Linear and Non-Linear Layers

Anubhab Baksi, Sumanta Chakraborty, Anupam Chattopadhyay +8 more

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.

IEEE International System-on-Chip Conference (SOCC)•Sep 16, 2024•8 citations
Abstract— This article presents a comprehensive analysis of Denisenko's method for constructing quantum circuits for S-boxes without using ancilla qubits. We elaborate on this methodology in terms of practical aspects that can be applied to S-boxes or permutations of arbitrary sizes. In addition, we created an automatic tool in C++ language that allows to construction of quantum circuits for any S-box without ancilla qubits. Furthermore, a quantum circuit for an 8-bit S-box of the MKV block cipher standard in the civilian sector of Vietnam is also provided using this tool.
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.
In recent years, quantum technology has been rapidly developed. As security analyses for symmetric ciphers continue to emerge, many require an evaluation of the resources needed for the quantum circuit implementation of the encryption algorithm. In this regard, we propose the quantum circuit decision problem, which requires us to determine whether there exists a quantum circuit for a given permutation f using M ancilla qubits and no more than K quantum gates within the circuit depth D. Firstly, we investigate heuristic algorithms and classical SAT-based models in previous works, revealing their limitations in solving the problem. Hence, we innovatively propose an improved SAT-based model incorporating three metrics of quantum circuits. The model enables us to find the optimal quantum circuit of an arbitrary 3 or 4-bit S-box under a given optimization goal based on SAT solvers, which has proved the optimality of circuits constructed by the tool, LIGHTER-R. Then, by combining different criteria in the model, we find more compact quantum circuit implementations of S-boxes such as RECTANGLE and GIFT. For GIFT S-box, our model provides the optimal quantum circuit that only requires 8 gates with a depth of 31. Furthermore, our model can be generalized to linear layers and improve the previous SAT-based model proposed by Huang et al. in ASIACRYPT 2022 by adding the criteria on the number of qubits and the circuit depth.
Two different algorithms are presented for generating a quantum circuit realization of a matrix representing a permutation on 2n2^n2n letters. All circuits involve nnn qubits and only use multi--controlled Toffoli gates. The first algorithm constructs a circuit from any decomposition of the permutation into a product of transpositions, but uses one ancilla line. The second, which uses no ancillae, constructs a circuit from a decomposition into a product of transpositions that have a Hamming distance of one. We show that any permutation admits such a decomposition, and we give a strategy for reducing the number of transpositions involved.
In recent years, the quantum circuit implementation in symmetric cryptography has attracted widespread attention. The SM4 block cipher algorithm is China's first commercial cipher standard and was accepted as an ISO/IEC international standard in 2021. S-box is the most complex component in the SM4 block cipher algorithm. This study investigates the quantum circuit implementation of the SM4 S-box. Based on the algebraic structure, using tower filed decomposition technology, the quantum circuit of the SM4 S-box is built. Based on the number of NCT gate sets, our quantum circuit requires 20 qubits, 52 Toffoli gates, 196 CNOT gates, and 13 X gates. The Toffoli depth of our circuit is 36. Compared with previous literature, the quantum circuit proposed herein requires fewer quantum resources.
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.