Pseudorandom Functions and Factoring
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).
- Pseudo-random functions and factoring (extended abstract)
- Number-theoretic constructions of efficient pseudo-random functions
- An improved pseudorandom generator based on hardness of factoring
- On the security of modular exponentiation with application to the construction of pseudorandom generators
- scientific article; zbMATH DE number 3928174
- On the security of modular exponentiation with application to the construction of pseudorandom generators
- Practical chosen ciphertext secure encryption from factoring
- Adaptively secure constrained pseudorandom functions in the standard model
- Generically speeding-up repeated squaring is equivalent to factoring: sharp thresholds for all generic-ring delay functions
- Building a pseudorandom function using a Naor-Reingold type construction
- Number-theoretic constructions of efficient pseudo-random functions
- Pseudo-random functions and factoring (extended abstract)
- A Twist on the Naor-Yung Paradigm and Its Application to Efficient CCA-Secure Encryption from Hard Search Problems
- Practical Chosen Ciphertext Secure Encryption from Factoring
- On optimal cryptographic key derivation
- An improved pseudorandom generator based on hardness of factoring
- scientific article; zbMATH DE number 2119690 (Why is no real title available?)
- Small bias requires large formulas
- Pseudorandom functions: three decades later
- The communication complexity of addition
- Pseudorandom properties of prime factors
- Cryptography and Coding
- When simple permutations mix poorly. Limited independence does not imply pseudorandomness
- Adaptively secure constrained pseudorandom functions in the standard model
- Performance improvement for the GGM-construction of pseudorandom functions
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)