||This article provides insufficient context for those unfamiliar with the subject. Learn how and when to remove this template message) (January 2011) (|
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-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