In cryptography, the pseudorandom-function advantage (PRF advantage) of an algorithm on a pseudorandom function family is a measure of how effectively the algorithm can distinguish between a member of the family and a random oracle. Consequently, the maximum pseudorandom advantage attainable by any algorithm with a fixed amount of computational resources is a measure of how well such a function family emulates a random oracle.
Say that an adversary algorithm has access to an oracle that will apply a function to inputs that are sent to it. The algorithm sends the oracle a number of queries before deciding whether the oracle is a random oracle or simply an instance of the pseudorandom function family. Say also that there is a 50% chance that the oracle is a random oracle and a 50% chance that it is a member of the function family. The pseudorandom advantage of the algorithm is defined as two times the probability that the algorithm guesses correctly minus one.12
References
References
- Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography" Archived 2012-04-21 at the Wayback Machine. Summer course on cryptography, MIT, 1996-2001
- Li, Ninghui (Fall 2004), Security of Symmetric Ciphers, retrieved December 6, 2010 from http://www.cs.purdue.edu/homes/ninghui/courses/Fall04/lectures/lect07.pdf Archived 2011-09-27 at the Wayback Machine
External links
External links
- http://cseweb.ucsd.edu/~mihir/papers/gb.html Archived 2012-04-21 at the Wayback Machine