# Indistinguibilidade de textos cifrados

Indistinguibilidade de textos cifrados é uma propriedade de alguns esquemas de encriptação. Intuitivamente, se um criptossistema possui a propriedade de indistinguibilidade, então um adversário será incapaz de distinguir pares de textos cifrados baseados em mensagens encriptadas por eles. A propriedade de indistinguibilidade sob ataque de texto claro escolhido é considerado um requisito básico por grande parte dos criptossistemas de chave pública demonstravelmente seguros, embora alguns esquemas também proveem indistinguibilidade sob ataque de texto cifrado escolhido e ataque de texto cifrado escolhido adaptativo. indistinguibilidade sob ataque de texto claro escolhido é equivalente à propriedade de segurança semântica, e muitas provas criptográficas usam essas definições indistintamente.
Um criptossistema é considerado seguro em termos de indistinguibilidade se nenhum adversário, dado uma encriptação de uma mensagem aleatoriamente escolhida de um espaço contendo duas mensagens determinado pelo adversário, pode identificar a escolha da mensagem com uma probabilidade significativamente melhor que a adivinhação aleatória (1⁄2). Se um adversário qualquer pode ser bem sucedido em distinguir o texto cifrado escolhido com uma probabilidade significativamente maior que 1⁄2, então esse adversário é considerado como tendo uma "vantagem" em distinguir o texto cifrado, e o esquema não é considerado seguro em termos de indistinguibilidade. Essa definição engloba a noção de que em um esquema seguro, o adversão não deveria ser capaz de obter nenhuma informação somente observando o texto cifrado. Portanto, o adversário não deveria ser capaz de fazer melhor do que se tivesse estipulado aleatoriamente.

## Definições formais

Segurança em termos de indistinguibilidade tem muitas definições, dependendo das suposições feitas sobre as capacidades do atacante. A definição de segurança é normalmente apresentada como um jogo, onde o criptossistema é considerado seguro se nenhum adversário pode ganhar o jogo com probabilidade significativamente maior que um adversário que estipula aleatoriamente. As definições mais comuns usadas em criptografia são indistinguibilidade sob ataque de texto claro escolhido (abreviação em inglês: IND-CPA), indistinguibilidade sob ataque (não-adaptativo) com texto cifrado escolhido (IND-CCA), e indistinguibilidade sob ataque adaptativo com texto cifrado escolhido (IND-CCA2). Segurança sob qualquer dessas definições implica segurança sob as anteriores: um esquema que é seguro sob IND-CCA também é seguro sob IND-CPA, e um esquema que é seguro sob IND-CCA2 também é seguro sob IND-CCA e sob IND-CPA. Portanto, IND-CCA2 é a mais forte das três definições de segurança.

### indistinguibilidade sob ataque com texto claro escolhido (IND-CPA)

Para um algoritmo de encriptação probabilística assimétrica de chave pública, indistinguibilidade sob ataque de texto claro escolhido (IND-CPA) é definida pelo seguinte jogo entre um adversário e um desafiador. Para esquemas baseados em segurança computacional, o adversário é modelado por uma máquina de Turing de tempo polinomial probabilístico, o que significa que ela deve completar o jogo e dar como saída uma estipulação dentro de um número polinomial de unidades de tempo. Sob essa definição, E(PK, M) representa a encriptação de uma mensagem M sob a chave PK:
* O desafiador gera um par de chaves PK, SK baseado em algum parâmetro de segurança k (e.g., um tamanho de chave em bits), e publica PK para o adversário. O desafiador guarda SK.
* O adversário pode realizar um número polinomialmente limitado de encriptações ou outras operações.
* Posteriormente, o adversário submete dois textos claros distintos $\scriptstyle M_{0},M_{1}$ ao desafiador.
* O desafiador seleciona um b $\in$ {0, 1} uniforme e aleatoriamente, e envia o texto cifrado desafio C = E(PK, $\scriptstyle M_{b}$) de volta ao adversário.
* O adversário é livre para realizar qualquer número de computações ou encriptações adicionais. Finalmente, ele dá como saída uma estipulação para o valor de b.
Um criptossistema é indistinguível sob ataque de texto claro escolhido se todo adversário de tempo polinomial probabilístico tem apenas uma "vantagem" desprezível sob estipulação aleatória. Um adversário é dito ter uma "vantagem" desprezível se ele vence o jogo acima com probabilidade $\scriptstyle \left({\frac {1}{2}}\right)\,+\,\epsilon (k)$, onde $\epsilon (k)$ é uma função desprezível no parâmetro de segurança k, isto é, para toda função polinomial (não-nula) $poly$ existe $k_{0}$ tal que $\scriptstyle |\epsilon (k)|\;<\;\left|{\frac {1}{poly(k)}}\right|$ para todo $\scriptstyle k\;>\;k_{0}$.
Embora o adversário conheça $\scriptstyle M_{0}$, $\scriptstyle M_{1}$ e PK, a natureza probabilística de E significa que a encriptação de $\scriptstyle M_{b}$ será apenas um de muitos textos cifrados válidos, e portanto encriptar $\scriptstyle M_{0}$, $\scriptstyle M_{1}$, e comparar os textos cifrados resultantes com o cifrotexto desafio não concede qualquer vantagem não-desprezível ao adversário.
Enquanto que a definição acima é específica para um criptossistema de chave assimétrica, ela pode ser adaptada ao caso simétrico substituindo-se a função de encriptação de chave pública por um "oráculo de encriptação", que retém a chave de encriptação secreta e encripta textos claros arbitrários à medida em que o adversário solicita.

### indistinguibilidade sob ataque de texto cifrado escolhido (IND-CCA, IND-CCA2)

Indistinguibilidade sob Ataque de texto cifrado Escolhido não-adaptativo (IND-CCA, IND-CCA2) usa uma definição semelhante à de IND-CPA. Entretanto, além da chave pública (ou do oráculo de encriptação, no caso simétrico), o adversário ganha acesso a um oráculo de decriptação que decripta textos cifrados arbitrários sob solicitação do adversário, retornando o texto claro. Na definição não-adaptativa, o adversário pode consultar esse oráculo somente até que ele receba o texto cifrado desafio. Na definição adaptativa, o adversário pode continuar a consultar o oráculo de decriptação mesmo após ele ter recebido o texto cifrado desafio, com a restrição de que ele não pode passar o texto cifrado desafio para decriptação (pois, do contrário, a definição seria trivial).
* O desafiador gera um par de chaves "PK", "SK" baseado em algum parâmetro de segurança k (e.g. um tamanho de chave em bits), e publica "PK" para o adversário. O desafiador retém "SK".
* O adversário pode realizar qualquer quantidade de encriptações, chamadas ao oráculo de decriptação baseadas em textos cifrados arbitrários, ou outras operações.
* Posteriormente, o adversário submete dois textos claros escolhidos distintos $\scriptstyle M_{0},M_{1}$ ao desafiador.
* The challenger selects a bit b ∈ {0, 1} uniformly at random, and sends the "challenge" ciphertext C = E(PK, ) back to the adversary. O desafiador seleciona um bit b $\scriptstyle \in$ {0, 1} uniforme e aleatoriamente por e envia o texto cifrado desafio C = E(PK, $\scriptstyle M_{b}$) de volta para o adversário.
* O adversário é livre para realizar qualquer quantidade de computações ou encriptações adicionais.
** No caso não adaptativo (IND-CCA), o adversário pode não fazer futuras chamadas ao oráculo de decriptação.
** No caso adaptativo (IND-CCA2), o adversário pode fazer chamadas para o oráculo de decriptação, mas não pode submeter o texto cifrado desafio C.
* Finamente, o adversário faz uma estipulação para o valor de "b e o dá como saída.
Um esquema é IND-CCA/IND-CCA2 seguro se nenhum adversário tem uma vantagem não desprezível para vencer o jogo acima.

## Equivalência e implicações

Indistinguibilidade é uma importante propriedade para manutenção da confidencialidade de comunicações encriptadas. No entanto, a propriedade da indistinguibilidade tem, em alguns casos sido revelada como implicando em outras, aparentemente não-relacionadas propriedades de segurança. Às vezes essas implicações vão em ambas as direções, tornando as duas definições equivalentes; por exemplo, sabe-se que a propriedade da indisguinbilidade sob ataque de cifrotexto escolhido adaptativo (IND-CCA2) é equivalente à propriedade da não-maleabilidade sob o mesmo cenário de ataque (NM-CCA2). Essa equivalência não é imediatamente óbvia, pois não-maleabilidade é uma propriedade que trata da integridade de mensagens, ao invés de confidencialidade. Em outros casos, tem sido demonstrado que indistinguibilidade pode ser combinada com certas outras definições, de modo a levar a outras definições úteis, e vice-versa. A seguinte lista resume algumas implicações conhecidas, embora não seja de forma alguma completa.
A notação $\scriptstyle A\;\Rightarrow \;B$ significa que a propriedade A implica na propriedade B. $\scriptstyle A\;\Leftrightarrow \;B$ siginfica que a propriedade A e B são equivalentes. $\scriptstyle A\;\not \Rightarrow \;B$ significa que a propriedade A não necessariamente implica na propriedade B.
* IND-CPA $\scriptstyle \Leftrightarrow$ semântica segura sobre CPA.
* NM-CPA (não maleável sob ataque de purotexto escolhido) $\scriptstyle \Rightarrow$ IND-CPA.
* NM-CPA (não maleável sob ataque de purotexto escolhido) $\scriptstyle \not \Rightarrow$ IND-CCA2.
* NM-CCA2 (não maleável sob ataque de cifrotexto escolhido) $\scriptstyle \Leftrightarrow$ IND-CCA2.