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
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
0.9116780757904052
0 references
0.8355497121810913
0 references
0.8165040612220764
0 references
0.8165040612220764
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