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, and cleverly assigning each element into one of the two tables. We use this approach to obtain: (i) 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 non cryptographic work. (ii) A security-preserving reduction from non-adaptive to adaptive PRFs.
Category / Keywords: foundations / cuckoo hashing; pseudorandom functions ; hardness preserving reductions; domain extension; non-adaptive to adaptive Publication Info: TCC 2013 proceedings Date: received 24 Dec 2012, last revised 24 Dec 2012 Contact author: ilan komargodski at weizmann ac il Available format(s): PDF | BibTeX Citation Note: Full version. Version: 20121227:173806 (All versions of this report) Short URL: ia.cr/2012/722 Discussion forum: Show discussion | Start new discussion