cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

, the pseudorandom-function advantage (PRF advantage) of an algorithm on a

pseudorandom function family In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle in the following way: no efficient algorithm can distinguish (with significant advantage) betwee ...

is a measure of how effectively the algorithm can distinguish between a member of the family and a

random oracle In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every ''unique query'' with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time th ...

. 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.

References

External links

* http://cseweb.ucsd.edu/~mihir/papers/gb.html {{Webarchive, url=https://web.archive.org/web/20120421084751/http://cseweb.ucsd.edu/~mihir/papers/gb.html , date=2012-04-21 Theory of cryptography Pseudorandomness