Segurança Semântica (16 min)

Meu objetivo para os segmentos próximos anos é para mostrar que, se usarmos um PRG seguro Iremos

obter um fluxo seguro mais seguro. A primeira coisa que temos a fazer é definir é, o que faz

significa para um fluxo mais seguro para ser seguro? Portanto, sempre que definir a segurança sempre

defini-lo em termos do que pode fazer o atacante? E qual é o atacante

tentando fazer? No contexto do fluxo cifras lembrar estas só são utilizados

com uma chave de uma única vez, e como resultado, o mais invasor a é sempre indo para ver é

cifra apenas um texto criptografado utilizando a chave que estamos usando. E assim nós vamos

limitar os atacantes? capacidade de, basicamente, obter apenas um texto cifrado. E em

fato, mais tarde, vamos permitir que o invasor fazer muito, muito, muito mais, mas

por enquanto estamos só vai lhe dar uma cifra de texto. E nós queríamos encontrar,

o que significa para a cifra a ser seguro? Assim, a primeira definição que

me vem à mente é, basicamente, quer dizer, bem, talvez nós queremos exigir que o atacante

não pode realmente recuperar a chave secreta. Ok então dado texto [inaudível] você

não deve ser capaz de recuperar a chave secreta. Mas isso é uma definição terrível

porque pensar sobre o brilhante caindo [inaudível], mas a forma como criptografar a

mensagem utilizando uma chave K é basicamente de saída [inaudível] a mensagem. Ok isto

é um sim cifra brilhante é claro que não faz nada dado uma mensagem apenas

saída uma mensagem que o texto cifrado. Esta não é uma encriptação particularmente boa

esquema, no entanto, dado o texto cifrado, principalmente o atacante mensagem pobres

não pode recuperar a chave porque ele não sabe o que é a chave. E assim, como resultado

esta cifra claramente que é inseguro, seria considerado seguro nos termos do presente

exigência de segurança. Portanto, esta definição não será bom. Ok então é

recuperar a chave do segredo é o caminho errado para definir a segurança. Assim, a próxima coisa que nós

pode tentar meio que é, basicamente, apenas dizer, bem, talvez o atacante não se preocupa com

chave secreta, o que ele realmente se preocupa é o texto puro. Então, talvez ele deve ser

difícil para o atacante recuperar todo o texto sem formatação. Mas mesmo que não

trabalho, porque vamos pensar sobre o esquema de criptografia seguinte. Então, suponhamos que

que este esquema de criptografia não é que demora duas mensagens, então eu vou usar dois

linhas para denotar concatenação de duas mensagens M0 linha, linha M1 significa

concatenar M0 e M1. E imaginar que o esquema não é realmente ele produz

M0 no. clara e concatenar para que a criptografia de M1 Talvez ainda

usando o Bloco de One Time ok? E aqui é o atacante vai ser dado um

texto cifrado. E seu objetivo seria recuperar os textos inteiros simples. Mas o

atacante pobres não podem fazer isso porque aqui nós temos talvez M1 criptografada usando o One

Time Pad para que o atacante não pode realmente recuperar M1 porque sabemos que o

Time Pad Um dado é seguro apenas um texto cifrado. Então, essa construção

iria satisfazer a definição, mas, infelizmente, claramente este não é um seguro

esquema de criptografia, porque nós só vazou metade do texto simples. M0 é

completamente disponível para o atacante por isso mesmo que ele não pode recuperar todo o

texto simples ele pode ser capaz de recuperar a maior parte do texto simples, e isso é claramente

inseguro. Então é claro que já sabe a solução para isso e falamos sobre

Shanon definição de segurança segredo perfeito, onde Shannon idéia era que, em

fato, quando as interceptações atacante um texto cifrado, ele deve aprender absolutamente nenhuma

informações sobre os textos simples. Ele não deve mesmo aprender um pouco sobre o

texto simples ou até mesmo que ele não deveria saber, ele não deve mesmo ser capaz de prever um pouco

pouco sobre um lance do texto simples. Absolutamente nenhuma informação sobre o texto sem formatação.

Então vamos recordar muito brevemente conceito de Shannon de sigilo perfeito

basicamente dissemos que você sabe que dada uma cifra Dissemos a cifra tem perfeita

sigilo se dado duas mensagens do mesmo comprimento acontece que a distribuição

de textos cifrados. No entanto, se escolher uma chave aleatória e olharmos para a distribuição de

textos cifrados que criptografam M0 temos exatamente a mesma distribuição de quando nós

encrypt M1. A intuição aqui é que se a consultoria observa os textos cifrados

então ele não sabe se ele veio a partir da distribuição do resultado da criptografia

M0 ou veio da distribuição como o resultado de criptografar M1. E como um

resultado, ele não pode dizer se nós criptografado M0 ou M1. E isso é verdade para todos

mensagens do mesmo comprimento e como resultado, um atacante pobre não sabe

que a mensagem foi criptografada. Claro que já disse que esta definição é muito

forte no sentido de que requer chaves realmente longas se cifra tem curta

chaves não pode satisfazer esta definição em um fluxo cifras particulares

pode satisfazer essa definição. Ok, então vamos tentar enfraquecer a definição um pouco

e vamos pensar para o segmento anterior, e podemos dizer que em vez de exigir

as duas distribuições para ser absolutamente idênticas o que podemos exigir é, é que

duas distribuições apenas ser computacionalmente indistinguíveis. Em outras palavras, um pobre

atacante eficiente não é possível distinguir as duas distribuições mesmo que a

distribuições pode ser muito, muito, muito diferente. Que acaba de dar uma amostra para

uma distribuição e uma amostra para outra distribuição o atacante não pode dizer que

distribuição foi-lhe dada uma amostra. Acontece que esta definição é realmente

quase certo, mas ainda é um pouco forte demais, que ainda não pode ser satisfeita, de modo

temos de acrescentar mais uma restrição, e isso é que em vez de dizer que este

definição deveria ter mantenha durante toda a M0 e M1. É manter para pares somente M0 M1

que os atacantes podem realmente apresentam. Ok então isso realmente

nos leva à definição de segurança semântica. E assim, novamente, isso é semântica

segurança para uma chave de tempo em outras palavras, quando o atacante só é dada uma cifra

texto. E assim a nossa forma de definir a segurança semântica é através da definição de dois experimentos,

ok vamos definir 0 experimento e experimento 1. E, mais geralmente vamos

pensar neles como experimentos B parênteses, onde B pode ser zero ou um. Ok então o

forma o experimento é definido é o seguinte, temos um adversário que é

tentando quebrar o sistema. A um adversário, que é meio o análogo de estatística

testes no mundo de pseudo geradores aleatórios. E então o desafiante faz

o seguinte, então realmente temos dois adversários, mas os adversários são tão

semelhante que pode apenas descrevê-los como um desafio único que em um caso leva

bits de seus insumos definido para zero, e outro caso, leva seus insumos bits definidos como

um. E deixe-me mostrar-lhe o que esses challengers fazer. A primeira coisa que o

challenger vai fazer é que vai pegar uma chave aleatória e, em seguida, o adversário

basicamente está indo para a saída de duas mensagens M0 e M1. Ok então esta é uma explícita

par de mensagens que o atacante quer ser posta em causa e como de costume não estamos

tentando esconder o comprimento das mensagens, é necessário que as mensagens de ser igual

comprimento. E então o desafiante basicamente irá imprimir ou a criptografia de M0

ou a criptografia de M1, bem assim no experimento 0, o adversário será a saída

criptografia de M0. No experimento 1, a saída será o challenger de criptografia

de M1. Razoável de modo que a diferença entre as duas experiências. E então o

adversário é tentar adivinhar, basicamente, se ele foi dado a criptografia de M0

ou dada a criptografia de M1. Ok então aqui está um pouco de notação vamos

definir o Wb eventos para os eventos que um experimento B, a saída do adversário.

Ok então que é apenas um evento que, basicamente, em experimento de zero significa que W0

saída do adversário e um experimento em uma W1 significa a saída do adversário um. E

agora podemos definir a vantagem deste adversário, basicamente para dizer que este é

chamado a vantagem de segurança semântica do adversário Um contra o regime de E,

para ser a diferença de que a probabilidade de estes dois eventos. Em outras palavras, estamos

olhando se o adversário se comporta de maneira diferente, quando foi dada a

criptografia de M0 a partir de quando ele foi dada a criptografia de M1. E eu quero fazer

certeza que isso é claro que eu vou dizer isso mais uma vez. Então, em zero experimento era

dada a criptografia de M0 e na experiência que ele foi dado a criptografia

de M1. Agora nós estamos apenas interessados em saber se a saída de um adversário ou não.

... Nestas experiências. Se em ambos os experimentos a saída 1 com adversário

a mesma probabilidade que significa que o adversário não era capaz de distinguir o

dois experimentos. Experimentos de zero, basicamente, olha para o adversário, o mesmo

como a experiência de um, porque em ambos os casos carregar uma com a mesma probabilidade.

No entanto, se o adversário é capaz de produzir 1 em um experimento com significativa

probabilidade diferente do que em outro experimento, em seguida, o adversário era

realmente capaz de distinguir os dois experimentos. Ok então ... Para dizer isso mais

formalmente, essencialmente, a vantagem mais uma vez porque é a diferença de dois

probabilidades a vantagem é um número entre zero e um. Se a vantagem é

próximo de zero o que significa que o adversário não foi capaz de distinguir

nula experiência de um experimento. No entanto, se a vantagem está perto de uma,

isso significa que o adversário era muito bem capaz de distinguir a zero a partir de experimento

experimento um e que realmente significa que ele era capaz de distinguir uma criptografia

de M0 a partir de uma criptografia de M1, ok? Então essa é a definição. Na realidade

que é apenas a definição do partido ea definição é exatamente o que

que seria de esperar, basicamente, vamos dizer que um esquema de criptografia simétrica é

semanticamente seguro se para todos os adversários eficientes aqui eu vou colocá-las entre aspas

novamente, "Para todos os adversários eficientes a vantagem é insignificante." Em outras palavras,

adversário não eficiente pode distinguir a criptografia de M0 da criptografia

de M1 e basicamente este é o que diz repetidamente que, para estes dois

mensagens que o adversário foi capaz de mostrar que ele não era capaz de distinguir

mensagens que o adversário foi capaz de mostrar que ele não era capaz de distinguir

definição elegante. Pode não parecer tão imediato, mas eu quero mostrar-lhe algumas

implicações dessa definição e você verá exatamente por isso que a definição é o caminho

é. Ok, então vamos olhar alguns exemplos. Assim, o primeiro exemplo é supor

temos um esquema de criptografia quebrada, em outras palavras, suponha que temos um adversário Um

que de alguma forma dado o texto cifrado, ele é sempre capaz de deduzir menos

pouco significativa do texto simples. Ok então, dada a criptografia de M0, este adversário

é capaz de deduzir o bit menos significativo do M0. Então isso é um terrível

esquema de criptografia porque basicamente vazamentos o bit menos significativo do

texto simples apenas dado o texto cifrado. Então, eu quero mostrar-lhe que este regime é

, portanto, semanticamente seguro para esse tipo de mostra que se um sistema é semanticamente

assegurar que não há invasor deste tipo. Ok, então vamos ver porque é que o sistema

não semanticamente segura bem assim o que nós vamos fazer é basicamente nós vamos usar

adversário nosso que é capaz de aprender as partes de nosso mais insignificantes, vamos

usá-lo para quebrar a segurança semântico, vamos usá-lo para distinguir

usá-lo para quebrar a segurança semântico, vamos usá-lo para distinguir

B algoritmo, vamos ser algoritmo B e este B algoritmo vai usar

Um algoritmo em sua barriga. Ok então a primeira coisa que vai acontecer é de

curso o desafiante vai escolher uma chave aleatória. A primeira coisa que vai

acontecer é que nós precisamos para a saída de duas mensagens. As mensagens que vamos

para a saída, basicamente, vai ter pedaços significativos de forma diferente. Assim, um

mensagem vai terminar com zero e uma mensagem vai acabar com um. Agora, o que

é o adversário vai fazer? O challenger vai nos dar a

criptografia de qualquer M0 ou M1, dependendo se na experiência 0 ou

no experimento 1. E então nós apenas transmitir a presente texto cifrado para o adversário

bem assim o adversário A. Agora, qual é a propriedade de um adversário? Dada a cifra

texto adversário, A pode nos dizer o que os bits menos significativos do texto simples é.

Em outras palavras, o adversário vai para a saída dos bits menos significativos de M0 ou M1

mas baixa e eis que é basicamente o B. bit E então nós somos apenas

indo para a saída que, como nosso convidado então vamos? s chamar essa coisa B principal Ok então agora este

descreve o adversário segurança semântica. E agora você me dizer o que é a semântica

vantagem de segurança deste adversário? Bem, então vamos ver. Em zero experimento, o que é

a probabilidade de que B gera um adversário? Bem em zero de experiência, é sempre

dada a criptografia de M zero e, portanto, um adversário sempre é a saída do

bit menos significativo do M zero, o que sempre acontece de ser zero. No experimento

zero, B sempre envia zero. Assim, a probabilidade de que produz uma é zero.

No entanto, em um experimento, estamos dado a criptografia de M1. Então, como é provável

B adversário para a saída de um experimento em um poço que sempre envia uma, mais uma vez por

as propriedades de algoritmo A e, por conseguinte, a vantagem é basicamente um.

Portanto, esta é uma grande vantagem, é tão grande quanto ele vai chegar. O que significa que este

adversário quebrou completamente o sistema. Ok então nós consideramos, portanto, sob semântica

segurança, basicamente, apenas deduzir o bit menos significativo é o suficiente para completamente

quebrar o sistema em uma definição de segurança semântica. Ok, agora o interessante

coisa aqui, claro, é que este não é apenas sobre o bit menos significativo, em

fato de a mensagem, por exemplo, o bit mais significativo, você sabe

bit número sete Talvez o XOR de todos os bits da mensagem e assim por diante

e assim por diante qualquer tipo de informação, qualquer pouco sobre o texto simples que pode ser

aprendeu basicamente significa que o sistema não é semanticamente seguro. Assim

basicamente tudo o que o adversário teria que fazer seria chegar com duas mensagens

M0 e M1 tal que, sob uma coisa que aprendi é o valor zero e, em seguida,

coisa a outra, o valor, é um deles. Por exemplo, se um era capaz de aprender a XOR

bits da mensagem, em seguida, M0 e M1 teria apenas diferente

XOR para todos os bits de suas mensagens e, em seguida, este seria um adversário

também ser suficiente para quebrar a segurança semântica. Ok então, basicamente para criptografia

é semanticamente seguro então nenhum bit de informação é revelada a um

adversário eficiente. Ok então este é exatamente um conceito de sigilo perfeito só

aplicada adversários apenas eficientes, em vez de todos os adversários. Assim, a próxima

coisa que eu quero mostrar é que na verdade o teclado uma vez, de facto, é

semanticamente seguro, é melhor ser semanticamente seguro porque é de fato,

é mais do que isso é perfeitamente seguro. Então, vamos ver por que isso é verdade. Bem assim

de novo, é uma dessas experiências, assim supor que temos um adversário que alega

para quebrar a segurança semântica do bloco de uma vez. O adversário é o primeiro vai fazer

é que ele vai de saída duas mensagens M0 e M1 do mesmo comprimento.

Agora o que ele voltar como um desafio? Como um desafio, ele recebe a criptografia do

de M0 ou a criptografia de M1 sob a almofada de uma vez.

E ele está tentando fazer a distinção entre esses dois textos cifrados possíveis que ele recebe, certo?

No experimento zero, ele recebe a criptografia de M0 e no experimento um, ele recebe o

criptografia de M1. Bem então deixe-me perguntar-lhe, então qual é a vantagem do adversário

Um contra a patente tempo um? Então eu me lembro que a propriedade dos que eu

tinha é que, que K, XOR M0 é distribuído de forma idêntica ao K, XOR M1.

Em outras palavras, essas distribuições são a distribuição absolutamente idênticos,

distribuições, idênticos. Esta é uma propriedade do XOR. Se XOR a almofada aleatória

K com qualquer coisa, seja M0 ou M1, temos uma distribuição uniforme. Assim, em ambos

casos, algoritmo A é dado como entrada no exactamente a mesma distribuição. Talvez o

distribuição uniforme em textos cifrados. E, portanto, vai se comportar exatamente o

mesma em ambos os casos, porque foi dada a distribuição exacta como entrada. E como um

resultado, a sua vantagem é zero, o que significa que a almofada de uma única vez é semanticamente

seguro. Agora a coisa interessante aqui não é só é semanticamente seguro, é

semanticamente seguro para todos os adversários. Nós nem sequer tem que restringir o

adversários para ser eficiente. Sem adversário, não importa o quão inteligente você é, não

adversário será capaz de distinguir K XOR M0 a partir de K XOR M1 porque os dois

distribuições são idênticos. Ok, então o bloco de uma vez é semanticamente seguro. Ok,

assim que completa a nossa definição de segurança semântico, a próxima coisa que nós estamos

vai fazer é provar para o PRG seguro, de fato implica que a cifra de fluxo é

semanticamente seguro.