Igors Stepanovs (Theory Seminar F14)

stepanov.jpg"Poly-Many Hardcore Bits for Any One-Way Function"
Igors Stepanovs
Monday, November 17th, 2014, 2:00 pm
EBU3B, Room 4258
We show how to extract an arbitrary polynomial number of simultaneously hardcore bits from any one-way function. In the case the one-way function is injective or has polynomially-bounded pre-image size, we assume the existence of indistinguishability obfuscation (iO). In the general case, we assume the existence of differing-input obfuscation (diO). Our construction for injective one-way functions extends to extract hardcore bits on multiple, correlated inputs, yielding new D-PKE schemes.

Joint work with Mihir Bellare and Stefano Tessaro.

Paper available at http://eprint.iacr.org/2013/873.pdf