Indistinguibilidade computacional

Em complexidade computacional e criptografia, duas famílias de distribuições são indistinguíveis computacionalmente se nenhum algoritmo eficiente puder dizer a diferença entre elas, exceto com pequena probabilidade.

Definição formal

Sejam $\scriptstyle \{D_{n}\}_{n\in \mathbb {N} }$ e $\scriptstyle \{E_{n}\}_{n\in \mathbb {N} }$ dois conjuntos de distribuição indexados por um parâmetro de segurança n (que geralmente se refere ao comprimento da entrada); dizemos que eles são indistinguíveis computacionalmente se para qualquer algoritmo de tempo polinomial probabilístico não uniforme A, a seguinte quantidade é uma função desprezível em n:

$\delta (n)=\left|\Pr _{x\gets D_{n}}[A(x)=1]-\Pr _{x\gets E_{n}}[A(x)=1]\right|.$

denotada como $D_{n}\approx E_{n}$. Em outras palavras, o comportamento de cada algoritmo A eficiente não muda significativamente quando são fornecidas amostras de acordo com D_n ou E_n no limite de $n\to \infty$. Outra interpretação da indistinguibilidade computacional é que algoritmos de tempo polinomial tentando ativamente distinguir entre os dois conjuntos não podem fazer isso: que qualquer algoritmo desse tipo terá um desempenho insignificante melhor do que se alguém apenas adivinhasse.

Noções relacionadas

Implícita na definição está a condição de que o algoritmo, $A$, deve decidir com base em uma única amostra de uma das distribuições. Pode-se conceber uma situação em que o algoritmo que tenta distinguir entre duas distribuições pudesse acessar quantas amostras fosse necessário. Portanto, dois conjuntos que não podem ser distinguidos por algoritmos de tempo polinomial olhando para amostras múltiplas são considerados indistinguíveis por amostragem de tempo polinomial. Se o algoritmo de tempo polinomial pode gerar amostras em tempo polinomial, ou tem acesso a um oráculo aleatório que gera amostras para ele, então a indistinguibilidade por amostragem em tempo polinomial é equivalente à indistinguibilidade computacional.

Ligações externas

• Yehuda Lindell. Introdução à criptografia (em inglês)
• Donald Beaver, Silvio Micali e Phillip Rogaway, A complexidade de rodada de protocolos seguros (resumo estendido), 1990, páginas 503 à 513 (em inglês)
• Shafi Goldwasser e Silvio Micali. Criptografia probabilística. JCSS, 28(2):270 à 299, 1984 (em inglês)
• Oded Goldreich. Fundamentos da criptografia: volume 2 - Aplicações básicas. Imprensa universitária de Cambridge, 2004 (em inglês)
• Jonathan Katz, Yehuda Lindell, "Introdução à criptografia moderna: princípios e protocolos" Chapman & Hall/CRC, 2007 (em inglês)

Este artigo incorpora material de computacionalmente indistinguível no PlanetMath, que está licenciado sob a licença Creative Commons Attribution/Share-Alike.