En criptografía , una permutación pseudoaleatoria (PRP) es una función que no se puede distinguir de una permutación aleatoria (es decir, una permutación seleccionada al azar con probabilidad uniforme, de la familia de todas las permutaciones en el dominio de la función) con esfuerzo práctico.
Sea F una función . F es un PRP si y sólo si
Una familia de permutaciones pseudoaleatorias es una colección de permutaciones pseudoaleatorias, donde se puede elegir una permutación específica utilizando una clave.
La abstracción idealizada de un cifrado de bloque (con clave) es una permutación verdaderamente aleatoria de las asignaciones entre texto simple y texto cifrado. Si existe un algoritmo distintivo que logra una ventaja significativa con menos esfuerzo que el especificado por el parámetro de seguridad del cifrado de bloque (esto generalmente significa que el esfuerzo requerido debería ser aproximadamente el mismo que una búsqueda de fuerza bruta a través del espacio de claves del cifrado), entonces el cifrado se considera roto al menos en un sentido de certificación, incluso si tal ruptura no conduce inmediatamente a una falla de seguridad práctica . [2]
Se espera que los cifrados modernos tengan una pseudoaleatoriedad superrápida, es decir, que el cifrado sea indistinguible de una permutación elegida aleatoriamente en el mismo espacio de mensajes, incluso si el adversario tiene acceso de caja negra a las direcciones directa e inversa del cifrado. [3]
Michael Luby y Charles Rackoff [4] demostraron que se puede construir una permutación pseudoaleatoria "fuerte" a partir de una función pseudoaleatoria utilizando una construcción de Luby-Rackoff que se construye utilizando un cifrado de Feistel .
Una permutación impredecible ( UP ) F k es una permutación cuyos valores no pueden predecirse mediante un algoritmo aleatorio rápido . Las permutaciones impredecibles pueden utilizarse como primitivas criptográficas , un bloque de construcción para sistemas criptográficos con propiedades más complejas.
Un adversario para una permutación impredecible se define como un algoritmo al que se le da acceso a un oráculo para operaciones de permutación tanto directa como inversa. Al adversario se le da una entrada de desafío k y se le pide que prediga el valor de F k . Se le permite realizar una serie de consultas al oráculo para ayudarlo a realizar esta predicción, pero no se le permite consultar el valor de k en sí. [5]
Un algoritmo aleatorio para generar permutaciones genera una permutación impredecible si sus resultados son permutaciones en un conjunto de elementos (descritos por cadenas binarias de longitud n ) que no se pueden predecir con una precisión significativamente mejor que la aleatoria por un adversario que realiza un número polinomial (en n ) de consultas al oráculo antes de la ronda de desafío, cuyo tiempo de ejecución es polinomial en n , y cuya probabilidad de error es menor que 1/2 para todas las instancias. Es decir, no se puede predecir en la clase de complejidad PP , relativizada por el oráculo para la permutación. [5]
Se puede demostrar que una función F k no es un código de autenticación de mensajes seguro (MAC) si satisface únicamente el requisito de imprevisibilidad. También se puede demostrar que no se puede construir un MAC de longitud de entrada variable eficiente a partir de un cifrado de bloque que se modela como un UP de n bits. Se ha demostrado que la salida de una construcción de Feistel de k = n / ω (log λ ) rondas con funciones de ronda impredecibles puede filtrar todos los valores de ronda intermedios. [5] Incluso para funciones impredecibles (UF) realistas, es posible que se filtre alguna información parcial sobre los valores de ronda intermedios a través de la salida. Más tarde se demostró que si se utiliza un número superlogarítmico de rondas en la construcción de Feistel, entonces la construcción UP resultante es segura incluso si el adversario obtiene todos los valores de ronda intermedios junto con la salida de permutación. [6]
También hay un teorema que ha sido probado a este respecto que establece que si existe un adversario UP eficiente A π que tiene una ventaja no despreciable ε π en el juego de imprevisibilidad contra la construcción UP ψ U,k y que realiza un número polinomial de consultas al retador, entonces también existe un adversario UF A f que tiene una ventaja no despreciable en el juego de imprevisibilidad contra un UF muestreado de la familia UF F . A partir de esto, se puede demostrar que la ventaja máxima del adversario UP A π es ε π = O ( ε f . ( qk ) 6 ). Aquí ε f denota la ventaja máxima de un adversario UF corriendo en el tiempo O( t + ( qk ) 5 ) contra un UF muestreado de F , donde t es el tiempo de ejecución del adversario PRP A ψ y q es el número de consultas realizadas por él. [6] [7]
Además, un esquema de firma que satisface la propiedad de imprevisibilidad y no necesariamente pseudoaleatoriedad es esencialmente una Función Impredecible Verificable (VUF). Una función impredecible verificable se define de manera análoga a una Función Pseudoaleatoria Verificable (VRF), pero la pseudoaleatoriedad se sustituye por una imprevisibilidad más débil. Las permutaciones impredecibles verificables son los análogos de permutación de las VUF o los análogos impredecibles de las VRP. Una VRP también es una VUP y una VUP puede construirse de hecho construyendo una VRP mediante la construcción de Feistel aplicada a una VRF. Pero esto no se considera útil ya que las VUF parecen ser mucho más fáciles de construir que las VRF. [8]
