International Association for Cryptologic Research

International Association
for Cryptologic Research


Revisiting the Indifferentiability of the Sum of Permutations

Aldo Gunsing , Radboud University
Ritam Bhaumik , EPFL
Ashwin Jha , CISPA Helmholtz Center for Information Security
Bart Mennink , Radboud University
Yaobin Shen , UCLouvain
DOI: 10.1007/978-3-031-38548-3_21 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: 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$-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$-bit regular indifferentiability security of the sum of public permutations.
  title={Revisiting the Indifferentiability of the Sum of Permutations},
  author={Aldo Gunsing and Ritam Bhaumik and Ashwin Jha and Bart Mennink and Yaobin Shen},