Number-theoretic constructions of efficient pseudo-random functions
- 1 March 2004
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 51 (2), 231-262
- https://doi.org/10.1145/972639.972643
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 0 (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 ≠ f s ( x )" given a commitment to a key s of a pseudo-random function f s .Keywords
This publication has 33 references indexed in Scilit:
- Synthesizers and Their Application to the Parallel Construction of Pseudo-Random FunctionsJournal of Computer and System Sciences, 1999
- Natural ProofsJournal of Computer and System Sciences, 1997
- Software protection and simulation on oblivious RAMsJournal of the ACM, 1996
- When Won′t Membership Queries Help?Journal of Computer and System Sciences, 1995
- Checking the correctness of memoriesAlgorithmica, 1994
- Constant depth circuits, Fourier transform, and learnabilityJournal of the ACM, 1993
- Depth efficient neural networks for division and related problemsIEEE Transactions on Information Theory, 1993
- A theory of the learnableCommunications of the ACM, 1984
- Probabilistic encryptionJournal of Computer and System Sciences, 1984
- New directions in cryptographyIEEE Transactions on Information Theory, 1976