Paper 2022/013

Quantum Rotational Cryptanalysis for Preimage Recovery of Round-Reduced Keccak

Runsong Wang, Xuelian Li, Juntao Gao, Hui Li, and Baocang Wang

Abstract

This paper considers the capability of 4-round Keccak-224/256/384/512 against the cryptanlysis involved by the quantum algorithm. In order to effectively find the corresponding rotational number for the rotational counterpart of preimage, we first establish a probabilistic algorithm based on the Grover search to guess a possible rotational number by using the fixed relations of bits pairs in some coordinates. This is committed to achieving that each iteration of searching the rotational counterparts contains only one run of 4-round Keccak variant applied for the verification, which can reduce the attack complexity in the quantum setting. Based on finding the rotational number under an acceptable randomness, we construct two attack models to focus on the recovery of preimage. In the first model, the Grover’s algorithm serves as finding out a rotational counterpart of the preimage. Through 64 attempts of checking the correct rotational number, the desired preimage can be obtained. In the second model, we abstract the finding of rotational counterparts into searching vertexes on a hypercube, and then, the SKW quantum algorithm is used to deal with the finding of the vertexes acted as rotational counterparts. Compared to the recent works in classical setting, we greatly reduce the attack complexity of preimage recovery. Furthermore, the first attack model is superior to the generic quantum preimage attack for 4-round Keccak-224/256/384/512, and the second model has slightly lower attack effect but more practicality on the 4-round Keccak-512/384, that is, the model is exponentially easier to implement in quantum circuit than both our first attack model and the generic quantum preimage attack.