## Abstract

Suppose we are given a perfect n + c-to-n bit compression function f and we want to construct a larger m + s-to-s bit compression function H instead. What level of security, in particular collision resistance, can we expect from H if it makes r calls to f? We conjecture that typically collisions can be found in 2(nr + cr − m)/(r + 1) queries. This bound is also relevant for building a m + s-to-s bit compression function based on a blockcipher with k-bit keys and n-bit blocks: simply set c = k, or c = 0 in case of fixed keys.
We also exhibit a number of (conceptual) compression functions whose collision resistance is close to this bound. In particular, we consider the following four scenarios:

Translated title of the contribution | Better Security/Efficiency Tradeoffs for Compression Functions |
---|---|

Original language | English |

Title of host publication | Advances in Cryptology - CRYPTO 2008 |

Publisher | Springer Berlin Heidelberg |

Pages | 397 - 412 |

Number of pages | 16 |

Volume | 5157 |

ISBN (Print) | 9783540851738 |

DOIs | |

Publication status | Published - 2008 |