Building indifferentiable compression functions from the PGV compression functions

P. Gauravaram, Nasour Bagheri, Lars Ramkilde Knudsen

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

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
Volume78
Issue number2
Pages (from-to)547-581
Number of pages35
ISSN0925-1022
DOIs
Publication statusPublished - 2016

Keywords

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

Cite this

@article{f542dffb405f4c188d334f6597435dd6,
title = "Building indifferentiable compression functions from the PGV compression functions",
abstract = "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.",
keywords = "Compression function, Generic MPGV, Generic PGV, Hash function, Indifferentiability",
author = "P. Gauravaram and Nasour Bagheri and Knudsen, {Lars Ramkilde}",
year = "2016",
doi = "10.1007/s10623-014-0020-z",
language = "English",
volume = "78",
pages = "547--581",
journal = "Designs, Codes and Cryptography",
issn = "0925-1022",
publisher = "Springer New York",
number = "2",

}

Building indifferentiable compression functions from the PGV compression functions. / Gauravaram, P.; Bagheri, Nasour; Knudsen, Lars Ramkilde.

In: Designs, Codes and Cryptography, Vol. 78, No. 2, 2016, p. 547-581.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - Building indifferentiable compression functions from the PGV compression functions

AU - Gauravaram, P.

AU - Bagheri, Nasour

AU - Knudsen, Lars Ramkilde

PY - 2016

Y1 - 2016

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

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

KW - Compression function

KW - Generic MPGV

KW - Generic PGV

KW - Hash function

KW - Indifferentiability

U2 - 10.1007/s10623-014-0020-z

DO - 10.1007/s10623-014-0020-z

M3 - Journal article

VL - 78

SP - 547

EP - 581

JO - Designs, Codes and Cryptography

JF - Designs, Codes and Cryptography

SN - 0925-1022

IS - 2

ER -