Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2024 Sep 10;14(1):21105.
doi: 10.1038/s41598-024-69188-8.

Implementing Grover's on AES-based AEAD schemes

Surajit Mandal  1 , Ravi Anand  2   3 , Mostafizar Rahman  4 , Santanu Sarkar  1 , Takanori Isobe  5
Affiliations

Implementing Grover's on AES-based AEAD schemes

Surajit Mandal et al. Sci Rep. .

Abstract

Extensive research is currently underway to determine the security of existing ciphers in light of the advancements in quantum computing. Against symmetric key cryptography, Grover's search algorithm is a prominent attack, capable of reducing search costs to the square root. For using Grover's algorithm, it is imperative to embed the target cipher into a quantum circuit. Even so, this area of research is relatively new; it has garnered significant attention from the research community. In this study, we provide the first estimation of the cost of Grover's key search attack against the AES-based AEAD schemes Rocca-S, AEGIS-128, and Tiaoxin-346. Our analysis considers circuit depth restrictions specified in NIST's PQC standardization process. Considering NIST's maximum depth constraints, We present the overall cost of these attacks using gate count and depth-times-width metrics. We observed that for MAXDEPTH = 2 40 , Rocca-S, AEGIS-128, and Tiaoxin-346 can be retrieved using Grover's search algorithm with gate count of 1.09 × 2253, 1.14 × 2124, and 1.22 × 2124 respectively. Concerning the current updated values by NIST, these ciphers are secure in terms of the cost of implementing Grover's attack for key recovery. The quantum circuits of these ciphers are implemented using QISKIT, an open-source software development kit (SDK) designed for working with quantum computers running on the IBM Quantum Experience platform.

Keywords: AEGIS-128; Rocca-S; Tiaoxin-346; Grovers; QISKIT.

PubMed Disclaimer

Conflict of interest statement

The authors declare no competing interests.

Figures

Figure 1
Figure 1
Toffoli gate expressed with T-depth 1 representation.
Figure 2
Figure 2
The Grover oracle. The (=) operator assesses the correspondence between the ENC output and the provided ciphertexts, and flips the target qubit in case of equality.
Figure 3
Figure 3
Quantum Circuit for A(X).
Figure 4
Figure 4
The round function of Rocca-S (in image A denotes the AES operation).
Figure 5
Figure 5
Rocca-S Round Function Quantum Circuit.
Figure 6
Figure 6
AEGIS-128 round function(A denotes the AES operation).
Figure 7
Figure 7
AEGIS-128 Round Function Quantum Circuit.
Figure 8
Figure 8
The round function of Tiaoxin-346 (A denotes the AES operation).
Figure 9
Figure 9
Circuit for Tiaoxin-346 round update function.
See this image and copyright information in PMC

References

    1. Shor, P. W. Algorithms for quantum computation: Discrete logarithms and factoring. In 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994, 124–134, 10.1109/SFCS.1994.365700 (IEEE Computer Society).
    1. Shor, P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput.26, 1484–1509. 10.1137/S0097539795293172 (1997).10.1137/S0097539795293172 - DOI
    1. Grassl, M., Langenberg, B., Roetteler, M. & Steinwandt, R. Applying grover’s algorithm to aes: quantum resource estimates. In Post-Quantum Cryptography: 7th International Workshop, PQCrypto 2016, Fukuoka, Japan, February 24-26, 2016, Proceedings 7, 29–43 (Springer, 2016).
    1. Langenberg, B., Pham, H. & Steinwandt, R. Reducing the cost of implementing AES as a quantum circuit. IACR Cryptol. ePrint Arch.2, 854 (2019).
    1. Jaques, S., Naehrig, M., Roetteler, M. & Virdia, F. Implementing grover oracles for quantum key search on AES and lowmc. In Canteaut, A. & Ishai, Y. (eds.) Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part II, vol. 12106 of Lecture Notes in Computer Science, 280–310, 10.1007/978-3-030-45724-2_10 (Springer).

LinkOut - more resources