Non-malleable extractors and symmetric key cryptography from weak secrets

ABSTRACT

We study the question of basing symmetric key cryptography on weak secrets. In this setting, Alice and Bob share an n-bit secret W, which might not be uniformly random, but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Since standard symmetric-key primitives require uniformly random secret keys, we would like to construct an authenticated key agreement protocol in which Alice and Bob use W to agree on a nearly uniform key R, by communicating over a public channel controlled by an active adversary Eve. We study this question in the information theoretic setting where the attacker is computationally unbounded. We show that single-round (i.e. one message) protocols do not work when k ≤ n/2, and require poor parameters even when n/2

On the other hand, for arbitrary values of k, we design a communication efficient two-round (challenge-response) protocol extracting nearly k random bits. This dramatically improves the previous construction of Renner and Wolf [32], which requires Θ(λ + log(n)) rounds where λ is the security parameter. Our solution takes a new approach by studying and constructing "non-malleable" seeded randomness extractors -- if an attacker sees a random seed X and comes up with an arbitrarily related seed X', then we bound the relationship between R= Ext(W;X) and R' = Ext(W;X').

We also extend our two-round key agreement protocol to the "fuzzy" setting, where Alice and Bob share "close" (but not equal) secrets W_A and W_B, and to the Bounded Retrieval Model (BRM) where the size of the secret W is huge.

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: M. Bellare, D. Pointcheval, and P. Rogaway. Authenticated key exchange secure against dictionary attacks. In EUROCRYPT, pages 139--155, 2000.
• 3: C. H. Bennett and G. Brassard. Quantum cryptography: public key distribution and coin tossing. Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing, pages 175--179, 1984.
• 4: C. H. Bennett, G. Brassard, C. Crepeau, and U. M. Maurer. Generalized privacy amplification. IEEE Transactions on Information Theory, 41(6):1915--1923, 1995.
• 5: Charles H. Bennett , Gilles Brassard , Jean-Marc Robert, Privacy amplification by public discussion, SIAM Journal on Computing, v.17 n.2, p.210-229, April 1988 [doi>10.1137/0217014]
• 6: C. Bosley and Y. Dodis. Does privacy require true randomness? In TCC, pages 1{20, 2007.
• 7: V. Boyko, P. D. MacKenzie, and S. Patel. Provably secure password-authenticated key exchange using diffie-hellman. In EUROCRYPT, pages 156--171, 2000.
• 8: R. Canetti, S. Halevi, J. Katz, Y. Lindell, and P. D. MacKenzie. Universally composable password-based key exchange. In EUROCRYPT, pages 404--421, 2005.
• 9: 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, pages 479--498, 2007.
• 10: R. Cramer, Y. Dodis, S. Fehr, C. Padro, and D. Wichs. Detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors. In EUROCRYPT, pages 471--488, 2008.
• 11: G. D. Crescenzo, R. J. Lipton, and S. Walfish. Perfectly secure password protocols in the bounded retrieval model. In TCC, pages 225--244, 2006.
• 12: Y. Dodis, J. Katz, L. Reyzin, and A. Smith. Robust fuzzy extractors and authenticated key agreement from close secrets. In CRYPTO, pages 232--250, 2006.
• 13: Yevgeniy Dodis , Shien Jin Ong , Manoj Prabhakaran , Amit Sahai, On the (Im)possibility of Cryptography with Imperfect Randomness, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.196-205, October 17-19, 2004 [doi>10.1109/FOCS.2004.44]
• 14: 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]
• 15: Y. Dodis, L. Reyzin, and A. Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. In EUROCRYPT, pages 523--540, 2004.
• 16: Yevgeniy Dodis , Joel Spencer, On the (non)Universality of the One-Time Pad, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.376, November 16-19, 2002
• 17: S. Dziembowski. Intrusion-resilience via the bounded-storage model. In TCC, pages 207--224, 2006.
• 18: 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]
• 19: 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]
• 20: Rosario Gennaro , Yehuda Lindell, A framework for password-based authenticated key exchange¹, ACM Transactions on Information and System Security (TISSEC), v.9 n.2, p.181-234, May 2006 [doi>10.1145/1151414.1151418]
• 21: Oded Goldreich , Yehuda Lindell, Session-Key Generation Using Human Passwords Only, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.408-432, August 19-23, 2001
• 22: Venkatesan Guruswami , Christopher Umans , Salil Vadhan, Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.96-108, June 13-March 16, 2007 [doi>10.1109/CCC.2007.38]
• 23: Bhavana Kanukurthi , Leonid Reyzin, An Improved Robust Fuzzy Extractor, Proceedings of the 6th international conference on Security and Cryptography for Networks, September 10-12, 2008, Amalfi, Italy [doi>10.1007/978-3-540-85855-3_11]
• 24: B. Kanukurthi and L. Reyzin. Key agreement from close secrets over unsecured channels. In EUROCRYPT, 2009. To Appear. Full version at http://eprint.iacr.org/2008/494.
• 25: Jonathan Katz , Rafail Ostrovsky , Moti Yung, Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.475-494, May 06-10, 2001
• 26: Ueli M. Maurer, Protocols for Secret Key Agreement by Public Discussion Based on Common Information, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.461-470, August 16-20, 1992
• 27: Ueli M. Maurer , Stefan Wolf, Privacy Amplification Secure Against Active Adversaries, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.307-321, August 17-21, 1997
• 28: U. M. Maurer and S. Wolf. Secret-key agreement over unauthenticated public channels iii: Privacy amplification. IEEE Transactions on Information Theory, 49(4):839--851, 2003.
• 29: James L. McInnes , Benny Pinkas, On the Impossibility of Private Key Cryptography with Weakly Random Keys, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.421-435, August 11-15, 1990
• 30: S. Micali and L. Reyzin. Physically observable cryptography (extended abstract). In TCC, pages 278--296, 2004.
• 31: Noam Nisan , David Zuckerman, Randomness is linear in space, Journal of Computer and System Sciences, v.52 n.1, p.43-52, Feb. 1996 [doi>10.1006/jcss.1996.0004]
• 32: R. Renner and S. Wolf. Unconditional authenticity and privacy from an arbitrarily weak secret. In CRYPTO, pages 78--95, 2003.
• 33: R. Renner and S. Wolf. The exact price for unconditionally secure asymmetric cryptography. In EUROCRYPT, pages 109--125, 2004.
• 34: Salil P. Vadhan, Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model, Journal of Cryptology, v.17 n.1, p.43-77, January 2004 [doi>10.1007/s00145-003-0237-x]
• 35: A. Wyner. The wire-tap channel. Bell Systems Technical Journal, 54(8):1355--1387, 1975.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

General Terms:
Algorithms, Security, Theory

Keywords:
authenticated key agreement, authentication, bounded retrieval model, encryption, information reconcilliation, information theoretic security, privacy amplification, randomness extractors