Paper 2023/840

Revisiting the Indifferentiability of the Sum of Permutations

Aldo Gunsing, Radboud University Nijmegen
Ritam Bhaumik, École Polytechnique Fédérale de Lausanne
Ashwin Jha, Helmholtz Center for Information Security
Bart Mennink, Radboud University Nijmegen
Yaobin Shen, UCLouvain

The sum of two $n$-bit pseudorandom permutations is known to behave like a pseudorandom function with $n$ bits of security. A recent line of research has investigated the security of two public $n$-bit permutations and its degree of indifferentiability. Mandal et al. (INDOCRYPT 2010) proved $2n/3$-bit security, Mennink and Preneel (ACNS 2015) pointed out a non-trivial flaw in their analysis and re-proved $(2n/3-\log_2(n))$-bit security. Bhattacharya and Nandi (EUROCRYPT 2018) eventually improved the result to $n$-bit security. Recently, Gunsing at CRYPTO 2022 already observed that a proof technique used in this line of research only holds for sequential indifferentiability. We revisit the line of research in detail, and observe that the strongest bound of $n$-bit security has two other serious issues in the reasoning, the first one is actually the same non-trivial flaw that was present in the work of Mandal et al., while the second one discards biases in the randomness influenced by the distinguisher. More concretely, we introduce two attacks that show limited potential of different approaches. We (i) show that the latter issue that discards biases only holds up to $2^{3n/4}$ queries, and (ii) perform a differentiability attack against their simulator in $2^{5n/6}$ queries. On the upside, we revive the result of Mennink and Preneel and show $(2n/3-\log_2(n))$-bit regular indifferentiability security of the sum of public permutations.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2023
indifferentiabilitysum of permutationsattacksresolutions
Contact author(s)
aldo gunsing @ ru nl
ritam bhaumik @ epfl ch
ashwin jha @ cispa de
b mennink @ cs ru nl
yaobin shen @ uclouvain be
2023-06-09: revised
2023-06-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Aldo Gunsing and Ritam Bhaumik and Ashwin Jha and Bart Mennink and Yaobin Shen},
      title = {Revisiting the Indifferentiability of the Sum of Permutations},
      howpublished = {Cryptology ePrint Archive, Paper 2023/840},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.