Paper 2000/029
Concrete Security Characterizations of PRFs and PRPs: Reductions and Applications
Anand Desai and Sara Miner
Abstract
We investigate, in a concrete security setting, several alternate characterizations of pseudorandom functions (PRFs) and pseudorandom permutations (PRPs). 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 a certain class of message authentication codes. We also apply these techniques 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.
Metadata
- Available format(s)
- PS
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- pseudo-randomnessconcrete security
- Contact author(s)
- adesai @ cs ucsd edu
- History
- 2000-06-15: revised
- 2000-06-14: received
- See all versions
- Short URL
- https://ia.cr/2000/029
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2000/029,
author = {Anand Desai and Sara Miner},
title = {Concrete Security Characterizations of PRFs and PRPs: Reductions and Applications},
howpublished = {Cryptology ePrint Archive, Paper 2000/029},
year = {2000},
note = {\url{https://eprint.iacr.org/2000/029}},
url = {https://eprint.iacr.org/2000/029}
}
