Abstract
We investigate several alternate characterizations of pseudorandom functions (PRFs) and pseudorandom permutations (PRPs) in a concrete security setting. By analyzing the concrete complexity of the reductions between the standard notions and the alternate ones, we show that the latter, while equivalent under polynomial-time reductions, are weaker in the concrete security sense. With these alternate notions, we argue that it is possible to get better concrete security bounds for certain PRF/PRP-based schemes. As an example, we show how using an alternate characterization of a PRF could result in tighter security bounds for some types of message authentication codes. We also use this method to give a simple concrete security analysis of the counter mode of encryption. In addition, our results provide some insight into how injectivity impacts pseudorandomness.
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
M. Bellare, R. Ccanetti and H. Krawczyk, “Keying hash functions for message authentication,” Advances in Cryptology-Crypto’ 96, LNCS Vol. 1109, N. Koblitz ed., Springer-Verlag, 1996.
M. Bellare, R. Canetti and H. Krawczyk, “Pseudorandom functions revisited: The cascade construction and its concrete security,” Proceedings of the 37th Symposium on Foundations of Computer Science, IEEE, 1996.
M. Bellare, A. Desai, E. Jokipii and P. Pogaway, “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, R. Guérin and P. Rogaway, “XOR MACs: New methods for message authentication using finite pseudorandom functions,” Advances in Cryptology-Crypto’ 95, LNCS Vol. 963, D. Coppersmith ed., Springer-Verlag, 1995.
M. Bellare, J. Kilian and P. Rogaway, “The security of the cipher block chaining message authentication code,” Advances in Cryptology-Crypto’ 94, LNCS Vol. 839, Y. Desmedt ed., Springer-Verlag, 1994.
M. Bellare and P. Rogaway, “On the construction of variable-input-length ciphers,” Proceedings of the SixthWorkshop on Fast Software Encryption, L. Knudsen ed., 1999.
A. Desai and S. Miner, “Concrete security characterizations of PRFs and PRPs: Reductions and applications,” Full version of this paper, available via: http://www-cse.ucsd.edu/users/sminer/.
O. Goldreich, S. Goldwasser and S. Micali, How to construct random functions. Journal of the ACM, 33(4): 792–807, 1986.
S. Goldwasser and S. Micali, “Probabilistic encryption,” Journal of Computer and System Science, Vol. 28, pp. 270–299, 1984.
S. Goldwasser, S. Micali and R. Rivest, “A digital signature signature scheme secure against adaptive chosen-message attacks,” SIAM J. of Computing, 17(2): 281–308, April 1988.
M. Luby and C. Rackoff, “How to construct pseudorandom permutations from pseudorandom functions,” SIAM J. Computing, 17(2), April 1988.
M. Naor and O. Reingold, “From unpredictability to indistinguishability: A simple construction of PRFs from MACs,” Advances in Cryptology-Crypto’ 98, LNCS Vol. 1462, H. Krawczyk ed., Springer-Verlag, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Desai, A., Miner, S. (2000). Concrete Security Characterizations of PRFs and PRPs: Reductions and Applications. In: Okamoto, T. (eds) Advances in Cryptology — ASIACRYPT 2000. ASIACRYPT 2000. Lecture Notes in Computer Science, vol 1976. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44448-3_39
Download citation
DOI: https://doi.org/10.1007/3-540-44448-3_39
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41404-9
Online ISBN: 978-3-540-44448-0
eBook Packages: Springer Book Archive