Journal of Southwest Jiaotong University

Key Search Quantum Circuit Design of AES Cipher

Jiabin Yuan

Published Jan 1, 2010• 0 citations

Abstract

In order to verify the feasibility of applying the quantum search to the key search of block ciphers,a key search quantum circuit of AES(advanced encryption standard) cipher was designed,including KeyExpansion module,encryption module and comparison module,based on the analyses of its computation processes and computation modules needed to be achieved.The encryption module includes four sub-modules,i.e.,quantum AddRoundKey,SubBytes,ShiftRows and MixColumns.In order to reuse the working quantum bits,the reversible computation is used to eliminate the quantum entanglement effect,and different methods of the reversible computation are adopted to different tasks of the 4 sub-modules in the realization of the quantum encryption module so as to save computation time and quantum memory.The research shows that applying the quantum search scheme to the key search of block ciphers to save square root time is feasible.

Related papers

A quantum circuit design of AES requiring fewer quantum qubits and gate operations

Ze-Guo Wang, Shi-Jie Wei, Gui‐Lu Long

Advanced Encryption Standard (AES) is one of the most widely used block ciphers nowadays, and has been established as an encryption standard in 2001. Here we design AES-128 and the sample-AES (S-AES) quantum circuits for deciphering. In the quantum circuit of AES-128, we perform an affine transformation for the SubBytes part to solve the problem that the initial state of the output qubits in SubBytes is not the ∣0⟩ ⊗8 state. After that, we are able to encode the new round sub-key on the qubits encoding the previous round sub-key, and this improvement reduces the number of qubits used by 224 compared with Langenberg et al. ’s implementation. For S-AES, a complete quantum circuit is presented with only 48 qubits, which is already within the reach of existing noisy intermediate-scale quantum computers.

arXiv:2109.12354Frontiers of PhysicsFeb 5, 202240 citations

Quantum Grover Attack on the Simplified-AES

Mishal Almazrooie, Rosni Abdullah, Azman Samsudin +1 more

In this work, a quantum design for the Simplified-Advanced Encryption Standard (S-AES) algorithm is presented. Also, a quantum Grover attack is modeled on the proposed quantum S-AES. First, quantum circuits for the main components of S-AES in the finite field F2[x]/(x4 + x + 1), are constructed. Then, the constructed circuits are put together to form a quantum version of S-AES. A C-NOT synthesis is used to decompose some of the functions to reduce the number of the needed qubits. The quantum S-AES is integrated into a black-box queried by Grover's algorithm. A new approach is proposed to uniquely recover the secret key when Grover attack is applied. The entire work is simulated and tested on a quantum mechanics simulator. The complexity analysis shows that a block cipher can be designed as a quantum circuit with a polynomial cost. In addition, the secret key is recovered in quadratic speedup as promised by Grover's algorithm.

International Conference on Software and Computer Applications (ICSCA)Feb 8, 201815 citations

Efficient Implementation of PRESENT and GIFT on Quantum Computers

Kyungbae Jang, Gyeongju Song, Hyunjun Kim +3 more

Grover search algorithm is the most representative quantum attack method that threatens the security of symmetric key cryptography. If the Grover search algorithm is applied to symmetric key cryptography, the security level of target symmetric key cryptography can be lowered from n-bit to n2-bit. When applying Grover’s search algorithm to the block cipher that is the target of potential quantum attacks, the target block cipher must be implemented as quantum circuits. Starting with the AES block cipher, a number of works have been conducted to optimize and implement target block ciphers into quantum circuits. Recently, many studies have been published to implement lightweight block ciphers as quantum circuits. In this paper, we present optimal quantum circuit designs of symmetric key cryptography, including PRESENT and GIFT block ciphers. The proposed method optimized PRESENT and GIFT block ciphers by minimizing qubits, quantum gates, and circuit depth. We compare proposed PRESENT and GIFT quantum circuits with other results of lightweight block cipher implementations in quantum circuits. Finally, quantum resources of PRESENT and GIFT block ciphers required for the oracle of the Grover search algorithm were estimated.

Applied SciencesMay 23, 202154 citations

Reducing the Cost of Implementing AES as a Quantum Circuit.

Brandon Langenberg, Hai Pham, Rainer Steinwandt

To quantify security levels in a postquantum scenario, it is common to use the quantum resources needed to attack the Advanced Encryption Standard (AES) as a reference value. Specifically, in the National Institute of Standards and Technology's ongoing postquantum standardization effort, different security categories are defined that reflect the quantum resources needed to attack AES-128, AES-192, and AES-256. This article presents a quantum circuit to implement the S-box of AES. Also, leveraging an improved implementation of the key expansion, we identify new quantum circuits for all three AES key lengths. For AES-128, the number of Toffoli gates can be reduced by more than 88% compared to Almazrooie et al. 's and Grassl et al. 's estimates while simultaneously reducing the number of qubits. Our circuits can be used to simplify a Grover-based key search for AES.

Jan 1, 201912 citations

Research on Parallel Quantum Key Search of Block Cipher

Ye Feng

Block cipher has some advantages such as fast,easy to achieve standardization and ease of hardware and software.It has the most extensive application in the computer communication and information system security.This article presents a parallel quantum key search model of block cipher,based on the combination of Grover search algorithm and classical parallel search ideas.Then we put forward the circuit design of corresponding quantum black-box of the typical block cipher.Finally we give a brief performance analysis.

Journal of Chinese Computer SystemsJan 1, 20110 citations

Quantum Security Analysis of AES

Xavier Bonnetain, María Naya‐Plasencia, André Schrottenloher

In this paper we analyze for the first time the post-quantum security of AES. AES is the most popular and widely used block cipher, established as the encryption standard by the NIST in 2001. We consider the secret key setting and, in particular, AES-256, the recommended primitive and one of the few existing ones that aims at providing a post-quantum security of 128 bits. In order to determine the new security margin, i.e., the lowest number of non-attacked rounds in time less than 2128 encryptions, we first provide generalized and quantized versions of the best known cryptanalysis on reduced-round AES, as well as a discussion on attacks that don’t seem to benefit from a significant quantum speed-up. We propose a new framework for structured search that encompasses both the classical and quantum attacks we present, and allows to efficiently compute their complexity. We believe this framework will be useful for future analysis.Our best attack is a quantum Demirci-Selçuk meet-in-the-middle attack. Unexpectedly, using the ideas underlying its design principle also enables us to obtain new, counter-intuitive classical TMD trade-offs. In particular, we can reduce the memory in some attacks against AES-256 and AES-128.One of the building blocks of our attacks is solving efficiently the AES S-Box differential equation, with respect to the quantum cost of a reversible S-Box. We believe that this generic quantum tool will be useful for future quantum differential attacks. Judging by the results obtained so far, AES seems a resistant primitive in the post-quantum world as well as in the classical one, with a bigger security margin with respect to quantum generic attacks.

IACR Transactions on Symmetric CryptologyJun 11, 2019175 citations