Welcome to the resource topic for 2000/029
Title:
Concrete Security Characterizations of PRFs and PRPs: Reductions and Applications
Authors: Anand Desai, 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.
ePrint: https://eprint.iacr.org/2000/029
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .