Building indifferentiable compression functions from the PGV compression functions

P. Gauravaram, Nasour Bagheri, Lars Ramkilde Knudsen

Research output: Contribution to journalJournal articleResearchpeer-review


Preneel, Govaerts and Vandewalle (PGV) analysed the security of single-block-length block cipher based compression functions assuming that the underlying block cipher has no weaknesses. They showed that 12 out of 64 possible compression functions are collision and (second) preimage resistant. Black, Rogaway and Shrimpton formally proved this result in the ideal cipher model. However, in the indifferentiability security framework introduced by Maurer, Renner and Holenstein, all these 12 schemes are easily differentiable from a fixed input-length random oracle (FIL-RO) even when their underlying block cipher is ideal. We address the problem of building indifferentiable compression functions from the PGV compression functions. We consider a general form of 64 PGV compression functions and replace the linear feed-forward operation in this generic PGV compression function with an ideal block cipher independent of the one used in the generic PGV construction. This modified construction is called a generic modified PGV (MPGV). We analyse indifferentiability of the generic MPGV construction in the ideal cipher model and show that 12 out of 64 MPGV compression functions in this framework are indifferentiable from a FIL-RO. To our knowledge, this is the first result showing that two independent block ciphers are sufficient to design indifferentiable single-block-length compression functions.
Original languageEnglish
JournalDesigns, Codes and Cryptography
Issue number2
Pages (from-to)547-581
Number of pages35
Publication statusPublished - 2016


  • Compression function
  • Generic MPGV
  • Generic PGV
  • Hash function
  • Indifferentiability


Dive into the research topics of 'Building indifferentiable compression functions from the PGV compression functions'. Together they form a unique fingerprint.

Cite this