PRF advantage

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.^[1]^[2]

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

External links

http://cseweb.ucsd.edu/~mihir/papers/gb.html Archived 2012-04-21 at the Wayback Machine

[1] Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography" Archived 2012-04-21 at the Wayback Machine. Summer course on cryptography, MIT, 1996-2001

[2] 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

[1]

[2]