On the impossibility of highly-efficient blockcipher-based hash functions (Q1027986)

The authors investigate the idea of building hash functions from blockciphers. During the years various schemes have been proposed. Although some of them are provably secure they are viewed as inefficient since the blockcipher key has to be changed each round. For the conventional blockciphers this key change is undesirable since scheduling a new key entails a significant computational cost. In the focus of this work, the authors put the question of whether it is possible to achieve provable security without incurring this cost. Fix a small nonempty set of blockcipher keys \(\mathcal{K}\). A blockcipher-based hash function is said to be highly-efficient if it makes exactly one blockcipher call for each message block hashed, and all blockcipher calls use a key from \(\mathcal{K}\). During the years a few highly-efficient constructions have been proposed, but no one has been able to prove their security. In the present paper the authors prove that in the ideal-cipher model it is impossible to construct a highly-efficient iterated blockcipher-based hash function that is provably secure. This result implies, in particular, that the TWeakable Chain Hash construction suggested by \textit{M. Liskov, R. L. Rivest}, and \textit{D. Wagner} [Lect. Notes Comput. Sci. 2442, 31--46 (2002; Zbl 1026.94533)] is not correct under an instantiation suggested for this construction nor can TCH be correctly instantiated by any other efficient means.