Provable Security of the Knudsen-Preneel Compression Functions

This paper discusses the provable security of the compression functions introduced by Knudsen and Preneel [11,12,13] that use linear error-correcting codes to build wide-pipe compression functions from underlying blockciphers operating in Davies-Meyer mode. In the information theoretic model, we prove that the Knudsen-Preneel compression function based on an

$[r,k,d]_{2^e}$

code is collision resistant up to

$2^{\frac{(r-d+1)n}{2r-3d+3}}$

query complexity if 2

d

 ≤ 

r

 + 1 and collision resistant up to

$2^{\frac{rn}{2r-2d+2}}$

query complexity if 2

d

 > 

r

 + 1. For MDS code based Knudsen-Preneel compression functions, this lower bound matches the upper bound recently given by Özen and Stam [23].

A preimage security proof of the Knudsen-Preneel compression functions has been first presented by Özen et al. (FSE ’10). In this paper, we present two alternative proofs that the Knudsen-Preneel compression functions are preimage resistant up to

$2^{\frac{rn}{k}}$

query complexity. While the first proof, using a wish list argument, is presented primarily to illustrate an idea behind our collision security proof, the second proof provides a tighter security bound compared to the original one.