Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / pseudo-randomness, concrete security

Date: received 13 Jun 2000, revised 14 Jun 2000

Contact author: adesai at cs ucsd edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20000615:004242 (All versions of this report)

Short URL: ia.cr/2000/029

Discussion forum: Show discussion | Start new discussion