Performance Improvement for the GGM-Construction of Pseudorandom Functions

Abstract

A pseudorandom function is a function that cannot be efficiently distinguished from a truly random function. The first construction of pseudorandom functions was introduced by Goldreich, Goldwasser, and Micali (GGM-construction). In this paper, we propose a simple variant of the GGM-construction that works slightly faster than the original one. Interestingly, we show that our construction is optimal under the assumption that the cost of generating l pseudorandom bits is θ (l).