Welcome to the resource topic for 2009/048
Title:
A Trade-Off Between Collision Probability and Key Size in Universal Hashing Using Polynomials
Authors: Palash Sarkar
Abstract:Let \rF be a finite field and suppose that a single element of \rF is used as an authenticator (or tag). Further, suppose that any message consists of at most L elements of \rF. For this setting, usual polynomial based universal hashing achieves a collision bound of (L-1)/|\rF| using a single element of \rF as the key. The well-known multi-linear hashing achieves a collision bound of 1/|\rF| using L elements of \rF as the key. In this work, we present a new universal hash function which achieves a collision bound of m\lceil\log_m L\rceil/|\rF|, m\geq 2, using 1+\lceil\log_m L\rceil elements of \rF as the key. This provides a new trade-off between key size and collision probability for universal hash functions.
ePrint: https://eprint.iacr.org/2009/048
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .