Paper 2025/2274

Post-Quantum Security of the Sum of Even-Mansour

JunTao Gao, Xidian University

XueLian Li, Xidian University

Abstract

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).

@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}
}