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

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.

Graphical abstract

Keywords

AES / S-AES / quantum circuit / quantum attack

References

[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)

[3] P. W. Shor , Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26 (5), 1484 (1997)

[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

[6] G. L. Long , Grover algorithm with zero theoretical failure rate, Phys. Rev. A 64 (2), 022307 (2001)

[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)

[10] A. Ambainis , Quantum walk algorithm for element distinctness, SIAM J. Comput. 37 (1), 210 (2007)

[11] M. Roetteler and R. Steinwandt , A note on quantum related-key attacks, Inf. Process. Lett. 115 (1), 40 (2015)

[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)

[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)

[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)

[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)

[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

RIGHTS & PERMISSIONS

Higher Education Press