International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Concrete Security Characterizations of PRFs and PRPs: Reductions and Applications

Authors:
Anand Desai
Sara Miner
Download:
URL: http://eprint.iacr.org/2000/029
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2000-11373,
  title={Concrete Security Characterizations of PRFs and PRPs: Reductions and Applications},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / pseudo-randomness, concrete security},
  url={http://eprint.iacr.org/2000/029},
  note={ adesai@cs.ucsd.edu 11123 received 13 Jun 2000, revised 14 Jun 2000},
  author={Anand Desai and Sara Miner},
  year=2000
}