Paper 2023/327

Nested Quantum Search Model on Symmetric Ciphers and Its Applications

Abstract

This paper puts forward a multi-round quantum key search model for symmetric ciphers. We turn an unstructured key search for symmetric ciphers into a nested structured quantum search. By the preimage of punctured ciphertexts (or keystream), we get a convergent sequence of subspaces of the full key space. In each round, our search is performed only in a subspace containing the real key, while the rest part is removed from search space. We find out several parameters, the length $s$ of the punctured ciphertext (or keystream), the iteration number $r$, and the error $\delta$ in the search algorithm, which can influence the resulting complexity. The query complexity of our search model is $\tilde {\mathcal O}(2^{\alpha_n\cdot n})$, where $\alpha_n$ is much smaller than $\frac{1}{2}$. Specifically, the query complexity is $\tilde{\mathcal O}(r2^{\frac n {2(r-1)}})$ (ignore constant $\delta$) better than Grover's $\tilde{\mathcal O}(2^{\frac n {2}})$, while parameter $r$ increases as $n$ increases. Our search model can be applied to symmetric ciphers. And it has been shown that doubling the key length is not an effective way anymore to resist the quantum search attacks. Even if the key length is increased by $r-1$ times, symmetric ciphers still struggle to obtain desired security for a re-selected value of $r$.