Performance improvement for the GGM-construction of pseudorandom functions (Q864800)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Performance improvement for the GGM-construction of pseudorandom functions |
scientific article |
Statements
Performance improvement for the GGM-construction of pseudorandom functions (English)
0 references
13 February 2007
0 references
A pseudorandom function (PRF) is a function that cannot be efficiently distinguished from a truly random function. More precisely, a PRF has the property that its input-output behaviour is computationally indistinguishable from that of a random function, and evaluating such a function can be implemented by an efficient algorithm. \textit{O. Goldreich, S. Goldwasser} and \textit{S. Micali} [Colloq. Math. Soc. János Bolyai 44, 161--189 (1986; Zbl 0596.65002)] proposed an elegant construction of length-preserving PRFs using pseudorandom bit generators (PRBGs) as the building blocks. The advantage of the PRF construction given by Goldreich, Goldwasser and Micali (abbreviated henceforth GGM-construction) is that a PRF can be built using any PRBGs. The aim of this paper is to propose a simple variant of the GGM-construction and to show that it can work faster in average. The authors compare the performance of the newly introduced GGM-construction with the original one, and prove that a 4-ary tree variant of the GGM-construction can achieve the best performance under the assumption that the underlying PRBGs generate pseudorandom bits sequentially. PRFs have many important cryptographic applications. For examples, two parties can share a random-looking function by merely sharing a common secret key. A scheme may be designed which allows the users to have black-box access to a random function and prove its security. The random function is shown to be replaceable with a PRF, the scheme security being still preserved.
0 references
pseudo-random function
0 references
pseudo-random bit generator
0 references
pseudo-randomness
0 references
Goldreich-Goldwasser-Micali construction
0 references
probabilistic polynomial-time algorithm
0 references
cryptography
0 references
0 references