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
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2000/029}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.