https://doi.org/10.1140/epjqt/s40507-025-00374-x
Research
Quantum attacks on Sum of Even-Mansour construction utilizing online classical queries
1
State Key Laboratory of Cryptology, 100878, Beijing, China
2
State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, 100876, Beijing, China
3
School of Computer and Big Data (School of Cybersecurity), Heilongjiang University, 150080, Harbin, China
4
School of Computer Science (National Pilot Software Engineering School), Beijing University of Posts and Telecommunications, 100876, Beijing, China
Received:
12
April
2025
Accepted:
26
May
2025
Published online:
5
June
2025
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 
and the nonce-based encryption scheme CENCPP∗. 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 
along with 
online classical queries. Compared with the current best classical result which requires 
time, 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 
. We further propose classical and quantum key recovery attacks on the generalized SoEMs1 construction (consisting of 
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.
Key words: Offline Simon’s algorithm / SoEM construction / Query complexity / Birthday-bound
© The Author(s) 2025
Open Access This article is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License, which permits any non-commercial use, sharing, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if you modified the licensed material. You do not have permission under this licence to share adapted material derived from this article or parts of it. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by-nc-nd/4.0/.
