Hardness-Preserving Reductions via Cuckoo Hashing

Itay Berman    Iftach Haitner     Ilan Komargodski    Moni Naor 

Abstract:

A pseudorandom function family (PRF) can be made more usable and more secure by first hashing the input into a smaller domain. This approach is used to achieve ``PRF domain extension"  using a short, e.g., fixed, input length PRF to get a variable-length PRF. Such reductions, however, are vulnerable to a ``birthday attack": after squareroot of of the range size  queries to the resulting PRF, a collision (i.e., two distinct inputs having the same hash value) is very likely to occur. As a consequence, the resulting PRF is insecure against an attacker making this number of queries.

In this work we 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, cleverly assigning each element to one of the two tables. We use this approach to obtain:

1.  A domain extension method that requires just two calls to the original PRF, can withstand as many queries as the original domain size, and has a distinguishing probability that is exponentially small in the amount of non-cryptographic work.
2.  A security-preserving reduction from non-adaptive to adaptive PRFs.

Paper: PDF.

Back to: On-Line Publications, Recent Papers

Back Home