##
Stateless evaluation of pseudorandom functions: Security beyond the
birthday barrier

** Authors: M. Bellare, O. Goldreich and H. Krawczyk
**
** Abstract: ** Many cryptographic solutions based on pseudorandom functions
(for common problems like encryption, message-authentication or
challenge-response protocols) have the following feature: There is a stateful
(counter based) version of the scheme that has high security, but if, to avoid
the use of state, we substitute a random value for the counter, the security of
the scheme drops below the birthday bound. In some situations the use of
counters or other forms of state is impractical or unsafe. Can we get security
beyond the birthday bound without using counters?

This paper presents a paradigm for strengthening pseudorandom function usages
to this end, the idea of which is roughly to use the XOR of the values of a
pseudorandom function on a small number of distinct random points in place of
its value on a single point. We establish two general security properties of
our construction, ``pseudorandomness'' and ``integrity'', with security beyond
the birthday bound. These can be applied to derive encryption schemes, and MAC
schemes (based on universal hash functions), that have security well beyond the
birthday bound, without the use of state and at moderate computational cost.

** Ref:** Extended abstract in Advances in Cryptology - Crypto 99
Proceedings, Lecture Notes in Computer Science Vol. 1666, M. Wiener ed,
Springer-Verlag, 1999. Full paper available below.

** Full paper: ** Available as compressed
postscript, postscript, or
pdf. ( Help if this doesn't work).