Welcome to the resource topic for 2025/472
Title:
Quantum Attacks on Sum of Even-Mansour Construction Utilizing Online Classical Queries
Authors: Zhenqiang Li, Shuqin Fan, Fei Gao, Yonglin Hao, Hongwei Sun, Xichao Hu, Dandan Li
Abstract:The Sum of Even-Mansour (SoEM) construction, proposed by Chen et al. at Crypto 2019, has become the basis for designing some symmetric schemes, such as
the nonce-based MAC scheme \text{nEHtM}_{p} and the nonce-based encryption scheme \text{CENCPP}^{\ast}. In this paper, we make the first attempt to study the quantum security of SoEM under the Q1 model where the targeted encryption oracle can only respond to classical queries rather than quantum ones.
Firstly, we propose a quantum key recovery attack on SoEM21 with a time complexity of \tilde{O}(2^{n/3}) along with O(2^{n/3}) online classical queries. Compared with the current best classical result which requires O(2^{2n/3}), our method offers a quadratic time speedup while maintaining the same number of queries. The time complexity of our attack is less than that observed for quantum exhaustive search by a factor of 2^{n/6}. We further propose classical and quantum key recovery attacks on the generalized SoEMs1 construction (consisting of s\geq 2 independent public permutations), revealing that the application of quantum algorithms can provide a quadratic acceleration over the pure classical methods. Our results also imply that the quantum security of SoEM21 cannot be strengthened merely by increasing the number of permutations.
ePrint: https://eprint.iacr.org/2025/472
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 .