Grover on $$\,SIMON\,$$ S I M O N
- PDF / 1,295,585 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 90 Downloads / 191 Views
Grover on SIMON Ravi Anand1 · Arpita Maitra2,3
· Sourav Mukhopadhyay1
Received: 25 April 2020 / Accepted: 21 August 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract For any symmetric key cryptosystem with n-bit secret key, the key can be recovered in O(2n/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 S I M O N was left unexplored. In this backdrop, we present Grover’s search algorithm on all the variants of S I M O N 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 S I M O N 2n/mn is O(2nr + mn), where r is the number of chosen plaintext–ciphertext pairs. We run a reduced version of S I M O N in IBMQ quantum simulator and the 14-qubit 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 S I M O N have also been presented. Keywords Lightweight cryptography · Quantum cryptanalysis · Quantum circuits · Grover’s algorithm · Feistel ciphers
1 Introduction The last two decades witnessed an enormous proliferation in the domain of quantum computation and communication. Due to the two pioneering quantum algorithms, Shor’s algorithm [21] and Grover’s search algorithm [6], the security of currently
B
Arpita Maitra [email protected]
1
Department of Mathematics, Indian Institute of Technology Kharagpur, Kharagpur, West Bengal 721302, India
2
TCG Centre for Research and Education in Science and Technology, Kolkata, West Bengal 700091, India
3
CR Rao Advanced Institute of Mathematics, Statistics and Computer Science, Hyderabad, India 0123456789().: V,-vol
123
340
Page 2 of 17
R. Anand et al.
deployed cryptosystems is under a threat. As a consequence, in recent time, a lot of symmetric constructions are being evaluated in quantum settings. For example, one can mention the key recovery attacks against Even–Mansour constructions and distinguishers against three-round Feistel constructions [16]. Not only that, the key recovery attacks against multiple encryptions [12], forgery attacks against CBC-like MACs [13] have also been studied. The list is expanding considering Quantum meetin-the-middle attack on Feistel constructions [9], key recovery attacks against FX constructions [18] etc. Researchers have also tried to convert the existing classical attacks to quantum settings [10,13,14,19]. Very recently, Bonnetain et al. [5] proposed a novel methodology for quantum cryptanalysis on symmetric ciphers. They exploited the algebraic structure of certain classical cryptosystems to bypass the standard quantum superposition queri
Data Loading...
