cispa_all_3998.pdf (631.78 kB)

Revisiting the Indifferentiability of the Sum of Permutations

Download (631.78 kB)
conference contribution
posted on 2023-11-29, 18:23 authored by Aldo Gunsing, Ritam Bhaumik, Ashwin Jha, Bart Mennink, Yaobin Shen
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.


Preferred Citation

Aldo Gunsing, Ritam Bhaumik, Ashwin Jha, Bart Mennink and Yaobin Shen. Revisiting the Indifferentiability of the Sum of Permutations. In: Advances in Cryptology (CRYPTO). 2023.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

Advances in Cryptology (CRYPTO)

Legacy Posted Date


Open Access Type

  • Green


@inproceedings{cispa_all_3998, title = "Revisiting the Indifferentiability of the Sum of Permutations", author = "Gunsing, Aldo and Bhaumik, Ritam and Jha, Ashwin and Mennink, Bart and Shen, Yaobin", booktitle="{Advances in Cryptology (CRYPTO)}", year="2023", }

Usage metrics


    No categories selected


    Ref. manager