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.