Linear-Size Universal Hashing
Speaker: Rafail Ostrovsky , UCLA
Date: December 7 2010
Time: 4:15PM to 5:15PM
Location: 32-144
Host: Scott Aaronson, CSAIL, MIT
Contact: Be Blackburn , 3-6098, imbe@mit.edu
Relevant URL: In this talk, we resolve a 30-year-old line of work on the asymptotic
computational complexity of universal hashing, an intensively studied
topic since the introduction of universal hashing by Carter and Wegman
(STOC 1977). Universal hash functions are fundamental algorithmic
constructs, and their use is widespread throughout computer science.
It was widely believed that pairwise-independent hashing, because of
its pseudorandom properties, is inherently computationally costly.
Our work shows that this is not the case by giving an explicit
construction of linear-size circuits for universal hash functions,
refuting a conjecture of Mansour, Nisan, and Tiwari (STOC 1990).
We were led to this result through our study of methods to reduce the
computational complexity of cryptographic primitives and protocols.
Current constructions of cryptographic primitives typically involve a
large multiplicative computational overhead that grows with the
desired level of security. We explore the possibility of implementing
cryptographic primitives (such as encryption, authentication,
signatures, or secure two-party computation) while incurring only a
constant computational overhead compared to insecure implementations
of the same tasks. The talk will be self-contained and accessible to
the general audience.
This is joint work with Yuval Ishai, Eyal Kushilevitz, and Amit Sahai.
See other events that are part of Theory Colloquium 2010/2011
See other events happening in December 2010
