Hardness Preserving Reductions via Cuckoo Hashing

Provided by: Tekyz Inc.
Topic: Security
Format: PDF
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.

Find By Topic