PRF advantage

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.Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography". Summer course on cryptography, MIT, 1996-2001Li, Ninghui (Fall 2004), Security of Symmetric Ciphers, retrieved December 6, 2010 from http://www.cs.purdue.edu/homes/ninghui/courses/Fall04/lectures/lect07.pdf
== References ==
== External links ==
* http://cseweb.ucsd.edu/~mihir/papers/gb.html
Category:Theory of cryptography
Category:Algorithms