Portanto, agora que entendemos o que é um PRG é seguro, e nós entendemos que semântica
significa segurança, possamos realmente argumentam que uma cifra de fluxo com um PRG seguro é, em
facto, uma semanticamente seguro. Então essa é a nossa meta para este, o segmento. É uma forma justa
prova simples, e vamos ver como ele vai. Assim, a teoria que quero provar é
que, basicamente, dado um gerador G que passa a ser um seguro, psedo-aleatório
gerador. Na verdade, a codificação de fluxo que é derivado a partir deste gerador é
vai ser semanticamente seguro. Ok, e eu quero enfatizar. Que não houve
esperança de provar um teorema como este para sigilo total. Para conceito de Shannon
sigilo total. Porque sabemos que uma cifra de fluxo não pode ser perfeitamente
seguro porque tem chaves curtas. E o segredo perfeito requer que as chaves ser tão
desde que a mensagem. Portanto, este é realmente o tipo do primeiro exemplo que vemos onde
somos capazes de provar que uma cifra com chaves curtas tem segurança. O conceito de
de segurança é a segurança semântica. E isso realmente confirma que, realmente, este é um
conceito muito útil. E, na verdade, você sabe, nós estaremos usando a segurança semântica
muitas e muitas vezes ao longo do curso. Ok, então como é que vamos provar uma teoria como a
isso? O que estamos realmente vai fazer, é que nós vamos estar provando a
contrapositive. O que vamos mostrar é o seguinte. Então, nós vamos provar isso
declaração aqui, mas deixe-me analisá-lo para você. Suponha. Você me dá uma semântica
A. adversário de segurança que nós vamos fazer é que vamos construir B adversário PRG para satisfazer
desigualdade isso aqui. Agora porque é que esta desigualdade é útil? Basicamente o que nós
sabe? Sabemos que, se B é um adversário eficiente. Então sabemos que desde que G é um
gerador seguro, sabemos que essa vantagem é insignificante, certo? Um seguro
gerador tem uma vantagem negligenciável contra qualquer teste estatístico eficaz. Assim
do lado direito, basicamente, vai ser insignificante. Mas porque a mão direita
lado é desprezível, podemos deduzir que o lado esquerdo é desprezível.
E, portanto, o adversário que você olhou realmente tem vantagem insignificante em
atacando o fluxo cifra E. Certo. Então é assim que isso, isso vai funcionar.
Basicamente tudo o que temos a fazer é dado um adversário Um vamos construir uma
B. adversário Sabemos que B tem a vantagem insignificante contra gerador, mas que
implica que A tem vantagem contra o insignificante cifra de fluxo.
Então vamos fazer isso. Então, tudo o que temos de fazer de novo é dado A, temos que construir B.
Então deixe A ser um adversário de segurança semântica contra a cifra de fluxo. Então deixe-me lembrá-lo
que isso significa. Basicamente, há um challenger. O desafiante começa por
escolher a chave K. E então o adversário está indo saída duas mensagens, duas iguais
mensagens de comprimento. E ele vai receber a criptografia de M0 ou M1
e B1 saídas. Ok, isso é o que é um adversário de segurança semântica é
vai fazer. Então agora vamos começar a jogar com este adversário. E
é assim que vamos provar o nosso lema. Tudo bem, então a primeira coisa
vamos fazer é que nós vamos fazer o desafiante. Também escolher um aleatório R.
Ok, uma seqüência aleatória R. Então, bem, você sabe que o adversário realmente não importa o que o
challenger faz internamente. O desafiante nunca usa R, e isso não afeta a
vantagem do adversário em tudo. O adversário simplesmente não se importa que o
challenger também pega R. Mas agora vem o truque. O que vamos fazer é que estamos
vai, em vez de criptografar usando GK. Estamos indo para criptografar usando R. Você pode
ver basicamente o que estamos fazendo aqui. Essencialmente, estamos mudando a
challenger então agora o texto cifrado desafio é criptografado utilizando uma
almofada verdadeiramente aleatório. Em oposição a GK almofada apenas pseudo aleatória. Okay. Agora, a propriedade de
o gerador pseudo-aleatório é que a sua saída é indistinguível da verdadeiramente
aleatória. Então, porque o PRG é seguro, o adversário não pode dizer que fizemos este
mudança. O adversário não pode dizer que nós mudamos de uma seqüência pseudo-aleatório para uma
seqüência verdadeiramente aleatória. Mais uma vez, porque o gerador é segura. Bem, mas agora olhar para
do jogo que terminou com. Assim, a vantagem do adversário não poderia ter
mudou por muito, porque ele não pode dizer a diferença. Mas agora olhar para o jogo que
acabamos com ele. Agora este jogo é realmente um jogo de time pad. Este semântico de um
jogo contra a almofada de segurança uma vez. Porque agora o adversário está a ficar um
criptografia pad tempo de M0 ou M1 Mas no bloco uma vez que sabemos que os adversários
vantagem é zero, porque você não pode bater o bloco de uma vez. A almofada de tempo um é
garantir incondicionalmente segura. E, como resultado, por causa disso. Essencialmente
porque o adversário não poderia ter dito a diferença quando
nos mudamos de pseudo aleatórios para aleatório. Mas ele não podia ganhar o jogo aleatório. Isso também significa que ele
não poderia ganhar o jogo sudo aleatória. E, como resultado, a cifra de fluxo, o original
cifra de fluxo deve ser seguro. Então essa é a intuição de como a prova vai passar.
Mas eu quero fazê-lo rigorosamente uma vez. A partir de agora, nós estamos apenas vai argumentar por
jogar com o nosso adversário. E, não vamos estar fazendo coisas tão formal como eu sou
vai fazer a seguir. Mas eu quero fazer formalmente e precisamente uma vez, apenas para que você veja como
essas provas realmente funcionar. Ok, então eu vou ter que introduzir alguma notação. E
eu vou fazer a notação usual, basicamente. Se a semântica originais estão aqui no
início, quando na verdade estamos usando uma almofada de pseudo-aleatório, eu vou usar W0 e W1
para denotar o caso em que o adversário produz um, quando se obtém o criptografia
de M0, ou se a criptografia de M1, respectivamente. Ok? Assim, corresponde a W0
saída 1 quando receber a criptografia de M0. E W1 corresponde
para a saída 1 quando receber a criptografia de M1. Então esse é o padrão
definição de segurança semântica. Agora, depois de jogarmos para a plataforma de forma aleatória. Eu vou usar
R0 e R1 para denotar o caso em que o adversário produz um ao receber o
criptografia pad um tipo de M0 ou a criptografia one-time pad de M1. Portanto, temos
quatro eventos, W0, W1 do jogo original semmantics segurança, e R0 e R1
do jogo semmantics segurança, uma vez que mudar para o one-time pad. Então agora
vamos olhar para as relações entre essas variáveis. Então, em primeiro lugar, R0 e R1 são
basicamente eventos de um jogo contra um segurança semmantics one-time pad. Assim
diferença entre essas probabilidades é que, como dissemos, basicamente o
vantagem do algoritmo de A, de adversário A, contra a almofada de uma só vez. Que sabemos que é
zero. Ok, então isso é ótimo. Então, que basicamente significa que a probabilidade de, de R0
é igual à probabilidade de R1. Então, agora, vamos colocar esses eventos em uma linha, em um
segmento de linha entre zero e um. Então aqui estão os eventos. W0 e W1 são os eventos
que está interessado em nós quer mostrar que estes dois são próximos. Okay. E o caminho
nós vamos fazer é basicamente mostrando, oh e eu devo dizer, aqui é
probabilidade R0 e R1, ele diz que ambos são mesmo, eu só colocá-los no
mesmo lugar. O que vamos fazer é que nós vamos mostrar que tanto o W0 e W1 estão
realmente fechar à probabilidade de RB e como resultado, eles devem ser perto de uma
outro. Ok, então a nossa forma de fazer isso é usando uma segunda alegação, por isso agora estamos
interessada na distância entre a probabilidade de Wb ea probabilidade de
Rb. Ok, então vamos provar a afirmação em um segundo. Deixe-me afirmar a alegação. O
reivindicação diz que não existe no B. adversário tal que a diferença destes dois
probabilidades é basicamente a vantagem de B contra o gerador G e este é
para ambos b do. Ok? Assim, dadas estas duas afirmações, como o teorema é feito porque
, basicamente, o que sabemos. Sabemos que esta distância é menor que a vantagem de B
contra G. É de reivindicação dois e similar, essa distância é, na verdade mesmo
igual, eu não vou dizer menos, mas é igual à vantagem. De B
contra G, e como resultado você pode ver que a distância entre W0 e W1
é, basicamente, quase duas vezes a vantagem de B contra G. Isso é basicamente
coisa o que estamos tentando provar. Ok, a única coisa que resta é apenas
provar esta afirmação dois e se você pensar sobre o que afirmam dois diz, basicamente,
capta a questão do que acontece em zero experimento o que acontece quando
substituir o GK pad pseudo-aleatório, por verdadeiramente aleatório pad R. Aqui em
nula experiência diz que nós estamos usando o teclado de pseudo-aleatório e aqui em zero experimento
estiver usando uma almofada verdadeiramente aleatório e estamos pedindo o adversário pode dizer a
diferença entre estes dois e queremos argumentar que ele não pode porque o gerador
é segura. Ok então aqui está o que nós vamos fazer. Então, vamos provar alegação dois. Então, nós
vão argumentar que, na verdade existe um adversário B PRG que tem exatamente o
diferença das duas probabilidades como sua vantagem. Ok e desde o ponto de
é uma vez que este é negligenciável este é negligenciável. E isso é basicamente o que nós
queria provar. Ok, então vamos olhar para o b teste estatístico. Então, o que, a nossa
b teste estatístico vai usar um adversário em sua barriga, assim que nós começamos a construir
b teste estatístico no entanto que queremos. Como dissemos, vai usar um adversário dentro de
que, para o seu funcionamento, e é um teste estatístico regular, por isso leva um pouco n-
string como insumos, e que é suposto para a saída, você sabe, aleatória ou não aleatória,
zero ou um. Ok, então vamos ver. Então é, a primeira coisa que vai fazer, é que vai
adversário corrida A, e um adversário está indo saída duas mensagens, M0 e M1. E, em seguida,
que adversário b vai fazer, é basicamente vai responder. Com M0 XOR ou a cadeia que
foi dado como entradas. Certo? Essa é a lição de estatística, então. Sempre que um
saídas, que vai de saída, a sua saída. E agora vamos olhar para a sua vantagem. Assim
, o que podemos dizer sobre a vantagem deste teste estatístico contra o
gerador? Bem, então por definição, é a probabilidade de que, se você escolher um
seqüência verdadeiramente aleatória. Então, aqui estão 01 para o N, então a probabilidade
que R, que B gera menos 1 a probabilidade, é que quando escolhemos um
pseudo-aleatório string, B saídas 1, ok? Ok, mas vamos pensar sobre o que é isso.
O que você pode me dizer sobre as primeiras expressões? O que você pode me dizer sobre
essa expressão por aqui? Bem, pela definição do que é exatamente se você acha
sobre o que está acontecendo aqui, que é essa é exatamente a probabilidade direito R0?
Porque este jogo que estamos jogando com o adversário aqui é, basicamente, ele ajudou a
nos M0 e M1 aqui ele ajudou a adicionar M0 e M1 e ele teve a criptografia
de M0 sob verdadeiramente pad vez. Ok, então esta é basicamente uma [inaudível]. Aqui
deixe-me escrever isto um pouco melhor. Essa é a probabilidade de nível básico de R0.
Agora, o que podemos dizer sobre a próxima expressão, bem o que podemos dizer sobre
quando B é dado um Y cadeia pseudo-aleatório como entrada.
Bem, nesse caso, este é exatamente o experimento jogo cifra zero e verdadeira corrente
porque agora estamos computando M XOR M0, XOR GK. Isto é exatamente o W0.
Ok, isso é exatamente o que temos de provar. Portanto, é uma espécie de prova trivial.
Ok, então que completa a prova da alegação dois. E, novamente, só para ter certeza tudo isso é claro, uma vez que temos
alegação dois, sabemos que W0 deve estar perto de W1, e esse é o teorema.
Isso é o que temos de provar. Ok, então agora nós estabelecemos que uma cifra de fluxo é em
fato symmantically seguro, assumindo que o PRG é segura.