**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:

- 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.
- A security-preserving reduction from non-adaptive to adaptive PRFs.

**Paper: ** PDF.

Back to: On-Line Publications, Recent Papers

Back Home