Paper 2025/1518

Sequential Indifferentiability of STH and EDM

, Institute for Advancing Intelligence (IAI), TCG CREST, Kolkata, India, Academy of Scientific and Innovative Research (AcSIR), Ghaziabad, India

Avijit Dutta, Institute for Advancing Intelligence (IAI), TCG CREST, Kolkata, India, Academy of Scientific and Innovative Research (AcSIR), Ghaziabad, India

Sougata Mandal, Institute for Advancing Intelligence (IAI), TCG CREST, Kolkata, India, Ramakrishna Mission Vivekananda Educational and Research Institute, Belur, India

Hrithik Nandi, Institute for Advancing Intelligence (IAI), TCG CREST, Kolkata, India, Ramakrishna Mission Vivekananda Educational and Research Institute, Belur, India

Abstract

The notion of indifferentiability was proposed by Maurer et al. to bound the distinguishing advantage of a construction built on a public primitive, from a public random function. In Indocrypt'10, Mandal et al. have shown that the sum of two independent permutations is indifferentiable from a public random function up to $2^{2n/3}$ queries. Later in ACNS'15, Mennink and Preneel identified an analytical flaw of Mandal et al's result and revised the security bound to $2^{2n/3}/n$. In Eurocrypt'18, Bhattacharya and Nandi have improved their indifferentiable bound to $2^n$ queries, which was again identified as incorrect in the analysis by Gunsing et al. In this paper, we study the indifferentiability of a few other PRF constructions, namely STH and EDM constructions. We will show that neither STH nor STH2 is indifferentiable, which led us to propose a generalized version called gSTH. We have shown that gSTH achieves a tight $l$-bit security bound, where $l$ denotes the size of the constants in terms of bits used in the construction. While we show that EDM achieves a tight $n/2$-bit indifferentiable bound with respect to our proposed simulator, single-keyed EDM is not indifferentiable from a public random function. We would like to mention that all the proofs and the attacks have been done in the sequential indifferentiability model.

@misc{cryptoeprint:2025/1518,
      author = {Nilanjan Datta and Avijit Dutta and Sougata Mandal and Hrithik Nandi},
      title = {Sequential Indifferentiability of {STH} and {EDM}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1518},
      year = {2025},
      doi = {10.62056/a3n59qxqi},
      url = {https://eprint.iacr.org/2025/1518}
}