cifras de fluxo são semanticamente seguro (11 min)

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.