On cryptography with auxiliary input

ABSTRACT

We study the question of designing cryptographic schemes which are secure even if an arbitrary function f(sk) of the secret key is leaked, as long as the secret key sk is still (exponentially) hard to compute from this auxiliary input. This setting of auxiliary input is more general than the more traditional setting, which assumes that some of information about the secret key sk may be leaked, but sk still has high min-entropy left. In particular, we deal with situations where 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.

REFERENCES

• 1: Adi Akavia , Shafi Goldwasser , Vinod Vaikuntanathan, Simultaneous Hardcore Bits and Cryptography against Memory Attacks, Proceedings of the 6th Theory of Cryptography Conference on Theory of Cryptography, p.474-495, March 15-17, 2009, San Francisco, CA [doi>10.1007/978-3-642-00457-5_28]
• 2: B. Applebaum. Fast Cryptographic Primitives Based on the Hardness of Decoding Random Linear Code. Unpublished Manuscript.
• 3: Boaz Barak , Oded Goldreich , Russell Impagliazzo , Steven Rudich , Amit Sahai , Salil P. Vadhan , Ke Yang, On the (Im)possibility of Obfuscating Programs, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.1-18, August 19-23, 2001
• 4: B. Barak, R. Shaltiel, and A. Wigderson. Computational analogues of entropy. In Proc. of 7th Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 2003.
• 5: Mihir Bellare , Chanathip Namprempre, Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.531-545, December 03-07, 2000
• 6: Avrim Blum , Merrick Furst , Michael Kearns , Richard J. Lipton, Cryptographic primitives based on hard learning problems, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.278-291, January 1994, Santa Barbara, California, United States
• 7: Avrim Blum , Adam Kalai , Hal Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.435-440, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335355]
• 8: Xavier Boyen, Reusable cryptographic fuzzy extractors, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030096]
• 9: X. Boyen, Y. Dodis, J. Katz, R. Ostrovsky, A. Smith. Secure Remote Authentication Using Biometric Data. In EUROCRYPT, pp. 147--163, 2005.
• 10: Ran Canetti, Towards Realizing Random Oracles: Hash Functions That Hide All Partial Information, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.455-469, August 17-21, 1997
• 11: R. Canetti, R. R. Dakdouk. Obfuscating Point Functions with Multibit Output. In EUROCRYPT 2008: 489--508.
• 12: R. Canetti, Y. Dodis, S. Halevi, E. Kushilevitz, and A. Sahai. Exposure-Resilient Functions and All-or-Nothing Transforms. In EUROCRYPT 2000: 453--469.
• 13: Ran Canetti , Dror Eiger , Shafi Goldwasser , Dah-Yoh Lim, How to Protect Yourself without Perfect Shredding, Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part II, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70583-3_42]
• 14: Ran Canetti , Daniele Micciancio , Omer Reingold, Perfectly one-way probabilistic hash functions (preliminary version), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.131-140, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276721]
• 15: D. Cash, Y. Z. Ding, Y. Dodis, W. Lee, R. J. Lipton, and S. Walfish. Intrusion--Resilient Key Exchange in the Bounded Retrieval Model. In TCC 2007: 479--498.
• 16: Jean-Sébastien Coron , Marc Joye , David Naccache , Pascal Paillier, Universal Padding Schemes for RSA, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.226-241, August 18-22, 2002
• 17: G. Di Crescenzo, R. Lipton and S. Walfish. Perfectly Secure Password Protocols in the Bounded Retrieval Model. In Theory of Cryptography Conference}, pp. 225--244, 2006.
• 18: Yevgeniy Dodis , Madhu Sudan, Exposure-resilient cryptography, Massachusetts Institute of Technology, 2000
• 19: Yevgeniy Dodis , Yael Tauman Kalai , Shachar Lovett, On cryptography with auxiliary input, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA [doi>10.1145/1536414.1536498]
• 20: Y. Dodis, J. Katz, L. Reyzin, and A. Smith. Robust Fuzzy Extractors and Authenticated Key Agreement from Close Secrets. In CRYPTO 2006: 232--250.
• 21: Yevgeniy Dodis , Rafail Ostrovsky , Leonid Reyzin , Adam Smith, Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data, SIAM Journal on Computing, v.38 n.1, p.97-139, March 2008 [doi>10.1137/060651380]
• 22: Y. Dodis, L. Reyzin, A. Smith. Fuzzy Extractors. In Security with Noisy Data (edited by Pim Tuyls, Boris Skoric, and Tom Kevenaar), Springer, 2007.
• 23: Yevgeniy Dodis , Amit Sahai , Adam Smith, On Perfect and Adaptive Security in Exposure-Resilient Cryptography, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.301-324, May 06-10, 2001
• 24: Yevgeniy Dodis , Adam Smith, Correcting errors without leaking partial information, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060688]
• 25: S. Dziembowski. On Forward-Secure Storage. In CRYPTO 2006: 251--270.
• 26: S. Dziembowski. Intrusion-Resilience Via the Bounded-Storage Model. In TCC 2006: 207--224.
• 27: Stefan Dziembowski , Krzysztof Pietrzak, Intrusion-Resilient Secret Sharing, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.227-237, October 21-23, 2007 [doi>10.1109/FOCS.2007.35]
• 28: Stefan Dziembowski , Krzysztof Pietrzak, Leakage-Resilient Cryptography, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.293-302, October 25-28, 2008 [doi>10.1109/FOCS.2008.56]
• 29: G. Forney. Concatenated Codes. MIT Press, Cambridge, MA, 1966.
• 30: Shafi Goldwasser , Yael Tauman Kalai, On the Impossibility of Obfuscation with Auxiliary Input, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.553-562, October 23-25, 2005 [doi>10.1109/SFCS.2005.60]
• 31: O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
• 32: S. Goldwasser and G. N. Rothblum. On Best-Possible Obfuscation. In TCC 2007: 194--213.
• 33: Stuart Haber , Benny Pinkas, Securely combining public-key cryptosystems, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502013]
• 34: Satoshi Hada, Zero-Knowledge and Code Obfuscation, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.443-457, December 03-07, 2000
• 35: D. Hofheinz, J. Malone-Lee and M. Stam. Obfuscation for Cryptographic Purposes. In TCC 2007: 214--232.
• 36: S. Hohenberger, G. N. Rothblum, A. Shelat, and V. Vaikuntanathan. Securely Obfuscating Re-encryption. In TCC 2007: 233--252.
• 37: Nicholas J. Hopper , Manuel Blum, Secure Human Identification Protocols, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.52-66, December 09-13, 2001
• 38: Chun-Yuan Hsiao , Chi-Jen Lu , Leonid Reyzin, Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility, Proceedings of the 26th annual international conference on Advances in Cryptology, p.169-186, May 20-24, 2007, Barcelona, Spain [doi>10.1007/978-3-540-72540-4_10]
• 39: Y. Ishai, M. Prabhakaran, A. Sahai, and D. Wagner. Private Circuits II: Keeping Secrets in Tamperable Circuits. In EUROCRYPT 2006: 308--327.
• 40: Y. Ishai, A. Sahai, and D. Wagner. Private Circuits: Securing Hardware against Probing Attacks. In CRYPTO 2003: 463--481.
• 41: A. Juels and S. A. Weis. Authenticating Pervasive Devices with Human Protocols. In CRYPTO 2005:293--308.
• 42: J. Katz and J. S. Shin. Parallel and Concurrent Security of the HB and HB+ Protocols. In EUROCRYPT 2006: 73--87.
• 43: B. Lynn, M. Prabhakaran, and A. Sahai. Positive Results and Techniques for Obfuscation. In EUROCRYPT 2004: 20--39.
• 44: S. Micali and L. Reyzin. Physically Observable Cryptography (Extended Abstract). In TCC 2004: 278--296.
• 45: M. Naor. On Cryptographic Assumptions and Challenges. In CRYPTO 2003: 96--109.
• 46: M. Naor , M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.427-437, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100273]
• 47: Noam Nisan , David Zuckerman, More deterministic simulation in logspace, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.235-244, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167162]
• 48: Krzysztof Pietrzak, A Leakage-Resilient Mode of Operation, Proceedings of the 28th Annual International Conference on Advances in Cryptology: the Theory and Applications of Cryptographic Techniques, April 26-30, 2009, Cologne, Germany [doi>10.1007/978-3-642-01001-9_27]
• 49: R. Raz. Private communication.
• 50: Oded Regev, On lattices, learning with errors, random linear codes, and cryptography, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060603]
• 51: Amit Sahai, Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.543, October 17-18, 1999
• 52: Adi Shamir, Identity-based cryptosystems and signature schemes, Proceedings of CRYPTO 84 on Advances in cryptology, p.47-53, August 1985, Santa Barbara, California, United States
• 53: Hoeteck Wee, On obfuscating point functions, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060669]
• 54: D. Zuckerman. Private communication.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Algorithms, Security, Theory

Keywords:
auxiliary information, code obfuscation, encryption schemes, error-correcting codes, learning parity with noise, randomness extractors