| Concrete security characterizations of PRFs and PRPs: Reductions and applications," Full version of this paper, available via: http://www-cse.ucsd.edu/users/sminer (1976) | |||||||||||||||||
Abstract | |||||||||||||||||
| 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 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. 1 | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||