Public-Key Encryption Schemes with Auxiliary Inputs
- Yevgeniy Dodis ,
- Shafi Goldwasser ,
- Yael Tauman Kalai ,
- Chris Peikert ,
- Vinod Vaikuntanathan
Theory of Cryptography Conference: Lecture Notes in Computer Science, 2010 |
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. As two independent technical contributions, we extend the Goldreich-Levin theorem to provide a hard-core (pseudorandom) value over large fields, and show the security of the learning with errors assumption in the presence of specific (linear) auxiliary information about the secrets