Grover on SIMON

Abstract

For any symmetric key cryptosystem with $n$-bit secret key, the key can be recovered in $O(2^{n/2})$ exploiting Grover search algorithm, resulting in the effective key length to be half. In this direction, subsequent work has been done on AES and some other block ciphers. On the other hand, lightweight ciphers like SIMON was left unexplored. In this backdrop, we present Grover's search algorithm on all the variants of SIMON and enumerate the quantum resources to implement such attack in terms of NOT, CNOT and Toffoli gates. We also provide the T-depth of the circuits and the number of qubits required for the attack. We show that the number of qubits required for implementing Grover on SIMON $2n/mn$ is $O(2nr+mn)$, where $r$ is the number of chosen plaintext-cipher text pairs. We run a reduced version of SIMON in IBMQ quantum simulator and the 14-qubits processor as well. We found that where simulation supports theory, the actual implementation is far from the reality due to the infidelity of the gates and short decoherence time of the qubits. The complete codes for all version of SIMON have also been presented.

References in corpus (7)

• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Breaking Symmetric Cryptosystems using Quantum Period Finding
• Quantum circuits of T-depth one
• Fault-Tolerant Logical Gates in the IBM Quantum Experience
• Quantum Attacks without Superposition Queries: the Offline Simon's Algorithm
• Quantum attacks against iterated block ciphers
• Introduction to Coding Quantum Algorithms: A Tutorial Series Using Pyquil

Cited by in corpus (2)

• Qubit Optimized Quantum Implementation of SLIM
• Quantum Key Recovery Attack on SIMON Block Cipher