Georgia Institute of Technology College of Sciences

We construct efficient and natural encryption schemes that remain secure (in the standard model) even when used to encrypt messages that may depend upon their secret keys. Our schemes are based on well-studied "noisy learning" problems. In particular, we design 1) A symmetric-key cryptosystem based on the "learning parity with noise" (LPN) problem, and 2) A public-key cryptosystem based on the "learning with errors" (LWE) problem, a generalization of LPN that is at least as hard as certain worst-case lattice problems (Regev, STOC 2005; Peikert, STOC 2009). Remarkably, our constructions are close (but non-trivial) relatives of prior schemes based on the same assumptions --- which were proved secure only in the usual key-independent sense --- and are nearly as efficient. For example, our most efficient public-key scheme encrypts and decrypts in amortized O-tilde(n) time per message bit, and has only a constant ciphertext expansion factor. This stands in contrast to the only other known standard-model schemes with provable security for key-dependent messages (Boneh et al., CRYPTO 2008), which incur a significant extra cost over other semantically secure schemes based on the same assumption. Our constructions and security proofs are simple and quite natural, and use new techniques that may be of independent interest. This is joint work with Chris Peikert and Amit Sahai.