How to stretch random functions: The security of protected counter sums

Let f be an unpredictable random function taking (b + c)-bit inputs to b-bi t outputs. This paper presents an unpredictable random function S' taking v ariable-length inputs to b-bit outputs. This construction has several advan tages over chaining, which was proven unpredictable by Bellare, Kilian, and Rogaway, and cascading, which was proven unpredictable by Bellare, Canetti , and Krawczyk. The highlight here is a very simple proof of security.