Ventaja de PRF

En criptografía , la ventaja de función pseudoaleatoria ( ventaja PRF ) de un algoritmo sobre una familia de funciones pseudoaleatorias es una medida de la eficacia con la que el algoritmo puede distinguir entre un miembro de la familia y un oráculo aleatorio . Por consiguiente, la máxima ventaja pseudoaleatoria que puede alcanzar cualquier algoritmo con una cantidad fija de recursos computacionales es una medida de la precisión con la que dicha familia de funciones emula un oráculo aleatorio.

Supongamos que un algoritmo adversario tiene acceso a un oráculo que aplica una función a las entradas que se le envían. El algoritmo envía al oráculo varias consultas antes de decidir si se trata de un oráculo aleatorio o simplemente de una instancia de la familia de funciones pseudoaleatorias. Supongamos también que existe un 50 % de probabilidad de que el oráculo sea aleatorio y un 50 % de probabilidad de que pertenezca a la familia de funciones. La ventaja pseudoaleatoria del algoritmo se define como el doble de la probabilidad de que el algoritmo acierte menos uno. ^{[ 1 ] [ 2 ]}

• http://cseweb.ucsd.edu/~mihir/papers/gb.html Archivado el 21/04/2012 en Wayback Machine