On cryptography with auxiliary input

We study the question of designing cryptographic schemes which are secure even if an arbitrary function f(sk) of thesecret key is leaked, as long as the secret key sk is still (exponentially)hard to compute from this auxiliary input. Thissetting of auxiliary input is more general than the more traditionalsetting, which assumes that some of information about the secret key sk may be leaked, but sk still hashigh min-entropy left. In particular, we deal with situationswhere f(sk) information-theoretically determines the entire secret key sk. As our main result, we construct CPA/CCA secure symmetric encryption schemes that remain secure with exponentially hard-to-invert auxiliary input. We give several applications of such schemes. We construct an average-case obfuscator for the class of point functions, which remains secure with exponentially hard-to-invert auxiliary input, and is reusable. We construct a reusable and robust extractor that remains secure with exponentially hard-to-invert auxiliary input. Our results rely on a new cryptographic assumption, Learning Subspace-with-Noise (LSN), which is related to the well known Learning Parity-with-Noise (LPN) assumption.