Paper 2020/1485

Quantum Search for Lightweight Block Ciphers: GIFT, SKINNY, SATURNIN

Subodh Bijwe, Amit Kumar Chauhan, and Somitra Kumar Sanadhya

Abstract

Grover's search algorithm gives a quantum attack against block ciphers with query complexity $O(\sqrt{N})$ to search a keyspace of size $N$, when given a sufficient number of plaintext-ciphertext pairs. A recent result by Jaques et al. (EUROCRYPT 2020) presented the cost estimates of quantum key search attacks against AES under different security categories as defined in NIST's PQC standardization process. In this work, we extend their approach to lightweight block ciphers for the cost estimates of quantum key search attacks under circuit depth restrictions. We present quantum circuits for the lightweight block ciphers GIFT, SKINNY, and SATURNIN. We give overall cost in both the gate count and depth-times-width cost metrics, under NIST's maximum depth constraints. We also present Q# implementation of the full Grover oracles for all versions of GIFT, SKINNY, and SATURNIN for unit tests and automatic resource estimations.