Beyond Uniformity: Better Security/Efficiency Tradeoffs for Compression Functions

M Stam

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

42 Citations (Scopus)


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 contributionBetter Security/Efficiency Tradeoffs for Compression Functions
Original languageEnglish
Title of host publicationAdvances in Cryptology - CRYPTO 2008
PublisherSpringer Berlin Heidelberg
Pages397 - 412
Number of pages16
ISBN (Print)9783540851738
Publication statusPublished - 2008

Bibliographical note

Conference Proceedings/Title of Journal: Advances in Cryptology - CRYPTO 2008

Fingerprint Dive into the research topics of 'Beyond Uniformity: Better Security/Efficiency Tradeoffs for Compression Functions'. Together they form a unique fingerprint.

Cite this