Hispanopedia Wiki
Articulo de referencia

permutación pseudoaleatoria

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

Hispanopedia WikiContenido en espanolLectura gratuita

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 un esfuerzo práctico.

Definición

Sea F una función de mapeo.{0,1}norte×{0,1}s→{0,1}norte{\displaystyle \left\{0,1\right\}^{n}\times \left\{0,1\right\}^{s}\rightarrow \left\{0,1\right\}^{n}}. F es un PRP si y solo si

  • Para cualquierK∈{0,1}s{\displaystyle K\in \left\{0,1\right\}^{s}},FK{\displaystyle F_{K}}es una biyección de{0,1}norte{\displaystyle \left\{0,1\right\}^{n}}a{0,1}norte{\displaystyle \left\{0,1\right\}^{n}}, dóndeFK(incógnita)=F(incógnita,K){\displaystyle F_{K}(x)=F(x,K)}.
  • Para cualquierK∈{0,1}s{\displaystyle K\in \left\{0,1\right\}^{s}}, existe un algoritmo "eficiente" para evaluarFK(incógnita){\displaystyle F_{K}(x)}para cualquierincógnita∈{0,1}norte{\displaystyle x\in \left\{0,1\right\}^{n}},.
  • Para todos los distinguidores probabilísticos de tiempo polinomialD{\displaystyle D}:|PAGr(DFK(1norte)=1)−PAGr(DFnorte(1norte)=1)|<ε(s){\displaystyle \left|Pr\left(D^{F_{K}}(1^{n})=1\right)-Pr\left(D^{f_{n}}(1^{n})=1\right)\right|<\varepsilon (s)}, dóndeK∈{0,1}s{\displaystyle K\in \left\{0,1\right\}^{s}}se elige uniformemente al azar yFnorte{\displaystyle f_{n}}se elige uniformemente al azar del conjunto de permutaciones en cadenas de n bits. [ 1 ]

Una familia de permutaciones pseudoaleatorias es una colección de permutaciones pseudoaleatorias, donde se puede elegir una permutación específica utilizando una clave.

El modelo de cifrado por bloques

La abstracción idealizada de un cifrado de bloques (con clave) es una permutación verdaderamente aleatoria de las correspondencias entre texto plano 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 bloques (esto generalmente significa que el esfuerzo requerido debería ser aproximadamente el mismo que una búsqueda por fuerza bruta en el espacio de claves del cifrado), entonces el cifrado se considera roto al menos en un sentido de certificación, incluso si dicha ruptura no conduce inmediatamente a una falla de seguridad práctica . [ 2 ]

Se espera que los cifrados modernos tengan una pseudoaleatoriedad superior. Es decir, el cifrado debe ser indistinguible de una permutación elegida al azar en el mismo espacio de mensajes, incluso si el adversario tiene acceso de caja negra a las direcciones directa e inversa del cifrado. [ 3 ]

Conexiones con función pseudoaleatoria

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

Permutación impredecible

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 componente básico para sistemas criptográficos con propiedades más complejas.

Un adversario para una permutación impredecible se define como un algoritmo que tiene acceso a un oráculo para operaciones de permutación tanto directas como inversas. Al adversario se le proporciona 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 hacer esta predicción, pero no se le permite consultar el valor de k en sí mismo. [ 5 ]

Un algoritmo aleatorio para generar permutaciones genera una permutación impredecible si sus salidas son permutaciones en un conjunto de elementos (descritos por cadenas binarias de longitud n ) que no pueden ser predichas 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 puede ser predicha en la clase de complejidad PP , relativizada por el oráculo para la permutación. [ 5 ]

Propiedades de las permutaciones impredecibles

Se puede demostrar que una función F k no es un código de autenticación de mensajes (MAC) seguro si solo satisface el requisito de imprevisibilidad. También se puede demostrar que no se puede construir un MAC eficiente de longitud de entrada variable a partir de un cifrado de bloques modelado como una UP de n bits. Se ha demostrado que la salida de una construcción 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, cierta información parcial sobre los valores de ronda intermedios puede filtrarse a través de la salida. Posteriormente se demostró que si se utiliza un número superlogarítmico de rondas en la construcción Feistel, 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 existe un teorema demostrado al 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 que se ejecuta en 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 de pseudoaleatoriedad es esencialmente una Función Impredecible Verificable (VUF). Una función impredecible verificable se define de forma análoga a una Función Pseudoaleatoria Verificable (VRF), pero sustituyendo la pseudoaleatoriedad 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 construyendo una VRP mediante la construcción de Feistel aplicada a una VRF. Sin embargo, esto no se considera útil, ya que las VUF parecen ser mucho más fáciles de construir que las VRF. [ 8 ]

Aplicaciones

K x X → X ∀ X={0,1} 64 , K={0,1} 56
K x X → X ∀ k=X={0,1} 128

Véase también

Referencias

  1. ↑ Katz, Jonathan; Lindell, Yehuda (2007). Introducción a la criptografía moderna: principios y protocolos . Chapman and Hall/CRC. ISBN 978-1584885511.
  2. ↑ Mihir Bellare , Phillip Rogaway (11 de mayo de 2005). "Capítulo 4: Funciones pseudoaleatorias" (PDF) . Introducción a la criptografía moderna . Consultado el 18 de mayo de 2020 .
  3. ↑ Craig Gentry y Zulfikar Ramzan. "Eliminación de oráculos de permutación aleatoria en el cifrado Even-Mansour" .
  4. ↑ Luby, Michael; Rackoff, Charles (1988). "Cómo construir permutaciones pseudoaleatorias a partir de funciones pseudoaleatorias" . SIAM J. Comput . 17 (2): 373– 386. doi : 10.1137/0217022 .
  5. 1 2 3 Puniya, Prashant (2007), Nuevos criterios de diseño para funciones hash y cifrados de bloques (PDF) , tesis doctoral, Departamento de Ciencias de la Computación, Universidad de Nueva York.
  6. 1 2 Avances en criptología – EUROCRYPT 2007: 26.ª Conferencia Internacional Anual sobre la Teoría y Aplicaciones de las Técnicas Criptográficas – por Moni Naor, Asociación Internacional para la Investigación Criptológica
  7. ↑ Steinberger, John P. (2007). "La intratabilidad de colisiones de MDC-2 en el modelo de cifrado ideal" (PDF) . Avances en criptología - EUROCRYPT 2007. Notas de clase en ciencias de la computación. Vol. 4515. págs. 34–51 . Bibcode : 2007LNCS.4515...34S . doi : 10.1007/978-3-540-72540-4_3 . ISBN   978-3-540-72539-8. S2CID 33464561 . Archivado del original (PDF) el 25 de marzo de 2007 . Recuperado el 27 de febrero de 2023 . 
  8. ↑ Micali, Silvio ; Rabín, Michael ; Vadhan, Salil (1999), "Funciones aleatorias verificables", 40º Simposio anual sobre fundamentos de la informática (Nueva York, 1999) , IEEE Computer Soc., Los Alamitos, CA, págs. 120-130 , CiteSeerX 10.1.1.207.6638 , doi : 10.1109/SFFCS.1999.814584 , ISBN   978-0-7695-0409-4, MR 1917552 , S2CID 221565852  .