Paper 2026/426

Post-Quantum Security of Keyed Sum of Permutations and Its Siblings

, Institute for Advancing Intelligence (IAI), TCG CREST, Kolkata, India, Academy of Scientific and Innovative Research (AcSIR), Ghaziabad, India

Avijit Dutta, Institute for Advancing Intelligence (IAI), TCG CREST, Kolkata, India, Academy of Scientific and Innovative Research (AcSIR), Ghaziabad, India

Sougata Mandal, Institute for Advancing Intelligence (IAI), TCG CREST, Kolkata, India, Ramakrishna Mission Vivekananda Educational and Research Institute, Belur, India

Hrithik Nandi, Institute for Advancing Intelligence (IAI), TCG CREST, Kolkata, India, Ramakrishna Mission Vivekananda Educational and Research Institute, Belur, India

Amlan Sinha, Institute for Advancing Intelligence (IAI), TCG CREST, Kolkata, India, Academy of Scientific and Innovative Research (AcSIR), Ghaziabad, India

Abstract

The rapid advancement of quantum computing poses significant challenges to the security of existing cryptographic constructions. Several constructions that are provably secure in the classical setting, e.g., the $3$-round Luby–Rackoff, Even–Mansour, Keyed Sum of Permutations, become vulnerable when the adversary is granted quantum oracle access (the Q2 model). In contrast, when the adversary is restricted to classical oracle queries while retaining the ability to perform quantum computations locally (the Q1 model), such attacks no longer apply. In this paper, we investigate the Q1 security of the Keyed Sum of Permutations construction and two closely related variants - one employing identical permutations and another using a single key. We prove that all three constructions achieve $n/3$-bit security in the Q1 model. In addition, for the same-key variant, we exhibit a key-recovery attack with matching complexity, thereby establishing the tightness of our security bound. For the remaining two constructions, we derive key-recovery attacks with complexity $2^{2n/3}$.

@misc{cryptoeprint:2026/426,
      author = {Nilanjan Datta and Avijit Dutta and Sougata Mandal and Hrithik Nandi and Amlan Sinha},
      title = {Post-Quantum Security of Keyed Sum of Permutations and Its Siblings},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/426},
      year = {2026},
      url = {https://eprint.iacr.org/2026/426}
}