Lossy trapdoor functions and their applications

ABSTRACT

We propose a new general primitive called lossy trapdoor functions (lossy TDFs), and realize it under a variety of different number theoretic assumptions, including hardness of the decisional Diffie-Hellman (DDH) problem and the worst-case hardness of lattice problems.

Using lossy TDFs, we develop a new approach for constructing several important cryptographic primitives, including (injective) trapdoor functions, collision-resistant hash functions, oblivious transfer, and chosen ciphertext-secure cryptosystems. All of the constructions are simple, efficient, and black-box.

These results resolve some long-standing open problems in cryptography. They give the first known injective trapdoor functions based on problems not directly related to integer factorization, and provide the first known CCA-secure cryptosystem based solely on the worst-case complexity of lattice problems.

REFERENCES

• 1: Miklós Ajtai , Cynthia Dwork, A public-key cryptosystem with worst-case/average-case equivalence, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.284-293, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258604]
• 2: Mihir Bellare, Alexandra Boldyreva, K. Kurosawa, and Jessica Staddon. Multirecipient encryption schemes: How to save on bandwidth and computation without sacrificing security. IEEE Transactions on Information Theory, 53(11):3927-3943, 2007.
• 3: Mihir Bellare , Shai Halevi , Amit Sahai , Salil P. Vadhan, Many-to-One Trapdoor Functions and Their Ralation to Public-Key Cryptosystems, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.283-298, August 23-27, 1998
• 4: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 5: Avrim Blum , Adam Kalai , Hal Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model, Journal of the ACM (JACM), v.50 n.4, p.506-519, July 2003 [doi>10.1145/792538.792543]
• 6: Manuel Blum , Paul Feldman , Silvio Micali, Non-interactive zero-knowledge and its applications, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.103-112, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62222]
• 7: Dan Boneh, The Decision Diffie-Hellman Problem, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.48-63, June 21-25, 1998
• 8: Dan Boneh , Ran Canetti , Shai Halevi , Jonathan Katz, Chosen-Ciphertext Security from Identity-Based Encryption, SIAM Journal on Computing, v.36 n.5, p.1301-1328, December 2006 [doi>10.1137/S009753970544713X]
• 9: Dan Boneh and Jonathan Katz. Improved efficiency for CCA-secure cryptosystems built using identity-based encryption. In CT-RSA, pages 87-103, 2005.
• 10: Xavier Boyen , Qixiang Mei , Brent Waters, Direct chosen ciphertext security from identity-based techniques, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102162]
• 11: Ran Canetti, Shai Halevi, and Jonathan Katz. Chosen-ciphertext security from identity-based encryption. In EUROCRYPT, pages 207-222, 2004.
• 12: Ronald Cramer , Victor Shoup, A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.13-25, August 23-27, 1998
• 13: Ronald Cramer , Victor Shoup, Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.45-64, May 02, 2002
• 14: Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, IT-22(6):644-654, 1976.
• 15: Yevgeniy Dodis, Leonid Reyzin, and Adam Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. In EUROCRYPT, pages 523-540, 2004.
• 16: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 17: Edith Elkind and Amit Sahai. A unified methodology for constructing public-key encryption schemes secure against adaptive chosen-ciphertext attack. Cryptology ePrint Archive, Report 2002/042, 2002. http://eprint.iacr.org/.
• 18: Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
• 19: Eiichiro Fujisaki , Tatsuaki Okamoto, Secure Integration of Asymmetric and Symmetric Encryption Schemes, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.537-554, August 15-19, 1999
• 20: Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC, 2008. To appear. Full version available at http://eprint.iacr.org/2007/432.
• 21: Yael Gertner, Tal Malkin, and Steven Myers. Towards a separation of semantic and CCA security for public key encryption. In TCC, pages 434-455, 2007.
• 22: Y. Gertner , T. Malkin , O. Reingold, On the Impossibility of Basing Trapdoor Functions on Trapdoor Predicates, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.126, October 14-17, 2001
• 23: 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]
• 24: Oded Goldreich , Silvio Micali , Avi Wigderson, How to prove all NP-statements in zero-knowledge, and a methodology of cryptographic protocol design, Proceedings on Advances in cryptology---CRYPTO '86, p.171-185, January 1987, Santa Barbara, California, United States
• 25: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 26: Iftach Haitner. Semi-honest to malicious oblivious transfer - the black-box way. In TCC, pages 412-426, 2008.
• 27: R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73009]
• 28: Akinori Kawachi, Keisuke Tanaka, and Keita Xagawa. Multi-bit cryptosystems based on lattice problems. In PKC, pages 315-329, 2007.
• 29: Moni Naor , Omer Reingold, Synthesizers and their application to the parallel construction of pseudo-random functions, Journal of Computer and System Sciences, v.58 n.2, p.336-375, April 1999 [doi>10.1006/jcss.1998.1618]
• 30: 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]
• 31: Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT, pages 223-238, 1999.
• 32: Chris Peikert, Limits on the Hardness of Lattice Problems in \ell _p Norms, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.333-346, June 13-March 16, 2007 [doi>10.1109/CCC.2007.12]
• 33: Chris Peikert and Brent Waters. Lossy trapdoor functions and their applications. Cryptology ePrint Archive, Report 2007/279, 2007. Full version available at http://eprint.iacr.org/2007/279.
• 34: M. O. Rabin, DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 35: Charles Rackoff , Daniel R. Simon, Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.433-444, August 11-15, 1991
• 36: Oded Regev, New lattice-based cryptographic constructions, Journal of the ACM (JACM), v.51 n.6, p.899-942, November 2004 [doi>10.1145/1039488.1039490]
• 37: 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]
• 38: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 39: 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
• 40: 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

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Security, Theory

Keywords:
public key encryption, trapdoor functions