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 -