Performance improvement for the GGM-construction of pseudorandom functions

摘要

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 variant of the GGM-construction and compare its performance with the original construction. We show that a 4-ary-tree variant construction can achieve the best performance under the assumption that the underlying pseudorandom generators generate pseudorandom bits sequentially.