Generating short-output digest functions
Long Hoang Nguyen and Andrew William Roscoe
Abstract
This paper introduces two related methods of generating a new cryptographic primitive termed digest which has similarities to epsilon-balanced and almost universal hash functions. Digest functions, however, typically have a very short output, e.g. 16-64 bits, and hence they are not required to resist collision and inversion attacks. They also have the potential to be very fast to compute relative to long-output hash functions. The first construction uses Toeplitz matrix multiplication, which is similar to a Toeplitz based universal hashing algorithm of Krawczyk, whose security requirements can be reduced to the underlying epsilon-biased sequences of random variables. The second is based on integer multiplications which have, perhaps surprisingly, a similar structure to Toeplitz matrix multiplication. However, due to the complication of carry bits, a rigorous mathematical proof of the second construction cannot be provided. We instead exploit the short output of digest functions to carry out statistical analysis, including chi-square tests, quantile-quantile plots and maximum median calculation, of digest collision and distribution test results to argue for the security of the second construction.
Details
| Journal |
To be submitted |
| Year |
2010 |
Links
Related pages
|
People |