Hardness Preserving Reductions via Cuckoo Hashing

In this paper, the authors show how to go beyond the birthday attack barrier, by replacing the above simple hashing approach with a variant of cuckoo hashing - a hashing paradigm typically used for resolving hash collisions in a table, by using two hash functions and two tables, and cleverly assigning each element into one of the two tables. They use this approach to obtain: a domain extension method that requires just two calls to the original PRF, which can withstand as many queries as the original domain size and has a distinguishing probability that is exponentially small in the non cryptographic work and a security-preserving reduction from non-adaptive to adaptive PRFs.

Provided by: Tekyz Inc. Topic: Security Date Added: Dec 2012 Format: PDF

Find By Topic