La indistinguibilidad del texto cifrado es una propiedad de muchos esquemas de cifrado . Intuitivamente, si un criptosistema posee la propiedad de indistinguibilidad , entonces un adversario no podrá distinguir pares de textos cifrados en función del mensaje que cifran. La propiedad de indistinguibilidad bajo el ataque de texto sin formato elegido se considera un requisito básico para la mayoría de los criptosistemas de clave pública demostrablemente seguros , aunque algunos esquemas también proporcionan indistinguibilidad bajo el ataque de texto cifrado elegido y el ataque de texto cifrado elegido adaptativo.. La indistinguibilidad bajo el ataque de texto sin formato elegido es equivalente a la propiedad de seguridad semántica , y muchas pruebas criptográficas usan estas definiciones indistintamente.
Un criptosistema se considera seguro en términos de indistinguibilidad si ningún adversario, dado el cifrado de un mensaje elegido al azar de un espacio de mensaje de dos elementos determinado por el adversario, puede identificar la elección del mensaje con una probabilidad significativamente mejor que la de adivinar al azar ( 1 ⁄ 2 ). Si cualquier adversario puede lograr distinguir el texto cifrado elegido con una probabilidad significativamente mayor que 1 ⁄ 2 , entonces se considera que este adversario tiene una "ventaja" para distinguir el texto cifrado, y el esquema no es válido.considerado seguro en términos de indistinguibilidad. Esta definición abarca la noción de que en un esquema seguro, el adversario no debe obtener información al ver un texto cifrado. Por lo tanto, el adversario no debería poder hacer nada mejor que si adivinara al azar.
La seguridad en términos de indistinguibilidad tiene muchas definiciones, dependiendo de las suposiciones hechas sobre las capacidades del atacante. Normalmente se presenta como un juego , donde el criptosistema se considera seguro si ningún adversario puede ganar el juego con una probabilidad significativamente mayor que un adversario que debe adivinar al azar. Las definiciones más comunes utilizadas en criptografía son la indistinguibilidad bajo el ataque de texto sin formato elegido (abreviado IND-CPA), la indistinguibilidad bajo el ataque de texto cifrado elegido (no adaptativo) (IND-CCA1) y la indistinguibilidad bajo el ataque de texto cifrado elegido adaptativo .(IND-CCA2). La seguridad según cualquiera de las últimas definiciones implica seguridad según las anteriores: un esquema que es seguro IND-CCA1 también es seguro IND-CPA, y un esquema que es seguro IND-CCA2 es seguro tanto IND-CCA1 como IND-CPA. Por lo tanto, IND-CCA2 es la más sólida de las tres definiciones de seguridad.
Para un algoritmo de cifrado de clave asimétrica probabilística , la indistinguibilidad bajo el ataque de texto sin formato elegido (IND-CPA) se define mediante el siguiente juego entre un adversario y un retador. Para esquemas basados en seguridad computacional , el adversario es modelado por una máquina de Turing de tiempo polinómico probabilístico , lo que significa que debe completar el juego y generar una conjetura dentro de un número polinomial de pasos de tiempo. En esta definición E(PK, M ) representa el cifrado de un mensaje M bajo la clave PK :