|
|
A quantum circuit design of AES requiring fewer quantum qubits and gate operations |
Ze-Guo Wang1, Shi-Jie Wei1,2(), Gui-Lu Long1,2,3,4() |
1. State Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, China 2. Beijing Academy of Quantum Information Sciences, Beijing 100193, China 3. Beijing National Research Center for Information Science and Technology and School of Information Tsinghua University, Beijing 100084, China 4. Frontier Science Center for Quantum Information, Beijing 100084, China |
|
|
Abstract 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.
|
Keywords
AES
S-AES
quantum circuit
quantum attack
|
Corresponding Author(s):
Shi-Jie Wei,Gui-Lu Long
|
Issue Date: 18 February 2022
|
|
1 |
M. Bellare and P. Rogaway , Introduction to modern cryptography, Ucsd Cse 207, 207 (2005)
|
2 |
R. L. Rivest , A. Shamir , and L. Adleman , A method for obtaining digital signatures and public key cryptosystems, Comm. ACM 21 (2), 120 (1978)
https://doi.org/10.1145/359340.359342
|
3 |
P. W. Shor , Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26 (5), 1484 (1997)
https://doi.org/10.1137/S0097539795293172
|
4 |
D. Joan and R. Vincent , The design of rijndael: AES — The advanced encryption standard, Inf. Secur. Cryptogr (2002)
|
5 |
L. K. Grover , A fast quantum mechanical algorithm for database search, in: Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, 1996, pp 212- 219
https://doi.org/10.1145/237814.237866
|
6 |
G. L. Long , Grover algorithm with zero theoretical failure rate, Phys. Rev. A 64 (2), 022307 (2001)
https://doi.org/10.1103/PhysRevA.64.022307
|
7 |
A. Yamamura and H. Ishizuka , Quantum cryptanalysis of block ciphers (Algebraic Systems, Formal Languages and Computations), RIMS Kokyuroku 1166, 235 (2000)
|
8 |
M. Kaplan , Quantum attacks against iterated block ciphers, arXiv: 1410.1434 (2014)
|
9 |
R. J. Li and C. H. Jin , Meet-in-the-middle attacks on 10- round AES-256, Des. Codes Cryptogr. 80 (3), 459 (2016)
https://doi.org/10.1007/s10623-015-0113-3
|
10 |
A. Ambainis , Quantum walk algorithm for element distinctness, SIAM J. Comput. 37 (1), 210 (2007)
https://doi.org/10.1137/S0097539705447311
|
11 |
M. Roetteler and R. Steinwandt , A note on quantum related-key attacks, Inf. Process. Lett. 115 (1), 40 (2015)
https://doi.org/10.1016/j.ipl.2014.08.009
|
12 |
D. R. Simon , On the power of quantum computation, in: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994, pp 116- 123
|
13 |
M. Grassl , B. Langenberg , M. Roetteler , and R. Steinwandt , Applying Grover’s algorithm to AES: Quantum resource estimates, in: Post-Quantum Cryptography, Springer, 2016, pp 29- 43
|
14 |
P. Kim , D. Han , and K. C. Jeong , Time– space complexity of quantum search algorithms in symmetric cryptanalysis: Applying to AES and SHA-2, Quantum Inform. Process. 17 (12), 339 (2018)
https://doi.org/10.1007/s11128-018-2107-3
|
15 |
M. Almazrooie , R. Abdullah , A. Samsudin , and K. N. Mutter , Quantum Grover attack on the simplified-AES, in: Proceedings of the 7th International Conference on Software and Computer Applications, 2018, pp 204- 211
|
16 |
F. Arute , K. Arya , R. Babbush , D. Bacon , J. C. Bardin , et al. , Quantum supremacy using a programmable superconducting processor, Nature 574 (7779), 505 (2019)
https://doi.org/10.1038/s41586-019-1666-5
|
17 |
J. Xu , S. Li , T. Chen , and Z. Y. Xue , Nonadiabatic geometric quantum computation with optimal control on superconducting circuits, Front. Phys. 15 (4), 41503 (2020)
https://doi.org/10.1007/s11467-020-0976-2
|
18 |
B. Langenberg , H. Pham , and R. Steinwandt , Reducing the cost of implementing the advanced encryption standard as a quantum circuit, IEEE Trans. Quantum Eng. 1, 1 (2020)
https://doi.org/10.1109/TQE.2020.2965697
|
19 |
J. Boyar and R. Peralta , A new combinational logic minimization technique with applications to cryptology, in: International Symposium on Experimental Algorithms, Springer, 2010, pp 178- 189
|
20 |
J. Zou , Z. H. Wei , S. W. Sun , X. M. Liu , and W. L. Wu , Quantum circuit implementations of AES with fewer qubits, in: International Conference on the Theory and Application of Cryptology and Information Security, Springer, 2020, pp 697- 726
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|