WEBVTT

00:00:00.000 --> 00:00:04.388
Neste segmento perguntamos se podemos construir a partir de cifras de bloco simples

00:00:04.388 --> 00:00:09.456
primitivos como pseudo geradores aleatórios. A resposta é sim. Então, para começar, vamos

00:00:09.456 --> 00:00:14.215
perguntar se podemos construir pseudo funções aleatórias em vez de pseudo-aleatório

00:00:14.215 --> 00:00:18.789
permutações de um gerador pseudo-aleatório. Podemos construir um PRF de um PRG?

00:00:18.789 --> 00:00:23.873
Nosso objetivo final que é construir uma cifra de bloco que é um PRP. E nós vamos chegar

00:00:23.873 --> 00:00:29.130
a que, no final. Ok, agora vamos construir um PRF. Então vamos começar com um PRG que

00:00:29.130 --> 00:00:34.590
dobra suas entradas de modo as sementes para o PRG é um elemento em K ea saída é

00:00:34.590 --> 00:00:39.420
, na verdade, dois elementos em K. Portanto, aqui temos um esquema do gerador, que

00:00:39.420 --> 00:00:44.296
basicamente tem sua entrada de C e K, e saídas de dois elementos, em K, como sua saída.

00:00:44.296 --> 00:00:48.992
E agora o que significa para essa pureza para ser seguro, lembre-se isto significa que

00:00:48.992 --> 00:00:52.965
essencialmente a saída é indistinguível de um elemento aleatório

00:00:52.965 --> 00:00:58.355
dentro de K quadrado Agora verifica-se que é muito fácil definir basicamente o que é

00:00:58.355 --> 00:01:03.455
chamado uma PRF bit um a partir deste PRG. Então, o que é um pouco um PRF é basicamente um PRF

00:01:03.455 --> 00:01:08.360
domínio que é apenas um bit. Ok, então é um PRF que só leva um pouco como

00:01:08.360 --> 00:01:13.461
de entrada. Ok, ea forma como vamos fazê-lo é que vai dizer é se o X bit de entrada é zero

00:01:13.461 --> 00:01:18.627
eu vou colocar a saída esquerda e se o bit de entrada X é um, então eu vou colocar o direito

00:01:18.627 --> 00:01:23.678
saída do PRF. Ok, em símbolos, temos basicamente o que escrevi aqui. Agora

00:01:23.678 --> 00:01:28.523
é simples para mostrar que, de facto, G é um PRG segura, então este bit PRF um é

00:01:28.523 --> 00:01:32.901
, de facto, uma PRF seguro. Se você pensar nisso por um segundo, isso realmente não é

00:01:32.901 --> 00:01:37.571
[inaudível]. É realmente apenas afirmando a mesma coisa duas vezes. Então eu vou deixá-lo por

00:01:37.571 --> 00:01:42.241
você pensar sobre isso de forma breve e ver e se convencer de que de fato esta

00:01:42.241 --> 00:01:46.853
teorema é verdadeiro. As verdadeiras questões é se podemos construir um PRF, que na verdade

00:01:46.853 --> 00:01:51.756
tem um domínio que é maior do que um bit. Idealmente gostaríamos que o domínio para ser 128

00:01:51.756 --> 00:01:56.425
bits, basta dizer que a [inaudível] tem. Então a questão é que podemos construir 128 bits PRS

00:01:56.425 --> 00:02:01.197
a partir de um gerador pseudo-aleatório. Bem, então vamos ver se podemos fazer progressos. Assim, o

00:02:01.197 --> 00:02:05.970
primeira coisa que vamos fazer é que nós vamos dizer, bem de novo, vamos começar com um PRG

00:02:05.970 --> 00:02:10.863
, que duplica o seu contributo vamos ver se podemos construir um PRG que quadruplica suas entradas.

00:02:10.863 --> 00:02:15.797
Ok? Assim, ele vai de K para K para o quarto em vez de K para K quadrado. Ok, então vamos

00:02:15.797 --> 00:02:20.809
ver como fazer isso. Então, vamos começar com a nossa PRG original que apenas duplica a sua

00:02:20.809 --> 00:02:25.884
entradas, agora lembrar que o facto de a sua é um PRG significa que a saída do

00:02:25.884 --> 00:02:30.771
PRG é indistinguível de dois valores aleatórios em K. Bem, se a saída se parece

00:02:30.771 --> 00:02:35.847
como dois valores aleatórios em K, podemos simplesmente aplicar o gerador de novo para os dois

00:02:35.847 --> 00:02:40.358
saídas. Então, digamos que nós aplicamos o gerador de uma vez para a saída da esquerda, e

00:02:40.358 --> 00:02:45.342
uma vez para as saídas de direitos. E nós vamos chamar a saída de que, este

00:02:45.342 --> 00:02:50.448
quádruplo de elementos, que são, vão chamar isso de G1K. E eu escrevi em

00:02:50.448 --> 00:02:55.554
símbolos que esse gerador faz, mas você pode ver, basicamente, a partir desta figura,

00:02:55.554 --> 00:03:00.862
exatamente como funciona o gerador. Portanto, agora que temos um gerador de K a K para

00:03:00.862 --> 00:03:06.170
quarta, Nós realmente obter um pouco PRF dois. Ou seja, o que vamos fazer é, vamos dizer,

00:03:06.170 --> 00:03:11.410
dado dois bits, 000110 ou 11, vontades implica a saída do bloco apropriado que

00:03:11.410 --> 00:03:16.070
saída de G1K. Ok, então agora podemos basicamente ter um PRF que leva quatro

00:03:16.070 --> 00:03:21.061
entradas possíveis ao invés de apenas duas entradas possíveis como antes. Portanto, a questão

00:03:21.061 --> 00:03:26.113
você deve estar me perguntando é porque é que este caso G1 seguro? Por que é um PRG seguro? Que

00:03:26.113 --> 00:03:30.611
é por que isso é quadruplicar de saídas indistinguíveis de forma aleatória. E assim

00:03:30.611 --> 00:03:35.664
vamos fazer uma prova rápida de isso, apenas vou fazer uma prova simples por imagens. Então aqui está

00:03:35.664 --> 00:03:40.408
gerador nossa que queremos provar é seguro. E o que isso significa é que nós

00:03:40.408 --> 00:03:45.399
quero argumentar que essa distribuição é indistinguível de um fordable aleatória

00:03:45.399 --> 00:03:49.292
em K para a quarta. Ok então nosso objetivo é provar que esses dois são

00:03:49.292 --> 00:03:53.887
indistinguíveis. Bem vamos fazer um passo de cada vez. Sabemos que o gerador

00:03:53.887 --> 00:03:58.028
é um gerador de segura, portanto, de facto, a saída do primeiro nível é

00:03:58.028 --> 00:04:02.453
indistinguível da aleatória. Em outras palavras, se se substituir o primeiro nível por

00:04:02.453 --> 00:04:06.991
seqüências verdadeiramente aleatórias estes dois são verdadeiramente aleatórios colhidos na tecla de espaço, então não

00:04:10.267 --> 00:04:11.359
adversário eficiente deve ser capaz de distinguir essas duas distribuições. Em

00:04:11.359 --> 00:04:15.954
fato, se você pudesse distinguir estas duas distribuições, é fácil mostrar que você

00:04:15.954 --> 00:04:20.768
iria quebrar o PRG original. Ok, mas essencialmente você ver que a razão pela qual podemos

00:04:20.768 --> 00:04:25.581
fazer esta substituição, pode-se substituir a saída de G, com valores verdadeiramente aleatório, é

00:04:25.581 --> 00:04:30.578
exatamente por causa da definição do PRG, que diz que o posto para fora do PRG é

00:04:30.578 --> 00:04:35.391
indistinguível de forma aleatória, por isso pode muito bem colocar aleatório lá, e não

00:04:35.391 --> 00:04:40.265
adversário eficiente pode distinguir os resultantes duas distribuições. Ok, até agora

00:04:40.265 --> 00:04:45.018
tão bom, mas agora podemos fazer a mesma coisa de novo para o lado esquerdo. Em outro

00:04:45.018 --> 00:04:49.710
palavras, podemos substituir estes dois pseudo saídas aleatórias, pelas saídas verdadeiramente aleatórios.

00:04:49.710 --> 00:04:53.925
E novamente, pois o gerador G é seguro, eficiente nenhum adversário pode dizer

00:04:54.091 --> 00:04:57.807
a diferença entre estas duas distribuições. Mas de maneira diferente, se um

00:04:57.807 --> 00:05:02.077
adversário pode distinguir estas duas distribuições, então nós também daria uma

00:05:02.077 --> 00:05:06.707
ataque ao gerador de G. E agora finalmente nós vamos fazer isso uma última vez. Estamos

00:05:06.707 --> 00:05:11.280
vai substituir este par pseudo-aleatório por um par verdadeiramente aleatório, e baixo e eis que

00:05:11.280 --> 00:05:15.672
obter a distribuição real de que nós estávamos gravando para, gostaríamos de obter uma distribuição

00:05:15.672 --> 00:05:19.851
que é realmente feito de quatro blocos independentes. E agora temos provado isso

00:05:19.851 --> 00:05:23.279
transição, basicamente, que estes dois indistinguíveis, estes dois

00:05:23.279 --> 00:05:27.243
indistinguíveis, e estes dois indistinguíveis, e, portanto, estes dois

00:05:27.243 --> 00:05:31.475
são indistinguíveis, que é o que queríamos provar. Ok então este é o tipo de

00:05:31.475 --> 00:05:35.760
a idéia de alto nível para a prova, não é muito difícil fazer este rigoroso,

00:05:35.760 --> 00:05:39.792
, mas eu só queria mostrar-lhe a intuição meio de como a prova funciona. Bem,

00:05:39.792 --> 00:05:44.363
se fôssemos capazes de estender as saídas de geradores de uma vez, não há nada que impeça

00:05:44.363 --> 00:05:48.822
nos de fazê-lo novamente por isso aqui é um gerador G1 que produz quatro elementos em

00:05:48.822 --> 00:05:53.337
espaço a chave. E lembre-se a saída aqui é indistinguível do nosso aleatória

00:05:53.337 --> 00:05:57.909
par quatro, que é o que acabamos de provar. E então não há nada que nos impede de

00:05:57.909 --> 00:06:02.480
aplicando o gerador de novo. Então vamos dar o gerador de aplicá-la a este aleatório

00:06:02.480 --> 00:06:07.221
procurando coisa e devemos ser capazes de obter essa coisa aleatória procurando. Este par mais

00:06:07.221 --> 00:06:11.511
aqui que é aleatória procurando. E nós podemos fazer a mesma coisa novamente, e novamente, e

00:06:11.511 --> 00:06:16.405
novamente. E agora, basicamente, nós construímos um novo gerador que produz elementos em K para

00:06:16.405 --> 00:06:21.261
oitavo a, em oposição a K para a quarta. E mais uma vez a prova de segurança é muito

00:06:21.261 --> 00:06:26.056
da mesma forma como o que acabei de mostrar, essencialmente, você alterar gradualmente a

00:06:26.056 --> 00:06:30.612
saídas em saídas verdadeiramente aleatórios. Então nós mudar isso para um verdadeiramente aleatório

00:06:30.612 --> 00:06:35.168
de saída, então este, em seguida, que, em seguida, este, em seguida, que e assim por diante e assim por diante. Até

00:06:35.168 --> 00:06:39.724
finalmente temos algo que é verdadeiramente aleatório e, portanto, os dois originais

00:06:39.724 --> 00:06:44.396
distribuições nós começamos com G2K e verdadeiramente aleatório são indistinguíveis. Ok,

00:06:44.396 --> 00:06:49.325
tão longe tão bom. Portanto, agora temos um gerador que produz elementos em K para o oitavo.

00:06:49.325 --> 00:06:54.016
Agora, se fizermos isso, basicamente, temos um bit PRF três. Em outras palavras, a zero, zero,

00:06:54.016 --> 00:06:58.884
de zero esta PRF geraria este bloco, e assim por diante e assim por diante, até que um, um, um que

00:06:58.884 --> 00:07:03.163
geraria este bloco. Agora, o interessante é que na verdade isso PRF

00:07:03.163 --> 00:07:07.695
é fácil de calcular. Por exemplo, vamos supor que queremos para calcular a PRF no ponto

00:07:07.695 --> 00:07:11.948
um zero um. Ok, é um pouco PRF três. Ok então um zero um. Como faríamos

00:07:11.948 --> 00:07:16.536
que? Bem, basicamente, que iria começar a partir do original chave K. E agora gostaríamos de aplicar

00:07:16.536 --> 00:07:20.620
G o gerador, mas nós só prestar atenção ao direito de saída G,

00:07:20.620 --> 00:07:25.040
porque o primeiro bit é um. E então vamos aplicar o gerador de novo, mas nós

00:07:25.040 --> 00:07:29.516
só prestar atenção para a esquerda da saída do gerador porque o

00:07:29.516 --> 00:07:33.864
segundo bit é zero. E, então, se aplicaria o gerador de novo e só paga

00:07:33.864 --> 00:07:38.588
atenção para as saídas da direita, porque o terceiro bit é um e que seria o

00:07:38.588 --> 00:07:43.140
saída final. Certo, então você pode ver que, que nos levam a 101, e, de fato, porque

00:07:43.140 --> 00:07:47.461
gerador [inaudível] é pseudo-aleatório, sabemos que, em particular, que,

00:07:47.461 --> 00:07:52.796
esta saída aqui é pseudo-aleatório. Ok, então isso nos dá um pouco PRF três. Bem, se

00:07:52.796 --> 00:07:58.632
ele trabalhou três vezes, não há nenhuma razão pela qual não podem trabalhar N vezes. E assim se

00:07:58.632 --> 00:08:03.501
aplicar esta transformação mais uma vez, chegamos ao que é chamado de GGMPRF. GGM

00:08:03.501 --> 00:08:07.956
estandes para Goldreich, Goldwasser e Micali estes são os inventores do

00:08:07.956 --> 00:08:12.528
PRF isso e assim que funciona é o seguinte. Então, começamos com um gerador

00:08:12.528 --> 00:08:17.279
apenas dobra suas saídas, e agora nós somos capazes de construir um PRF que atua em um grande

00:08:17.279 --> 00:08:22.236
domínio principalmente um domínio de tamanho zero um para o N. ou N poderia ser tão grande como 128 ou mesmo

00:08:22.236 --> 00:08:26.897
mais. Então vamos ver, vamos supor que nós estamos dando uma entrada em 01 para o N, deixe-me mostrar-lhe como

00:08:26.897 --> 00:08:31.274
para avaliar a PRF. Bem, agora você deve realmente ter uma boa idéia de como

00:08:31.274 --> 00:08:35.480
para fazê-lo. Essencialmente, nós começamos a partir da chave original e, em seguida, aplicamos o

00:08:35.480 --> 00:08:40.255
gerador e tomamos a esquerda ou a direita dependendo do bit X0 e

00:08:40.255 --> 00:08:44.746
, em seguida, chegamos à próxima chave, K1. E, então, aplicar o gerador de novo e nós

00:08:44.746 --> 00:08:49.444
tomar à esquerda ou à direita dependendo X1 e chegamos à próxima chave. E

00:08:49.444 --> 00:08:54.730
então fazer isso de novo e de novo, até que finalmente estamos a chegar à saída. Então, nós

00:08:54.730 --> 00:08:59.818
ter processado todos os bits finais, e chegamos à saída desta função. E

00:08:59.818 --> 00:09:05.170
, basicamente, podemos provar a segurança de novo muito bonito ao longo das mesmas linhas como fizemos

00:09:05.170 --> 00:09:10.324
antes, e nós podemos mostrar que se G é um PRG seguro, então, de facto, temos um seguro

00:09:10.324 --> 00:09:14.917
PRF, a 01 para o N, em um domínio muito grande. Então, isso é fantástico. Agora, temos

00:09:14.917 --> 00:09:19.064
temos essencial, temos uma PRF que é comprovadamente seguro, assumindo que o

00:09:19.064 --> 00:09:23.495
gerador subjacente é seguro, eo gerador é supostamente muito mais fácil

00:09:23.495 --> 00:09:28.153
construir do que um PRF real. E, na verdade ele funciona em blocos que podem ser muito grandes, em

00:09:28.153 --> 00:09:33.296
particular, 01 ao 128, que é o que precisávamos. Então você pode perguntar por que não é bem

00:09:33.296 --> 00:09:39.122
coisa esta sendo usado na prática? E a razão é, que na verdade é bastante lento.

00:09:39.122 --> 00:09:44.597
Então, imagine que ligar como um gerador que conecta o gerador de salsa. Então agora para

00:09:44.597 --> 00:09:50.142
avaliar este PRF em um 128 entradas de bits, teríamos basicamente tem que executar o salsa

00:09:50.142 --> 00:09:55.617
gerador 128 vezes. Uma vez por bit da entrada. Mas, então, teria um PRF

00:09:55.617 --> 00:10:01.513
que é 128 vezes mais lenta do que a salsa original. E isso é muito, muito, muito mais lento

00:10:01.513 --> 00:10:06.227
que o AES. AES é um PRF heurística. Mas, no entanto, é muito mais rápido, então o que nós

00:10:06.227 --> 00:10:10.585
acabou de chegar aqui. E por isso mesmo que esta é uma construção muito elegante, ela não é usada

00:10:10.585 --> 00:10:14.522
, na prática, para construir pseudo funções aleatórias, embora em uma semana estaremos

00:10:14.522 --> 00:10:18.915
usando este tipo de construção para construir um mecanismo de integridade da mensagem. Assim, a última

00:10:18.915 --> 00:10:23.183
passo, é basicamente agora que temos construído um PRF, as perguntas é se podemos

00:10:23.183 --> 00:10:27.729
realmente construir a cifra de bloco. Em outras palavras, podemos realmente construir uma PRP seguro

00:10:27.729 --> 00:10:32.054
a partir de um PRG seguro. Tudo o que fizemos até agora, não é reversível. Novamente, se você

00:10:32.054 --> 00:10:36.600
olhar para essa construção aqui, não podemos decifrar, basicamente devido aos resultados finais.

00:10:36.600 --> 00:10:40.535
Não é possível voltar atrás ou, pelo menos, não sabemos como voltar a, o

00:10:40.535 --> 00:10:44.520
entradas originais. Então agora a questão de interesse é tão podemos realmente resolver o

00:10:44.520 --> 00:10:48.654
problema que queria resolver inicialmente? Principalmente, podemos realmente construir uma cifra de bloco de

00:10:48.654 --> 00:10:53.540
um PRG seguro? Tão mal deixá-lo pensar sobre isso por um segundo, e marcar a resposta. Assim

00:10:53.540 --> 00:10:57.718
é claro que eu espero que todos disse que a resposta é sim e você já tem todos os

00:10:57.718 --> 00:11:01.896
ingredientes para fazê-lo. Em particular, você já sabe como construir um PRF de um

00:11:01.896 --> 00:11:06.395
gerador pseudo-aleatório. E nós dissemos que uma vez que temos um PRF que podemos ligá-lo na

00:11:06.395 --> 00:11:10.573
construção Luby-Rackoff, que se você se lembra, é apenas Feistel um três-redonda.

00:11:10.573 --> 00:11:14.750
Então nós dissemos que se você ligar um PRF seguro em um Feistel de três rounds, você recebe um

00:11:14.750 --> 00:11:19.044
PRP seguro. Então, combinando estes dois, basicamente nos dá uma PRP seguro

00:11:19.044 --> 00:11:23.328
a partir de um gerador pseudo-aleatório. E isto é provably assegurar enquanto o

00:11:23.328 --> 00:11:28.075
gerador subjacente é segura. Portanto, é um belo resultado, mas infelizmente mais uma vez

00:11:28.075 --> 00:11:32.475
ela não é usada na prática porque é consideravelmente mais lento que a heurística

00:11:32.475 --> 00:11:36.725
construções como AES. Ok assim que este completa o nosso módulo sobre construção

00:11:36.725 --> 00:11:40.456
pseudo permutações aleatórias e pseudo funções aleatórias. E, em seguida, no próximo

00:11:40.456 --> 00:11:44.287
módulo nós vamos falar sobre como usar essas coisas para fazer a criptografia apropriada.