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
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
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.