2012 | OriginalPaper | Chapter
Optimal Collision Security in Double Block Length Hashing with Single Length Key
Author : Bart Mennink
Published in: Advances in Cryptology – ASIACRYPT 2012
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The idea of double block length hashing is to construct a compression function on 2
n
bits using a block cipher with an
n
-bit block size. All optimally secure double length hash functions known in the literature employ a cipher with a key space of double block size, 2
n
-bit. On the other hand, no optimally secure compression functions built from a cipher with an
n
-bit key space are known. Our work deals with this problem. Firstly, we prove that for a wide class of compression functions with two calls to its underlying
n
-bit keyed block cipher collisions can be found in about 2
n
/2
queries. This attack applies, among others, to functions where the output is derived from the block cipher outputs in a linear way. This observation demonstrates that all security results of designs using a cipher with 2
n
-bit key space crucially rely on the presence of these extra
n
key bits. The main contribution of this work is a proof that this issue can be resolved by allowing the compression function to make one extra call to the cipher. We propose a family of compression functions making three block cipher calls that asymptotically achieves optimal collision resistance up to 2
n
(1 −
ε
)
queries and preimage resistance up to 2
3
n
(1 −
ε
)/2
queries, for any
ε
> 0. To our knowledge, this is the first optimally collision secure double block length construction using a block cipher with single length key space.