The computational hardness of factoring integers is the most established
assumption 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 (small) 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.