IACR News item: 27 December 2012
Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor
ePrint ReportIn 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.
Additional news items may be found on the IACR news page.