Segurança semântica

Em criptografia, um sistema criptográfico é semanticamente seguro se nenhum algoritmo probabilístico de tempo polinomial (PPTA) que, quando recebe o texto cifrado de uma determinada mensagem $m$ (obtido de qualquer distribuição de mensagens) e o comprimento da mensagem, consegue determinar qualquer informação parcial sobre a mensagem com probabilidade não insignificante maior do que todos os outros PPTA que só têm acesso ao tamanho da mensagem (e não o texto cifrado). Em outras palavras, o conhecimento do texto cifrado (e seu comprimento) de alguma mensagem desconhecida não revela nenhuma informação adicional sobre a mensagem que, possivelmente, pode ser extraída. Este conceito é o análogo da complexidade computacional ao conceito de sigilo perfeito de Shannon. Sigilo perfeito significa que o texto cifrado não revela nenhuma informação sobre o texto puro, enquanto que a segurança semântica implica que qualquer informação revelada não pode ser extraída.

História

A noção de segurança semântica foi apresentada pela primeira vez por Goldwasser e Micali em 1982. No entanto, a definição inicialmente proposta não oferecia meios diretos para provar a segurança dos sistemas de encriptação práticos. Goldwasser e Micali, posteriormente, demonstraram que a segurança semântica é equivalente a outra definição de segurança chamada indistinguibilidade de textos cifrados sob ataque de texto puro escolhido. Esta última definição é mais comum do que a definição original de segurança semântica, porque ela facilita a prova da segurança dos sistemas de encriptação práticos.

Criptografia de chave simétrica

No caso de criptossistemas que usam um algoritmo de chave simétrica, um adversário não deve ser capaz de computar qualquer informação sobre um texto puro a partir do seu texto cifrado. Isto pode ser posto como: adversários, dados dois textos simples de igual comprimento e seus respectivos textos cifrados, não podem determinar qual texto cifrado pertence a qual texto puro.

Criptografia de chave pública

Para um criptossistema que usa um algoritmo de encriptação de chave pública (ou assimétrica) ser semanticamente seguro, deve ser inviável para um adversário computacionalmente limitado obter informações importantes sobre uma mensagem (texto puro), quando dados apenas o seu texto cifrado e a chave pública correspondente. A segurança semântica considera apenas o caso de um atacante "passivo", ou seja, aquele que gera e observa as mensagens cifradas usando a chave pública e textos puros de sua escolha.

Ao contrário de outras definições de segurança, segurança semântica não considera o caso de ataque de cifrotexto escolhido (ACE), no qual um atacante é capaz de solicitar a decriptação de mensagens cifradas escolhidas, e muitos esquemas de criptografia semanticamente seguros são comprovadamente inseguros contra ataques de cifrotexto escolhido. Consequentemente, a segurança semântica é agora considerada uma condição insuficiente para garantir um sistema de criptografia para uso geral, embora, geralmente, isso seja uma descrição imprecisa da realidade.

Indistinguibilidade sob o ataque de texto puro escolhido (IND-CPA) é comumente definida pelo seguinte experimento:

1. 1. Um par aleatório $(pk,sk)$ 1. é gerado quando se roda $Gen(1^{n})$.
2. 2. A um adversário limitado probabilística e polinomialmente pelo tempo é dada a chave pública $pk$ , a qual ele pode usar para gerar qualquer número de mensagens cifradas (dentro de limites polinomiais).
3. 3. O adversário gera duas mensagens de igual comprimento $m_{0}$ e $m_{1}$, 3. e as transmite para um oráculo desafiador juntamente com a chave pública.
4. 4. O oráculo desafiador seleciona uma das mensagens, jogando uma moeda justa (selecionando um bit aleatório $b\in {0,1}$), 4. criptografa a mensagem $m_{b}$ sob a chave pública, e retorna o resultado do texto cifrado desafio $c$ ao adversário.

O sistema de criptografia subjacente é IND-CPA (e, portanto, semanticamente seguro sob o ataque de texto simples escolhido) se o adversário não puder determinar qual das duas mensagens foi escolhida pelo oráculo, com probabilidade significativamente maior do que $1/2$ (a taxa de sucesso de adivinhação aleatória). Variantes dessa definição definem indistinguibilidade sob ataque de cifrotexto escolhido e ataque de cifrotexto escolhido adaptativo (IND-CCA, IND-CCA2).

Porque o adversário possui a chave pública de criptografia no jogo acima, um esquema de criptografia semanticamente seguro deve, por definição, ser probabilística, possuindo a componente de aleatoriedade. Se não fosse esse o caso, o adversário poderia simplesmente computar a criptografia determinística de $m_{0}$ e $m_{1}$ e compará-las com o texto cifrado $c$ retornado para adivinhar com sucesso a escolha do oráculo.

Algoritmos de encriptação semanticamente seguros incluem Goldwasser-Micali, El Gamal e Paillier. Estes esquemas são comprovados seguros, pois a sua segurança semântica pode ser reduzida para resolver alguns problemas matemáticos difíceis (por exemplo, Decisional Diffie-Hellman ou a Quadratic Residuosity Problem). Outros algoritmos semanticamente inseguros, como RSA, podem se tornar semanticamente seguros (sob hipóteses mais fortes) através da utilização de sistemas de criptografia de preenchimento aleatório, tais como a encriptação assimétrica de preenchimento ótimo (OAEP).