Pseudorandom Functions and Factoring (Q3149873)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1808481
Language Label Description Also known as
default for all languages
No label defined
    English
    Pseudorandom Functions and Factoring
    scientific article; zbMATH DE number 1808481

      Statements

      Pseudorandom Functions and Factoring (English)
      0 references
      0 references
      0 references
      0 references
      29 September 2002
      0 references
      cryptography
      0 references
      pseudorandomness
      0 references
      pseudorandom functions
      0 references
      computational number theory
      0 references
      integer factorization
      0 references
      Blum-Blum-Shub generator
      0 references
      factoring
      0 references
      NR method
      0 references
      BBS generator
      0 references
      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).
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references