Revisiting the Indifferentiability of the Sum of Permutations

(2023) Revisiting the Indifferentiability of the Sum of Permutations. (Submitted)

Text 2023-840.pdf Download (646kB)

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-\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.

Item Type:	Conference or Workshop Item (A Paper) (Paper)
Divisions:	Antoine Joux (AJ)
Conference:	CRYPTO Advances in Cryptology
Depositing User:	Ashwin Jha
Date Deposited:	27 Jul 2023 07:17
Last Modified:	27 Jul 2023 07:17
Primary Research Area:	NRA1: Trustworthy Information Processing
URI:	https://publications.cispa.saarland/id/eprint/3998

Actions

Actions (login required)

View Item