CISPA
Browse
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.

History

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

2023-07-27

Open Access Type

  • Green

BibTeX

@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

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC