Pseudorandom functions and factoring
The computational hardness of factoring integers is the most established assumption on which cryptographic primitives are based. This work presents an efficient construction of pseudo-random functions whose security is based on the intractability of factoring. In particular, we are able to construct efficient length-preserving pseudo random 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 pseudo random functions based on factoring and matches ( up to a constant factor) the efficiency of the best-known factoring-based pseudo-random bit generators.
pseudorandomness pseudorandom functions cryptography computational number theory integer factorization