[Resource Topic] 2023/327: New Quantum Search Model on Symmetric Ciphers and Its Applications

Welcome to the resource topic for 2023/327

New Quantum Search Model on Symmetric Ciphers and Its Applications

Authors: Yangru Zheng, Juntao Gao, Baocang Wang


It has been a long-standing viewpoint that doubling the length of key seeds in symmetric cipher can resist the quantum search attacks. This paper establishes a quantum key search model to deal with the post-quantum security of symmetric ciphers. The quantum search is performed in the punctured keystream/ciphertext space instead of the key space. On inputting the punctured keystreams/ciphertexts, we rule out the fake keys and find out the real key via the iterative use of the quantum singular value search algorithm.
We find out several parameters, such as the length and min-entropy of the punctured keystream, the iterations, and the error in the search algorithm, and all of them can influence the resulting complexity. When these parameters are chosen properly, a better complexity can be obtained than Grover algorithm. Our search model can apply to any typical symmetric cipher. To demonstrate the power, we apply our model to analyze block cipher AES family, stream ciphers Grain-128 and ZUC-128. The resulting complexity of AES-128 is \tilde{\mathcal O}(2^{30.8}), \tilde{\mathcal O}(2^{32.0}) of AES-192, \tilde{\mathcal O}(2^{32.7}) of AES-256, \tilde{\mathcal O}(2^{27.5}) of Grain-128, and \tilde{\mathcal O}(2^{39.8}) of ZUC-128.

Our results show that increasing the length of key seeds is not an effective way anymore to resist the quantum search attacks, and it is necessary to propose new measures to ensure the post-quantum security of symmetric ciphers.

ePrint: https://eprint.iacr.org/2023/327

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .