Pseudorandom Functions and Factoring

From MaRDI portal





The object of the paper is the efficient construction of a family of pseudorandom functions whose security is based on the computational intractability of the problem of factoring integer numbers. A distribution of functions is pseudorandom if it cannot be efficiently distinguished from uniform distribution. Pseudorandom functions were originally defined by \textit{O. Goldreich}, \textit{S. Goldwasser} and \textit{S. Micali} [J. Assoc. Comput. Mech. 33, 792-807 (1986); see also Theory of algorithms, Colloq. Pécs/Hung. 1984, Colloq. Math. Soc. János Bolyai 44, 161-189 (1986; Zbl 0596.65002)]. The first two authors of the present paper gave an efficient method (cited as the NR method) to build pseudorandom functions based on factoring [Proc. 38th IEEE Symp. Foundations Comput. Sc. Miami Beach, FL, 458-467 (1997)]. Such a method however has a single bit like output. In this article the authors improve the NR method to obtain length-preserving pseudorandom functions. For doing so they combine the NR method with the very well-known Blum-Blum-Shub pseudorandom bit generators [\textit{L. Blum}, \textit{M. Blum} and \textit{M. Shub}, SIAM J. Comput. 15, 364-383 (1986; Zbl 0602.65002)]. The BBS generator takes the least significant bit of \(x^2\text{ mod }n\), where \(n\) is a product of two primes \(p\), \(q\), each congruent to 3 modulo 4. However, for convenience, the authors substitute in their construction the least significant bit for the so-called Goldreich-Levin predicate \(\text{Br}(.)\). After some introductory sections, the authors give their construction in Section 4, while the long Section 5 is dedicated to the proof of the authors' claim that the functions built are at least as secure as factoring the Blum integers. Section 6 shows how to adapt the given construction when \(\text{Br}(.)\) is replaced for the least significant bit originally used in the BBS construction. Finally, further research is suggested that would complete the results of the paper, and the authors compare their construction with the NR construction (pointing out that the least one possesses some good additional features lacking in the present construction).











This page was built for publication: Pseudorandom Functions and Factoring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3149873)