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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
W. Aiello, and R. Venkatesan. Foiling birthday attacks in length-doubling transformations. Advances in Cryptology-Eurocrypt 96 Proceedings, Lecture Notes in Computer Science Vol. 1070, U. Maurer ed., Springer-Verlag, 1996.
M. Bellare, A. Desai, E. Jokipii and P. Rogaway. A concrete security treatment of symmetric encryption: Analysis of the DES modes of operation. Proceedings of the 38th Symposium on Foundations of Computer Science, IEEE, 1997.
M. Bellare, O. Goldreich and h. Krawczyk. Beyond the birthday barrier, without counters. Full version of this paper, available via http://www-cse. ucsd.edu/users/mihir.
M. Bellare, R. GuÉrin and P. Rogaway. XOR MACs: New Methods for Message Authentication using Finite Pseudorandom Functions. Full version available via http://www-cse.ucsd.edu/users/mihir. Preliminary version in Advances in Cryptology-Crypto 95 Proceedings, Lecture Notes in Computer Science Vol. 963, D. Coppersmith ed., Springer-Verlag, 1995.
M. Bellare, J. Kilian and P. Rogaway. The Security of Cipher Block Chaining. Advances in Cryptology-Crypto 94 Proceedings, Lecture Notes in Computer Science Vol. 839, Y. Desmedt ed., Springer-Verlag, 1994.
M. Bellare, T. Krovetz and P. Rogaway. Luby-Rackoff backwards: Increasing security by making block ciphers non-invertible. Advances in Cryptology-Eurocrypt 97 Proceedings, Lecture Notes in Computer Science Vol. 1233, W. Fumy ed., Springer-Verlag, 1997.
O. Goldreich, S. Goldwasser and S. Micali. How to construct random functions. Journal of the ACM, Vol. 33, No. 4, 1986, pp. 210–217.
C. Hall, D. Wagner, J. Kelsey and B. Schneier. Building PRFs from PRPs. Advances in Cryptology-Crypto 98 Proceedings, Lecture Notes in Computer Science Vol. 1462, H. Krawczyk ed., Springer-Verlag, 1998.
H. Krawczyk. LFSR-based Hashing and Authentication. Advances in Cryptology-Crypto 94 Proceedings, Lecture Notes in Computer Science Vol. 839, Y. Desmedt ed., Springer-Verlag, 1994.
M. Luby and C. Rackoff. How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Computing, Vol. 17, No. 2, April 1988.
M. Naor and O. Reingold. On the construction of pseudorandom permutations: Luby-Rackoff revisited. J. of Cryptology Vol. 12, No. 1, 1999, pp. 29–66.
J. Patarin. Improved security bounds for pseudorandom permutations. Proceedings of the Fourth Annual Conference on Computer and Communications Security, ACM, 1997.
J. Patarin. About Feistel schemes with six (or more) rounds. Proceedings of the 5th Fast Software Encryption Workshop, Lecture Notes in Computer Science Vol. 1372, Springer-Verlag, 1998.
B. Preneel and P. van Oorschott. MDx-MAC and building fast MACs from hash functions. Advances in Cryptology-Crypto 95 Proceedings, Lecture Notes in Computer Science Vol. 963, D. Coppersmith ed., Springer-Verlag, 1995.
V. Shoup. On Fast and Provably Secure Message Authentication Based on Universal Hashing. Advances in Cryptology-Crypto 96 Proceedings, Lecture Notes in Computer Science Vol. 1109, N. Koblitz ed., Springer-Verlag, 1996.
M. Wegman and L. Carter. New hash functions and their use in authentication and set equality. J. of Computer and System Sciences, vol. 22, 1981, pp. 265–279.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bellare, M., Goldreich, O., Krawczyk, H. (1999). Stateless Evaluation of Pseudorandom Functions: Security Beyond the Birthday Barrier. In: Wiener, M. (eds) Advances in Cryptology — CRYPTO’ 99. CRYPTO 1999. Lecture Notes in Computer Science, vol 1666. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48405-1_17
Download citation
DOI: https://doi.org/10.1007/3-540-48405-1_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66347-8
Online ISBN: 978-3-540-48405-9
eBook Packages: Springer Book Archive