El cifrado probabilístico es el uso de la aleatoriedad en un algoritmo de cifrado , de modo que al cifrar el mismo mensaje varias veces, en general, se obtendrán diferentes textos cifrados . El término "cifrado probabilístico" se utiliza normalmente en referencia a algoritmos de cifrado de clave pública ; sin embargo, varios algoritmos de cifrado de claves simétricas logran una propiedad similar (por ejemplo, cifrados de bloque cuando se utilizan en un modo de encadenamiento como CBC ) y cifrados de flujo como Freestyle [1] que son inherentemente aleatorios. Para ser semánticamente seguro , es decir, para ocultar incluso información parcial sobre el texto sin formato , un algoritmo de cifrado debe ser probabilístico .
El primer esquema de cifrado de clave pública probabilística demostrablemente seguro fue propuesto por Shafi Goldwasser y Silvio Micali , basado en la dureza del problema de residuosidad cuadrática y tenía un factor de expansión del mensaje igual al tamaño de la clave pública. Los algoritmos de cifrado probabilístico más eficientes incluyen Elgamal , Paillier y varias construcciones bajo el modelo de oráculo aleatorio , incluido OAEP.
El cifrado probabilístico es particularmente importante cuando se utiliza criptografía de clave pública . Supongamos que el adversario observa un texto cifrado y sospecha que el texto claro es "SÍ" o "NO", o tiene el presentimiento de que el texto claro podría ser "ATAQUE EN CALAIS". Cuando se utiliza un algoritmo de cifrado determinista , el adversario puede simplemente intentar cifrar cada una de sus conjeturas con la clave pública del destinatario y comparar cada resultado con el texto cifrado de destino. Para combatir este ataque, los esquemas de cifrado de clave pública deben incorporar un elemento de aleatoriedad, asegurando que cada texto plano se asigne a uno de un gran número de posibles textos cifrados.
Un enfoque intuitivo para convertir un esquema de cifrado determinista en uno probabilístico es simplemente rellenar el texto plano con una cadena aleatoria antes de cifrarlo con el algoritmo determinista . Por el contrario, el descifrado implica aplicar un algoritmo determinista e ignorar el relleno aleatorio. Sin embargo, los primeros esquemas que aplicaban este enfoque ingenuo fracasaron debido a las limitaciones de algunos esquemas de cifrado deterministas. Técnicas como el relleno de cifrado asimétrico óptimo (OAEP) integran el relleno aleatorio de una manera segura mediante cualquier permutación de trampilla .
Ejemplo de cifrado probabilístico utilizando cualquier permutación de trampilla:
Esto es ineficiente porque solo se cifra un bit. En otras palabras, el factor de expansión del mensaje es igual al tamaño de la clave pública.
Ejemplo de cifrado probabilístico en el modelo de Oracle aleatorio:
