0:00:00.000,0:00:04.134
Portanto, agora que entendemos o que é um PRG é seguro, e nós entendemos que semântica

0:00:04.134,0:00:08.425
significa segurança, possamos realmente argumentam que uma cifra de fluxo com um PRG seguro é, em

0:00:08.425,0:00:12.559
facto, uma semanticamente seguro. Então essa é a nossa meta para este, o segmento. É uma forma justa

0:00:12.559,0:00:16.746
prova simples, e vamos ver como ele vai. Assim, a teoria que quero provar é

0:00:16.746,0:00:20.932
que, basicamente, dado um gerador G que passa a ser um seguro, psedo-aleatório

0:00:20.932,0:00:24.805
gerador. Na verdade, a codificação de fluxo que é derivado a partir deste gerador é

0:00:24.805,0:00:28.924
vai ser semanticamente seguro. Ok, e eu quero enfatizar. Que não houve

0:00:28.924,0:00:33.085
esperança de provar um teorema como este para sigilo total. Para conceito de Shannon

0:00:33.085,0:00:37.193
sigilo total. Porque sabemos que uma cifra de fluxo não pode ser perfeitamente

0:00:37.193,0:00:41.264
seguro porque tem chaves curtas. E o segredo perfeito requer que as chaves ser tão

0:00:41.264,0:00:45.321
desde que a mensagem. Portanto, este é realmente o tipo do primeiro exemplo que vemos onde

0:00:45.321,0:00:49.229
somos capazes de provar que uma cifra com chaves curtas tem segurança. O conceito de

0:00:49.229,0:00:53.236
de segurança é a segurança semântica. E isso realmente confirma que, realmente, este é um

0:00:53.236,0:00:56.943
conceito muito útil. E, na verdade, você sabe, nós estaremos usando a segurança semântica

0:00:56.943,0:01:00.750
muitas e muitas vezes ao longo do curso. Ok, então como é que vamos provar uma teoria como a

0:01:00.750,0:01:04.257
isso? O que estamos realmente vai fazer, é que nós vamos estar provando a

0:01:04.257,0:01:08.264
contrapositive. O que vamos mostrar é o seguinte. Então, nós vamos provar isso

0:01:08.264,0:01:12.815
declaração aqui, mas deixe-me analisá-lo para você. Suponha. Você me dá uma semântica

0:01:12.815,0:01:18.345
A. adversário de segurança que nós vamos fazer é que vamos construir B adversário PRG para satisfazer

0:01:18.345,0:01:23.686
desigualdade isso aqui. Agora porque é que esta desigualdade é útil? Basicamente o que nós

0:01:23.686,0:01:28.878
sabe? Sabemos que, se B é um adversário eficiente. Então sabemos que desde que G é um

0:01:28.878,0:01:33.053
gerador seguro, sabemos que essa vantagem é insignificante, certo? Um seguro

0:01:33.053,0:01:37.510
gerador tem uma vantagem negligenciável contra qualquer teste estatístico eficaz. Assim

0:01:37.510,0:01:42.023
do lado direito, basicamente, vai ser insignificante. Mas porque a mão direita

0:01:42.023,0:01:46.023
lado é desprezível, podemos deduzir que o lado esquerdo é desprezível.

0:01:46.023,0:01:50.767
E, portanto, o adversário que você olhou realmente tem vantagem insignificante em

0:01:50.767,0:01:54.538
atacando o fluxo cifra E. Certo. Então é assim que isso, isso vai funcionar.

0:01:54.538,0:01:58.486
Basicamente tudo o que temos a fazer é dado um adversário Um vamos construir uma

0:01:58.486,0:02:02.591
B. adversário Sabemos que B tem a vantagem insignificante contra gerador, mas que

0:02:02.591,0:02:06.036
implica que A tem vantagem contra o insignificante cifra de fluxo.

0:02:06.082,0:02:10.994
Então vamos fazer isso. Então, tudo o que temos de fazer de novo é dado A, temos que construir B.

0:02:10.994,0:02:15.183
Então deixe A ser um adversário de segurança semântica contra a cifra de fluxo. Então deixe-me lembrá-lo

0:02:15.183,0:02:19.320
que isso significa. Basicamente, há um challenger. O desafiante começa por

0:02:19.320,0:02:23.509
escolher a chave K. E então o adversário está indo saída duas mensagens, duas iguais

0:02:23.509,0:02:27.383
mensagens de comprimento. E ele vai receber a criptografia de M0 ou M1

0:02:27.383,0:02:31.226
e B1 saídas. Ok, isso é o que é um adversário de segurança semântica é

0:02:31.226,0:02:34.933
vai fazer. Então agora vamos começar a jogar com este adversário. E

0:02:34.933,0:02:38.498
é assim que vamos provar o nosso lema. Tudo bem, então a primeira coisa

0:02:38.498,0:02:42.535
vamos fazer é que nós vamos fazer o desafiante. Também escolher um aleatório R.

0:02:42.535,0:02:47.500
Ok, uma seqüência aleatória R. Então, bem, você sabe que o adversário realmente não importa o que o

0:02:47.500,0:02:52.405
challenger faz internamente. O desafiante nunca usa R, e isso não afeta a

0:02:52.405,0:02:56.365
vantagem do adversário em tudo. O adversário simplesmente não se importa que o

0:02:56.365,0:03:00.706
challenger também pega R. Mas agora vem o truque. O que vamos fazer é que estamos

0:03:00.706,0:03:05.042
vai, em vez de criptografar usando GK. Estamos indo para criptografar usando R. Você pode

0:03:05.042,0:03:09.993
ver basicamente o que estamos fazendo aqui. Essencialmente, estamos mudando a

0:03:09.993,0:03:14.219
challenger então agora o texto cifrado desafio é criptografado utilizando uma

0:03:14.219,0:03:19.006
almofada verdadeiramente aleatório. Em oposição a GK almofada apenas pseudo aleatória. Okay. Agora, a propriedade de

0:03:19.006,0:03:23.639
o gerador pseudo-aleatório é que a sua saída é indistinguível da verdadeiramente

0:03:23.639,0:03:28.273
aleatória. Então, porque o PRG é seguro, o adversário não pode dizer que fizemos este

0:03:28.273,0:03:33.082
mudança. O adversário não pode dizer que nós mudamos de uma seqüência pseudo-aleatório para uma

0:03:33.082,0:03:37.422
seqüência verdadeiramente aleatória. Mais uma vez, porque o gerador é segura. Bem, mas agora olhar para

0:03:37.422,0:03:41.762
do jogo que terminou com. Assim, a vantagem do adversário não poderia ter

0:03:41.762,0:03:46.630
mudou por muito, porque ele não pode dizer a diferença. Mas agora olhar para o jogo que

0:03:46.630,0:03:51.073
acabamos com ele. Agora este jogo é realmente um jogo de time pad. Este semântico de um

0:03:51.073,0:03:55.803
jogo contra a almofada de segurança uma vez. Porque agora o adversário está a ficar um

0:03:55.803,0:04:00.238
criptografia pad tempo de M0 ou M1 Mas no bloco uma vez que sabemos que os adversários

0:04:00.238,0:04:04.048
vantagem é zero, porque você não pode bater o bloco de uma vez. A almofada de tempo um é

0:04:04.048,0:04:08.165
garantir incondicionalmente segura. E, como resultado, por causa disso. Essencialmente

0:04:08.165,0:04:12.674
porque o adversário não poderia ter dito a diferença quando

0:04:12.674,0:04:17.013
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

0:04:17.013,0:04:21.411
não poderia ganhar o jogo sudo aleatória. E, como resultado, a cifra de fluxo, o original

0:04:21.411,0:04:25.634
cifra de fluxo deve ser seguro. Então essa é a intuição de como a prova vai passar.

0:04:25.634,0:04:29.594
Mas eu quero fazê-lo rigorosamente uma vez. A partir de agora, nós estamos apenas vai argumentar por

0:04:29.594,0:04:33.975
jogar com o nosso adversário. E, não vamos estar fazendo coisas tão formal como eu sou

0:04:33.975,0:04:38.304
vai fazer a seguir. Mas eu quero fazer formalmente e precisamente uma vez, apenas para que você veja como

0:04:38.304,0:04:42.629
essas provas realmente funcionar. Ok, então eu vou ter que introduzir alguma notação. E

0:04:42.629,0:04:47.751
eu vou fazer a notação usual, basicamente. Se a semântica originais estão aqui no

0:04:47.751,0:04:52.937
início, quando na verdade estamos usando uma almofada de pseudo-aleatório, eu vou usar W0 e W1

0:04:52.937,0:04:58.059
para denotar o caso em que o adversário produz um, quando se obtém o criptografia

0:04:58.059,0:05:02.856
de M0, ou se a criptografia de M1, respectivamente. Ok? Assim, corresponde a W0

0:05:02.856,0:05:07.719
saída 1 quando receber a criptografia de M0. E W1 corresponde

0:05:07.719,0:05:13.141
para a saída 1 quando receber a criptografia de M1. Então esse é o padrão

0:05:13.141,0:05:19.606
definição de segurança semântica. Agora, depois de jogarmos para a plataforma de forma aleatória. Eu vou usar

0:05:19.606,0:05:24.505
R0 e R1 para denotar o caso em que o adversário produz um ao receber o

0:05:24.505,0:05:29.125
criptografia pad um tipo de M0 ou a criptografia one-time pad de M1. Portanto, temos

0:05:29.125,0:05:33.567
quatro eventos, W0, W1 do jogo original semmantics segurança, e R0 e R1

0:05:33.567,0:05:38.365
do jogo semmantics segurança, uma vez que mudar para o one-time pad. Então agora

0:05:38.365,0:05:42.985
vamos olhar para as relações entre essas variáveis. Então, em primeiro lugar, R0 e R1 são

0:05:42.985,0:05:47.427
basicamente eventos de um jogo contra um segurança semmantics one-time pad. Assim

0:05:47.427,0:05:51.929
diferença entre essas probabilidades é que, como dissemos, basicamente o

0:05:51.929,0:05:56.902
vantagem do algoritmo de A, de adversário A, contra a almofada de uma só vez. Que sabemos que é

0:05:56.902,0:06:01.231
zero. Ok, então isso é ótimo. Então, que basicamente significa que a probabilidade de, de R0

0:06:01.231,0:06:05.662
é igual à probabilidade de R1. Então, agora, vamos colocar esses eventos em uma linha, em um

0:06:05.662,0:06:10.261
segmento de linha entre zero e um. Então aqui estão os eventos. W0 e W1 são os eventos

0:06:10.261,0:06:14.499
que está interessado em nós quer mostrar que estes dois são próximos. Okay. E o caminho

0:06:14.499,0:06:18.490
nós vamos fazer é basicamente mostrando, oh e eu devo dizer, aqui é

0:06:18.490,0:06:22.754
probabilidade R0 e R1, ele diz que ambos são mesmo, eu só colocá-los no

0:06:22.754,0:06:27.237
mesmo lugar. O que vamos fazer é que nós vamos mostrar que tanto o W0 e W1 estão

0:06:27.237,0:06:31.720
realmente fechar à probabilidade de RB e como resultado, eles devem ser perto de uma

0:06:31.720,0:06:35.656
outro. Ok, então a nossa forma de fazer isso é usando uma segunda alegação, por isso agora estamos

0:06:35.656,0:06:39.865
interessada na distância entre a probabilidade de Wb ea probabilidade de

0:06:39.865,0:06:44.730
Rb. Ok, então vamos provar a afirmação em um segundo. Deixe-me afirmar a alegação. O

0:06:44.730,0:06:49.938
reivindicação diz que não existe no B. adversário tal que a diferença destes dois

0:06:49.938,0:06:55.081
probabilidades é basicamente a vantagem de B contra o gerador G e este é

0:06:55.081,0:06:59.833
para ambos b do. Ok? Assim, dadas estas duas afirmações, como o teorema é feito porque

0:06:59.833,0:07:04.771
, basicamente, o que sabemos. Sabemos que esta distância é menor que a vantagem de B

0:07:04.771,0:07:09.523
contra G. É de reivindicação dois e similar, essa distância é, na verdade mesmo

0:07:09.523,0:07:14.401
igual, eu não vou dizer menos, mas é igual à vantagem. De B

0:07:14.401,0:07:19.455
contra G, e como resultado você pode ver que a distância entre W0 e W1

0:07:19.455,0:07:24.446
é, basicamente, quase duas vezes a vantagem de B contra G. Isso é basicamente

0:07:24.446,0:07:29.375
coisa o que estamos tentando provar. Ok, a única coisa que resta é apenas

0:07:29.375,0:07:34.304
provar esta afirmação dois e se você pensar sobre o que afirmam dois diz, basicamente,

0:07:34.304,0:07:39.170
capta a questão do que acontece em zero experimento o que acontece quando

0:07:39.170,0:07:43.530
substituir o GK pad pseudo-aleatório, por verdadeiramente aleatório pad R. Aqui em

0:07:43.530,0:07:48.910
nula experiência diz que nós estamos usando o teclado de pseudo-aleatório e aqui em zero experimento

0:07:48.910,0:07:53.593
estiver usando uma almofada verdadeiramente aleatório e estamos pedindo o adversário pode dizer a

0:07:53.593,0:07:58.972
diferença entre estes dois e queremos argumentar que ele não pode porque o gerador

0:07:58.972,0:08:03.845
é segura. Ok então aqui está o que nós vamos fazer. Então, vamos provar alegação dois. Então, nós

0:08:03.845,0:08:08.728
vão argumentar que, na verdade existe um adversário B PRG que tem exatamente o

0:08:08.728,0:08:13.764
diferença das duas probabilidades como sua vantagem. Ok e desde o ponto de

0:08:13.764,0:08:18.319
é uma vez que este é negligenciável este é negligenciável. E isso é basicamente o que nós

0:08:18.319,0:08:22.323
queria provar. Ok, então vamos olhar para o b teste estatístico. Então, o que, a nossa

0:08:22.323,0:08:26.514
b teste estatístico vai usar um adversário em sua barriga, assim que nós começamos a construir

0:08:26.514,0:08:31.091
b teste estatístico no entanto que queremos. Como dissemos, vai usar um adversário dentro de

0:08:31.091,0:08:35.558
que, para o seu funcionamento, e é um teste estatístico regular, por isso leva um pouco n-

0:08:35.558,0:08:39.694
string como insumos, e que é suposto para a saída, você sabe, aleatória ou não aleatória,

0:08:39.694,0:08:43.995
zero ou um. Ok, então vamos ver. Então é, a primeira coisa que vai fazer, é que vai

0:08:43.995,0:08:48.407
adversário corrida A, e um adversário está indo saída duas mensagens, M0 e M1. E, em seguida,

0:08:48.407,0:08:54.053
que adversário b vai fazer, é basicamente vai responder. Com M0 XOR ou a cadeia que

0:08:54.053,0:08:59.942
foi dado como entradas. Certo? Essa é a lição de estatística, então. Sempre que um

0:08:59.942,0:09:05.418
saídas, que vai de saída, a sua saída. E agora vamos olhar para a sua vantagem. Assim

0:09:05.418,0:09:10.477
, o que podemos dizer sobre a vantagem deste teste estatístico contra o

0:09:10.477,0:09:15.606
gerador? Bem, então por definição, é a probabilidade de que, se você escolher um

0:09:15.606,0:09:20.527
seqüência verdadeiramente aleatória. Então, aqui estão 01 para o N, então a probabilidade

0:09:20.527,0:09:25.587
que R, que B gera menos 1 a probabilidade, é que quando escolhemos um

0:09:25.587,0:09:32.603
pseudo-aleatório string, B saídas 1, ok? Ok, mas vamos pensar sobre o que é isso.

0:09:32.603,0:09:37.398
O que você pode me dizer sobre as primeiras expressões? O que você pode me dizer sobre

0:09:37.398,0:09:42.256
essa expressão por aqui? Bem, pela definição do que é exatamente se você acha

0:09:42.256,0:09:47.366
sobre o que está acontecendo aqui, que é essa é exatamente a probabilidade direito R0?

0:09:47.366,0:09:52.729
Porque este jogo que estamos jogando com o adversário aqui é, basicamente, ele ajudou a

0:09:52.729,0:09:58.028
nos M0 e M1 aqui ele ajudou a adicionar M0 e M1 e ele teve a criptografia

0:09:58.028,0:10:03.919
de M0 sob verdadeiramente pad vez. Ok, então esta é basicamente uma [inaudível]. Aqui

0:10:03.919,0:10:10.214
deixe-me escrever isto um pouco melhor. Essa é a probabilidade de nível básico de R0.

0:10:10.660,0:10:15.467
Agora, o que podemos dizer sobre a próxima expressão, bem o que podemos dizer sobre

0:10:15.467,0:10:19.100
quando B é dado um Y cadeia pseudo-aleatório como entrada.

0:10:19.100,0:10:23.493
Bem, nesse caso, este é exatamente o experimento jogo cifra zero e verdadeira corrente

0:10:23.493,0:10:29.999
porque agora estamos computando M XOR M0, XOR GK. Isto é exatamente o W0.

0:10:29.999,0:10:33.015
Ok, isso é exatamente o que temos de provar. Portanto, é uma espécie de prova trivial.

0:10:33.015,0:10:39.563
Ok, então que completa a prova da alegação dois. E, novamente, só para ter certeza tudo isso é claro, uma vez que temos

0:10:39.563,0:10:43.799
alegação dois, sabemos que W0 deve estar perto de W1, e esse é o teorema.

0:10:43.814,0:10:50.383
Isso é o que temos de provar. Ok, então agora nós estabelecemos que uma cifra de fluxo é em

0:10:50.383,0:10:53.880
fato symmantically seguro, assumindo que o PRG é segura.