El cifrado probabilístico es el uso de 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 clave simétrica 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 simple , un algoritmo de cifrado debe ser probabilístico .
El primer esquema de cifrado probabilístico de clave pública 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 de 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 simple es "SÍ" o "NO", o tiene la corazonada de que el texto simple podría ser "ATAQUE EN CALAIS". Cuando se utiliza un algoritmo de cifrado determinista , el adversario puede simplemente intentar cifrar cada una de sus suposiciones 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 simple se corresponda con uno de un gran número de textos cifrados posibles.
Un enfoque intuitivo para convertir un esquema de cifrado determinista en uno probabilístico es simplemente rellenar el texto sin formato 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 determinista. Las técnicas como el relleno de cifrado asimétrico óptimo (OAEP) integran el relleno aleatorio de una manera que es segura utilizando cualquier permutación de puerta trampa .
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 oráculo aleatorio:
