Vinod Vaikuntanathan

Public key Encryption Schemes with Auxiliary Input

Y. Dodis, S. Goldwasser, Y. Kalai, C. Peikert and V. Vaikuntanathan '09

We construct public-key cryptosystems that remain secure even when the
adversary is given any computationally uninvertible function of the
secret key as auxiliary input (even one that may reveal the secret key
information-theoretically).  Our schemes are based on the decisional
Diffie-Hellman and Learning with Errors problems.

Our technical contributions include:

* a novel extension of the Goldreich-Levin theorem to provide a
hard-core (pseudorandom) value over large fields, and
* a proof that the learning with errors assumption holds even in the
presence of auxiliary information about the secrets.