Cryptology ePrint Archive: Report 2021/1211

Grover on SPEEDY

Gyeongju Song and Kyungbae Jang and Hyunjun Kim and Siwoo Eum and Minjoo Sim and Hyunji Kim and Wai-Kong Lee and Hwajeong Seo

Abstract: With the advent of quantum computers, revisiting the security of cryptography has been an active research area in recent years. In this paper, we estimate the cost of applying Grover's algorithm to SPEEDY block cipher. SPEEDY is a family of ultra-low-latency block ciphers presented in CHES'21. It is ensured that the key search equipped with Grover's algorithm reduces the $n$-bit security of the block cipher to $\frac{n}{2}$-bit. The issue is how many quantum resources are required for Grover's algorithm to work. NIST estimates the post-quantum security strength for symmetric key cryptography as the cost of Grover key search algorithm. SPEEDY provides 128-bit security or 192-bit security depending on the number of rounds. Based on our estimated cost, we present that increasing the number of rounds is insufficient to satisfy the security against attacks on quantum computers. To the best of our knowledge, this is the first implementation of SPEEDY as a quantum circuit.

Category / Keywords: implementation / Grover's Search Algorithm, Quantum Computing, SPEEDY