A Quantum Differential Attack on ChaCha and Related Resources Estimation

Existing classical cryptanalytic techniques against ChaCha primarily rely on differential cryptanalysis, leveraging probabilistic neutral bits (PNBs) introduced by Aumasson <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">et al</i>. Separately, Bathe <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">et al</i>. proposed a quantum brute force search attack using Grover’s algorithm with complexity 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">128</sup>. However, since the setups for brute force attacks and differential attacks with probabilistic neutral bits differ significantly, the feasibility of applying Grover’s algorithm to the existing differential attacks on ChaCha remained unclear. In this paper, we demonstrate for the first time that a quantum setup for a PNB-based differential attack is indeed possible on ChaCha, where we can utilize the power of Grover’s algorithm to improve further. By combining Grover’s algorithm with PNB-based differential attack, we propose a quantum algorithm for PNB based differential attack and present a quantum attack on 6-round ChaCha that provides more than a quadratic speedup. Specifically, our attack achieves a complexity of 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">70</sup>, surpassing the quadratic speedup of the brute-force attack applying Grover’s algorithm, proposed by Bathe <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">et al</i>. We achieve a circuit depth of 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">83</sup> with our algorithm, marking a substantial advancement in efficiency.