Abstract
<title>Abstract</title> <p>It is assumed that the attacker obtains an error-containing noisy key through side-channel attacks, and the probability distribution of the key space follows a \((n)\)-fold Bernoulli distribution. We investigate the key search problem of cryptographic algorithms in the scenario of side-channel attacks. The main contributions of this study are summarized as follows: First, the computational complexity of the classical key search algorithm in the scenario of side-channel attacks is derived. Second, a quantum key search algorithm is designed based on Grover’s algorithm and Montanaro's algorithm. By leveraging the \((n)\)-fold Bernoulli distribution, the key space partition strategy is determined, different from Montanaro's algorithm, thus developing an improved quantum key search algorithm; the computational complexity of this improved algorithm is further analyzed. Simulation results show that the proposed quantum key search algorithm can achieve a super-quadratic speedup over the classical counterpart under side-channel attack conditions. Taking a 256-bit cryptographic key as an example (1% BER), the query complexity decreases from \((2^{256})\) for the conventional classical algorithm to \((2^{62.29})\) with side-channel attacks, and is further reduced from Glaser's \((2^{21.59})\) to \((2^{19.77})\) by our quantum algorithm. Correspondingly, the speedup factor of the proposed quantum algorithm relative to the classical algorithm under side-channel attack conditions reaches 3.15, while the speedup factor reported by Glaser is only 2.73 under the same conditions. Third, to address the difficulty of input state preparation in the our quantum algorithm, we transform the problem of input state preparation into the preparation of the Dicke state. The Dicke state can be implemented by \((O(nd))\) CNOT gates with \((O\left(d \log \frac{n}{d}\right))\) circuit depth for ion trap topology (or \((O\left(\sqrt{nd}\right))\) circuit depth for superconducting topology) in short-depth quantum circuits, and the input state of our algorithm only need to add \((O(d))\) \((X)\)-gates based on the Dicke state.</p>