Grover on KATAN: Quantum Resource Estimation
Mostafizar Rahman, Goutam Paul
Abstract
This article presents the cost analysis of mounting Grover’s key search attack on the family of KATAN block cipher. Several designs of the reversible quantum circuit of KATAN are proposed. Owing to the National Insitute of Standards and Technology’s (NIST) proposal for postquantum cryptography standardization, the circuits are designed focusing on minimizing the overall depth. We observe that the reversible quantum circuits designed using <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"/> <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">and</small> gates and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$T$</tex-math></inline-formula> -depth one Toffoli gate give more shallow circuits. Grover oracle for KATAN is designed based on the reversible circuits, which are used further to mount Grover’s key search attack on KATAN. The designs are implemented using the software framework ProjectQ, which provides a resource estimation tool to perform an appropriate cost analysis in an automated way. While estimating the resources, NIST’s depth restrictions are also respected.