Number-theoretic constructions of efficient pseudo-random functions

ABSTRACT

We describe efficient constructions for various cryptographic primitives in private-key as well as public-key cryptography. Our main results are two new constructions of pseudo-random functions. We prove the pseudo-randomness of one construction under the assumption that factoring (Blum integers) is hard while the other construction is pseudo-random if the decisional version of the Diffie--Hellman assumption holds. Computing the value of our functions at any given point involves two subset products. This is much more efficient than previous proposals. Furthermore, these functions have the advantage of being in TC⁰ (the class of functions computable by constant depth circuits consisting of a polynomial number of threshold gates). This fact has several interesting applications. The simple algebraic structure of the functions implies additional features such as a zero-knowledge proof for statements of the form "y = f_s(x)" and "y &neq; f_s(x)" given a commitment to a key s of a pseudo-random function f_s.

REFERENCES

• 1: Dana Angluin , Michael Kharitonov, When won't membership queries help?, Journal of Computer and System Sciences, v.50 n.2, p.336-355, April 1995
• 2: Paul W Beame , Stephen A Cook , H James Hoover, Log depth circuits for division and related problems, SIAM Journal on Computing, v.15 n.4, p.994-1003, Nov. 1986 [doi>10.1137/0215070]
• 3: Mihir Bellare , Shafi Goldwasser, New paradigms for digital signatures and message authentication based on non-interactive zero knowledge proofs, Proceedings on Advances in cryptology, p.194-211, July 1989, Santa Barbara, California, United States
• 4: Mihir Bellare , Silvio Micali, Non-Interactive Oblivious Transfer and Spplications, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.547-557, August 20-24, 1989
• 5: Biham, E. Boneh, D., and Reingold, O. 1997. Breaking generalized Diffie--Hellman modulo a composite is no easier than Factoring. Theory of Cryptography Library, Record 97-14 at: http://theory. lcs.mit.edu/ tcryptol/homepage.html
• 6: L Blum , M Blum , M Shub, A simple unpredictable pseudo random number generator, SIAM Journal on Computing, v.15 n.2, p.364-383, May 1986 [doi>10.1137/0215025]
• 7: Blum, M., Evans, W., Gemmell, P., Kannan, S., and Naor, M. 1994. Checking the correctness of memories. Algorithmica, 225--244.
• 8: Manuel Blum , Shafi Goldwasser, An efficient probabilistic public key encryption scheme which hides all partial information, Proceedings of CRYPTO 84 on Advances in cryptology, p.289-302, August 1985, Santa Barbara, California, United States
• 9: Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
• 10: Dan Boneh, The Decision Diffie-Hellman Problem, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.48-63, June 21-25, 1998
• 11: Dan Boneh , Richard J. Lipton, Algorithms for Black-Box Fields and their Application to Cryptography (Extended Abstract), Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.283-297, August 18-22, 1996
• 12: Dan Boneh , Ramarathnam Venkatesan, Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.129-142, August 18-22, 1996
• 13: Stefan A. Brands, An Efficient Off-line Electronic Cash System Based On The Representation Problem., CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1993
• 14: Gilles Brassard, Modern cryptology, Springer-Verlag New York, Inc., New York, NY, 1988
• 15: Brickell, E. F., Gordon, D. M., McCurley, K. S., and Wilson, D. B. 1992. Fast exponentiation with precomputation. In Proceedings of Advances in Cryptology---EUROCRYPT '92. Lecture Notes in Computer Science, Springer-Verlag, New York, 200--207.
• 16: 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
• 17: Canetti, R., Friedlander, J., and Shparlinski, I. 1997. On certain exponential sums and the distribution of Diffie--Hellman triples. Research report, IBM T. J. Watson Research Center, Number RC 20915 (92645), July.
• 18: David Chaum , Hans Van Antwerpen, Undeniable Signatures, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.212-216, August 20-24, 1989
• 19: Benny Chor , Amos Fiat , Moni Naor, Tracing Traitors, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.257-270, August 21-25, 1994
• 20: 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
• 21: Alfredo De Santis , Yvo Desmedt , Yair Frankel , Moti Yung, How to share a function securely, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.522-533, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195405]
• 22: Diffie, W., and Hellman, M. 1976. New directions in cryptography. IEEE Trans. Inform. Theory 22, 6, 644--654.
• 23: Taher El Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms, Proceedings of CRYPTO 84 on Advances in cryptology, p.10-18, August 1985, Santa Barbara, California, United States
• 24: Franklin, M., and Haber, S. 1996. Joint encryption and message-efficient secure computation. J. Cryptology 9, 4, 217--232.
• 25: Gertner, Y., and Malkin, T. 1997. A PSRG based on the decision Diffie--Hellman assumption, preprint.
• 26: Oded Goldreich, Two remarks concerning the Goldwasser-Micali-Rivest signature scheme, Proceedings on Advances in cryptology---CRYPTO '86, p.104-110, January 1987, Santa Barbara, California, United States
• 27: Goldreich, O. 1995. Foundations of Cryptography (fragments of a book). Electronic publication: http://www.eccc.uni-trier.de/eccc/info/ECCC-Books/eccc-books.html (Electronic Colloquium on Computational Complexity).
• 28: Goldreich, O. 1998. Modern cryptography, probabilistic proofs and pseudo-randomness. Algorithms Combin. 17.
• 29: Oded Goldreich , Shafi Goldwasser , Silvio Micali, On the cryptographic applications of random functions, Proceedings of CRYPTO 84 on Advances in cryptology, p.276-288, August 1985, Santa Barbara, California, United States
• 30: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 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: Goldwasser, S., and Micali, S. 1984. Probabilistic encryption. J. Comput. Syst. Sci. 28, 2, 270--299.
• 33: Oded Goldreich , Rafail Ostrovsky, Software protection and simulation on oblivious RAMs, Journal of the ACM (JACM), v.43 n.3, p.431-473, May 1996 [doi>10.1145/233551.233553]
• 34: Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
• 35: Impagliazzo, R., and Naor, M. 1996. Efficient cryptographic schemes provably secure as subset sum. J. Crypt. 9, 199--216.
• 36: Impagliazzo, R., and Zuckerman, D. 1989. Recycling random bits. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 248--253.
• 37: Joux, A., and Nguyen, K. 2001. Separating decision Diffie--Hellman from Diffie--Hellman in cryptographic groups, Cryptology ePrint Archive, Report 2001/003, 2001. http://eprint.iacr.org.
• 38: Michael Kearns , Leslie Valiant, Cryptographic limitations on learning Boolean formulae and finite automata, Journal of the ACM (JACM), v.41 n.1, p.67-95, Jan. 1994 [doi>10.1145/174644.174647]
• 39: Michael Kharitonov, Cryptographic hardness of distribution-specific learning, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.372-381, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167197]
• 40: Matthias Krause , Stefan Lucks, On the Minimal Hardware Complexity of Pseudorandom Function Generators, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, p.419-430, February 15-17, 2001
• 41: Langberg, M. 1998. An implementation of efficient pseudo-random functions. At: http://www.wisdom.weizmann.ac.il/∼naor/p_r_func/abs/abs.html.
• 42: Nathan Linial , Yishay Mansour , Noam Nisan, Constant depth circuits, Fourier transform, and learnability, Journal of the ACM (JACM), v.40 n.3, p.607-620, July 1993 [doi>10.1145/174130.174138]
• 43: Michael George Luby , Luby Michael, Pseudorandomness and Cryptographic Applications, Princeton University Press, Princeton, NJ, 1994
• 44: Michael Luby , Charles Rackoff, How to construct pseudorandom permutations from pseudorandom functions, SIAM Journal on Computing, v.17 n.2, p.373-386, April 1988 [doi>10.1137/0217022]
• 45: Ueli M. Maurer , Stefan Wolf, The Relationship Between Breaking the Diffie--Hellman Protocol and Computing Discrete Logarithms, SIAM Journal on Computing, v.28 n.5, p.1689-1721, April/May 1999 [doi>10.1137/S0097539796302749]
• 46: K. S. McCurley, A key distribution system equivalent to factoring, Journal of Cryptology, v.1 n.2, p.95-105, Aug. 1988 [doi>10.1007/BF02351718]
• 47: McCurley, K. 1990. The discrete logarithm problem. In Cryptography and Computational Number Theory, Proceedings of the Symposium on Applied Mathematics. AMS Lecture Notes, vol. 42, 49--74.
• 48: Naor, M., and Pinkas, B. 1998. Secure and efficient metering. In Proceedings of Advances in Cryptology---EUROCRYPT '98. Lecture Notes in Computer Science, vol. 1462. Springer-Verlag, New York.
• 49: Moni Naor , Benny Pinkas, Oblivious Transfer with Adaptive Queries, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.573-590, August 15-19, 1999
• 50: Naor, M., Pinkas, B., and Reingold, O. 1999. Distributed pseudo-random functions and KDCs. In Proceedings of Advances in Cryptology---Eurocrypt '99. Lecture Notes in Computer Science, vol. 1592. Springer-Verlag, New York, 327--346.
• 51: M. Naor , O. Reingold, Number-theoretic constructions of efficient pseudo-random functions, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.458, October 19-22, 1997
• 52: Moni Naor , Omer Reingold, On the construction of pseudo-random permutations: Luby-Rackoff revisited (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.189-199, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258581]
• 53: 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]
• 54: Moni Naor , Omer Reingold , Alon Rosen, Pseudo-random functions and factoring (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.11-20, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335307]
• 55: Odlyzko, A. M. 1993. Discrete logarithms and smooth polynomials. Contemp. Math.
• 56: Alexander A. Razborov , Steven Rudich, Natural proofs, Journal of Computer and System Sciences, v.55 n.1, p.24-35, Aug. 1997 [doi>10.1006/jcss.1997.1494]
• 57: Reif, J. 1987. On threshold circuits and polynomial computation. In Proceedings of the 2nd Conference on Structure in Complexity Theory. 118--123.
• 58: John H. Reif , Stephen R. Tate, On threshold circuits and polynomial computation, SIAM Journal on Computing, v.21 n.5, p.896-908, Oct. 1992 [doi>10.1137/0221053]
• 59: Shmuely, Z. 1985. Composite Diffie--Hellman public-key generating systems are hard to break, Tech. Rep. No. 356, Computer Science Dept., Technion, Technion City, Israel.
• 60: Shoup, V. 1997. Lower bounds for discrete logarithms and related problems. In Proceedings of Advances in Cryptology---EUROCRYPT '97. Lecture Notes in Computer Science, vol. 1233. Springer-Verlag, New York, 256--266.
• 61: Siu, K.-Y., Bruck, J., Kailath, T., and Hofmeister, T. 1993. Depth efficient neural network for division and related problems. IEEE Trans. Inform. Theory 39, 946--956.
• 62: Kai-Yeung Siu , Vwani P. Roychowdhury, On Optimal Depth Threshold Circuits for Multiplication andRelated Problems, SIAM Journal on Discrete Mathematics, v.7 n.2, p.284-292, May 1994 [doi>10.1137/S0895480192228619]
• 63: Stadler, M. 1996. Publicly verifiable secret sharing. In Proceedings of Advances in Cryptology---EUROCRYPT '96, Lecture Notes in Computer Science, vol. 1070. Springer-Verlag, New York, 190--199.
• 64: Michael Steiner , Gene Tsudik , Michael Waidner, Diffie-Hellman key distribution extended to group communication, Proceedings of the 3rd ACM conference on Computer and communications security, p.31-37, March 14-15, 1996, New Delhi, India [doi>10.1145/238168.238182]
• 65: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• 66: Yao, A. C. 1982. Theory and applications of trapdoor functions. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science. ACM, New York, 80--91.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
  G.4 MATHEMATICAL SOFTWARE

General Terms:
Algorithms, Security, Theory

Keywords:
Pseudo-random functions, constant-depth threshold circuits, decision Diffie--Hellman, factoring, learning theory, natural proofs