Quantum Resource Estimates of Grover’s Key Search on ARIA

Amit Kumar Chauhan, Somitra Kumar Sanadhya

Kyungbae Jang, Seungjoo Choi, Hyeokdong Kwon +1 more

Yujin Oh, Kyungbae Jang, Yujin Yang +1 more

The progression of quantum computing is considered a potential threat to traditional cryptography system, highlighting the significance of post-quantum security in cryptographic systems. Regarding symmetric key encryption, the Grover algorithm can approximately halve the search complexity. Despite the absence of fully operational quantum computers at present, the necessity of assessing the security of symmetric key encryption against quantum computing continues to grow.In this paper, we implement the ARIA block cipher in a quantum circuit and compare it with previous research. Our implementation of the ARIA quantum circuit achieves over 92.5% improvement in full depth and over 98.7% improvement in Toffoli depth compared to the implementation proposed in Chauhan et al. Compared to Yang et al.’s implementation, our implementation is improved the full depth by 36.7% and the number of qubits by 8%. Additionally, we analyze the complexity of Grover’s search attack and compare it with NIST criteria. We confirm that ARIA achieves quantum security level 1, 3, and 5 (ARIA-128, 192, and 256, respectively).

Markus Grassl, Brandon Langenberg, Martin Roetteler +1 more

Bhupendra Singh, Mohankumar Mylsamy, Thamaraimanalan Thangarajan

“Grover's Algorithm: Quantum Search” explores Grover's Algorithm in the context of quantum search, beginning with an overview of its mechanics. The section includes a literature survey that covers Grover's algorithm, stream ciphers, and the Grover attack, as well as quantum resource estimation. The section then introduces a simplified 4-bit Grain cipher (with a 4-bit key and 4-bit IV), detailing its design, initialization, and key stream generation. Following this, the chapter discusses about key recovery using Grover's algorithm, with an emphasis on quantum circuit development for the simplified Grain 4-bit cipher. It outlines key steps in the circuit, such as executing the Boolean function and XORing the NFSR's fourth bit. Further, the section details the development of a Grover attack quantum circuit, describing both single and double pair methods. Experimental results are provided across multiple cases, with a summary of test cases and classical computation times. Quantum resource estimation, including the costs associated with the simplified Grain 4-bit cipher and the Grover oracle, is analyzed. The section concludes with a discussion on the results, classical and quantum resource estimations, and the potential for future enhancements to the approach.

Honghan Yan