Beyond uniformity: Better security/efficiency tradeoffs for compression functions

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.


Published in:
Advances In Cryptology - Crypto 2008, Proceedings, 5157, 397-412
Presented at:
28th Annual International Cryptology Conference, Santa Barbara, CA, Aug 17-21, 2008
Year:
2008
Publisher:
Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa
ISBN:
978-3-540-85173-8
Keywords:
Laboratories:




 Record created 2010-11-30, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)