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
    0 references
    0 references
    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

    Identifiers