Preimage resistance of LPmkr with r = m-1

Abstract

In this paper, we give a concrete analysis of preimage resistance for a wide class of linearly-dependent permutation-based compression functions. Specifically, we prove the preimage resistance of LPmkr with r = m - 1 up to 2((k-1)n/k-logn) queries. As a special case, the preimage resistance of LP362 is proved up to 2(5n/6-logn) query complexity, closing the gap between the lower bound (= 2(4n/5)) and the upper bound (= 2(5n/6)) presented in Rogaway and Steinberger (2008) [9]. (C) 2010 Elsevier B.V. All rights reserved.