Paper 2025/2274
Post-Quantum Security of the Sum of Even-Mansour
, Xidian University, Xidian UniversityAbstract
The Sum of Even-Mansour (SoEM) construction, introduced at Crypto 2019, implements a pseudorandom function via the XOR sum of independent Even-Mansour structures and serves as the core design for symmetric schemes like CENCPP* and nEHTm. This paper establishes the tight post-quantum security of the single-key, two-permutation variant, SoEM21, under the Q1 adversarial model. We prove that when an adversary makes classical queries to the keyed construction and quantum superposition queries to the underlying permutations, SoEM21 guarantees up to \(n/3\) bits of security. This bound exactly matches the \(\tilde{O}(2^{n/3})\) complexity of the recent quantum key recovery attack proposed by Li et al. To demonstrate the applicability of this theoretical bound, we further analyze two SoEM-based symmetric primitives. We use our results to prove the post-quantum security---in the same model---of the symmetric-key schemes 1K-CENCPP* (a nonce-based encryption mode) and the core structure of $n\mathsf{EHTm}_p$ (a nonce-based message authentication code).
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint.
- Keywords
- Post-Quantum CryptographySum of Even-MansourQ1 Quantum SecurityTight Security Bound
- Contact author(s)
-
24011211360 @ stu xidian edu cn
jtgao @ mail xidian edu cn - History
- 2026-05-11: last of 5 revisions
- 2025-12-18: received
- See all versions
- Short URL
- https://ia.cr/2025/2274
- License
-
CC BY-NC-ND
BibTeX
@misc{cryptoeprint:2025/2274,
author = {YanJin Tan and JunTao Gao and XueLian Li},
title = {Post-Quantum Security of the Sum of Even-Mansour},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/2274},
year = {2025},
url = {https://eprint.iacr.org/2025/2274}
}
