Factoring integers is arguably the most established problem on which cryptographic primitives are based. This work presents an efficient construction of pseudorandom functions whose security is based on the intractability of factoring. In particular, we are able to construct efficient length-preserving pseudorandom functions where each evaluation requires only a constant number of modular multiplications per output bit. This is substantially more efficient than any previous construction of pseudorandom functions based on factoring, and matches (up to a constant factor) the efficiency of the best known factoring-based pseudorandom bit generators.
Postscript , gzipped Postscript .
Moni Naor, Benny Pinkas and Omer Reingold, Distributed Pseudo-Random Functions and KDC. Eurocrypt'99. Abstract, Postscript , gzipped Postscript . Moni Naor and Omer Reingold, Synthesizers and their application to the parallel construction of pseudo-random functions. J. of Computer and Systems Sciences, vol. 58 (2), April 1999, pp. 336-375. Abstract, Postscript , gzipped Postscript. Moni Naor and Omer Reingold, From Unpredictability to Indistinguishability: A Simple Construction of Pseudo-Random Functions from MACs, Crypto'98. Abstract, Postscript, gzipped Postscript . Moni Naor, Omer Reingold, Number-Theoretic Constructions of Efficient Pseudo-Random Functions, J. of the ACM, 2004, Abstract, Postscript, gzipped Postscript