La ventaja de la función pseudoaleatoria ( ventaja PRF ) de un algoritmo en 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 . En consecuencia, la ventaja pseudoaleatoria máxima que puede alcanzar cualquier algoritmo con una cantidad fija de recursos computacionales es una medida de qué tan bien esta familia de funciones emula un oráculo aleatorio.
Digamos que un algoritmo adversario tiene acceso a un oráculo que aplicará una función a las entradas que se le envíen. El algoritmo envía al oráculo una serie de consultas antes de decidir si el oráculo es un oráculo aleatorio o simplemente una instancia de la familia de funciones pseudoaleatorias. Digamos también que hay un 50% de probabilidad de que el oráculo sea un oráculo aleatorio y un 50% de probabilidad de que sea un miembro de la familia de funciones. La ventaja pseudoaleatoria del algoritmo se define como dos veces la probabilidad de que el algoritmo adivine correctamente menos uno. [1] [2]
Referencias
- ^ Goldwasser, S. y Bellare, M. "Notas de la conferencia sobre criptografía" . Curso de verano sobre criptografía, MIT, 1996-2001
- ^ Li, Ninghui (otoño de 2004), Security of Symmetric Ciphers, consultado el 6 de diciembre de 2010 en http://www.cs.purdue.edu/homes/ninghui/courses/Fall04/lectures/lect07.pdf