TY - GEN
T1 - On cryptography with auxiliary input
AU - Dodis, Yevgeniy
AU - Kalai, Yael Tauman
AU - Lovett, Shachar
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
KW - Auxiliary information
KW - Code obfuscation
KW - Encryption schemes
KW - Error-correcting codes
KW - Learning parity with noise
KW - Randomness extractors
UR - http://www.scopus.com/inward/record.url?scp=70350674336&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70350674336&partnerID=8YFLogxK
U2 - 10.1145/1536414.1536498
DO - 10.1145/1536414.1536498
M3 - Conference contribution
AN - SCOPUS:70350674336
SN - 9781605585062
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 621
EP - 630
BT - STOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing
T2 - 41st Annual ACM Symposium on Theory of Computing, STOC '09
Y2 - 31 May 2009 through 2 June 2009
ER -