WEBVTT

00:00:00.000 --> 00:00:04.134
Сада када смо разумели појам безбедности псеудослучајног генератора, као и појам

00:00:04.134 --> 00:00:08.425
семантичке безбедности, можемо да докажемо да је шифра тока са безбедним PRG-ом

00:00:08.425 --> 00:00:12.559
семантички безбедна. То ће бити наш циљ за овај одељак.

00:00:12.559 --> 00:00:16.746
То је врло једноставан доказ, па хајде да погледамо. Теорија коју желимо да докажемо је

00:00:16.746 --> 00:00:20.932
да имајући генератор који је безбедни, псеудослучајни генератор,

00:00:20.932 --> 00:00:24.805
шифра тока коју добијамо од овог генератора

00:00:24.805 --> 00:00:28.924
јесте семантички безбедна. Желим да нагласим да није

00:00:28.924 --> 00:00:33.085
било могуће да се оваква теорема докаже за савршену безбедност, за Шенонов појам

00:00:33.085 --> 00:00:37.193
савршене безбедности. Зато што знамо да шифра тока не може да буде савршено безбедна,

00:00:37.193 --> 00:00:41.264
зато што има кратак кључ. А савршена безбедност захтева да кључеви буду исте

00:00:41.264 --> 00:00:45.321
дужине као и порука. Тако да је ово први пример који видимо, у коме можемо

00:00:45.321 --> 00:00:49.229
да докажемо да и шифра са кратким кључевима има безбедност, у смислу

00:00:49.229 --> 00:00:53.236
семантичке безбедности. Тиме се потврђује да је ово заиста

00:00:53.236 --> 00:00:56.943
користан појам, и у ствари, користићемо семантичку безбедност

00:00:56.943 --> 00:01:00.750
много пута током течаја. Добро, како доказујемо једну овакву теорију?

00:01:00.750 --> 00:01:04.257
Почињемо од тога што претпоставимо супротно.

00:01:04.257 --> 00:01:08.264
Показаћемо следеће - доказаћемо ову

00:01:08.264 --> 00:01:12.815
тврдњу овде, али да је прво рашчланим. Рецимо дате ми нападача семантичке безбедности, А.

00:01:12.815 --> 00:01:18.345
Направићемо PRG нападач В који задовољава

00:01:18.345 --> 00:01:23.686
ову неједначину овде. А зашто нам је ова неједначина корисна? У суштини, шта ми знамо?

00:01:23.686 --> 00:01:28.878
Знамо да ако је В ефикасан нападач, пошто је G безбедни генератор,

00:01:28.878 --> 00:01:33.053
знамо да је ова предност занемарљива, јел тако? Безбедни генератор

00:01:33.053 --> 00:01:37.510
има занемарљиву предност над произвољним ефикасним статистичким тестом.

00:01:37.510 --> 00:01:42.023
Тако да је ова десна страна практично занемарљива. Али зато што је десна страна

00:01:42.023 --> 00:01:46.023
занемарљива, закључујемо да је и лева страна занемарљива.

00:01:46.023 --> 00:01:50.767
Следи да нападач који посматрамо има заправо занемарљиву предност

00:01:50.767 --> 00:01:54.538
приликом нападања шифре тока Е.

00:01:54.538 --> 00:01:58.486
За постојећег нападача А направићемо

00:01:58.486 --> 00:02:02.591
нападача В. Знамо да он има занемарљиву предност над генератором,

00:02:02.591 --> 00:02:06.036
али из тога следи да А има занемарљиву предност над шифром тока.

00:02:06.082 --> 00:02:10.994
Дакле за задато А треба да саградимо В.

00:02:10.994 --> 00:02:15.183
Нека је А нападач семантичке безбедности шифре тока. Подсећам вас

00:02:15.183 --> 00:02:19.320
шта то значи: постоји изазивач, који почиње тако што

00:02:19.320 --> 00:02:23.509
одабере кључ k. А затим нападач шаље две поруке једнаке

00:02:23.509 --> 00:02:27.383
дужине, и добија шифру поруке m0 или m1,

00:02:27.383 --> 00:02:31.226
и на излазу даје b'. Дакле то ради нападач семантичке

00:02:31.226 --> 00:02:34.933
безбедности. Сада ћемо да започнемо игру са овим нападачем.

00:02:34.933 --> 00:02:38.498
И тако ћемо да докажемо нашу лему.

00:02:38.498 --> 00:02:42.535
Прво што чемо да урадимо је да на страни изазивача одаберемо насумично r,

00:02:42.535 --> 00:02:47.500
насумични низ r. Нападача се не тиче шта

00:02:47.500 --> 00:02:52.405
изазивач интерно ради. Нападач никада не користи r, тако да ово нема никаквог утицаја

00:02:52.405 --> 00:02:56.365
на предност нападача. Нападача се уопште не тиче

00:02:56.365 --> 00:03:00.706
што изазивач користи r. Али ево у чему је ствар. Ми ћемо,

00:03:00.706 --> 00:03:05.042
уместо да шифрујемо користећи G(k), да користимо r за шифровање.

00:03:05.042 --> 00:03:09.993
Видите шта овде радимо. Мењамо изазивача

00:03:09.993 --> 00:03:14.219
тако да се сада шифрат добија коришћењем

00:03:14.219 --> 00:03:19.006
истински случајног кључа, уместо псеудослучајног кључа G(k). Својство

00:03:19.006 --> 00:03:23.639
псеудослучајног генератора је да је његов излаз нераспознатљив од истински

00:03:23.639 --> 00:03:28.273
случајног. Дакле зато што је PRG безбедан, нападач не распознаје да смо направили ову

00:03:28.273 --> 00:03:33.082
измену. Нападач не види да смо прешли са псеудослучајног низа на

00:03:33.082 --> 00:03:37.422
истински случајан, зато што је генератор безбедан. Погледајмо сада

00:03:37.422 --> 00:03:41.762
коју игру смо добили. Предност нападача није могла

00:03:41.762 --> 00:03:46.630
да се много промени, зато што он не распознаје разлику. Али погледајмо ову игру.

00:03:46.630 --> 00:03:51.073
Ова игра је истинска једнократна бележница. Ово је игра семантичке

00:03:51.073 --> 00:03:55.803
безбедности против једнократне бележнице. Зато што сада нападач добија

00:03:55.803 --> 00:04:00.238
шифру једнократне бележнице за m0 или m1. Али овде је, као што знамо, предност

00:04:00.238 --> 00:04:04.048
нападача нула, зато што не можете да победите једнократну бележницу - она је

00:04:04.048 --> 00:04:08.165
безусловно безбедна. А као последица тога,

00:04:08.165 --> 00:04:12.674
зато што нападач не види разлику приликом

00:04:12.674 --> 00:04:17.013
преласка са псеудослучајног на случајни кључ, а не може да победи случајну игру, то значи да

00:04:17.013 --> 00:04:21.411
не би победио ни псеудослучајну игру. Следи да првобитна шифра тока

00:04:21.411 --> 00:04:25.634
мора да је безбедна. Дакле ово је интуитивно изведени доказ.

00:04:25.634 --> 00:04:29.594
Али желим да одрадим и строго формални доказ. Од сада па надаље, доказе ћемо да изводимо

00:04:29.594 --> 00:04:33.975
играјући игре са нашим изазивачем. И нећемо да се бавимо строго формалним доказима

00:04:33.975 --> 00:04:38.304
као што је овај што следи. Али желим да одрадим и један такав доказ,

00:04:38.304 --> 00:04:42.629
чисто да видите како изгледају ови докази. Добро, сада морам да уведем неке ознаке.

00:04:42.629 --> 00:04:47.751
Користићу уобичајено обележавање. У првобитној игри против семантичке сигурности,

00:04:47.751 --> 00:04:52.937
када користимо псеудослучајни кључ, користићу W0 и W1

00:04:52.937 --> 00:04:58.059
да означим догађај да нападач враћа 1 када добија шифру

00:04:58.059 --> 00:05:02.856
од m0 или од m1, редом. Дакле W0 одговара

00:05:02.856 --> 00:05:07.719
излазу 1, када се добија шифра од m0, а W1 одговара

00:05:07.719 --> 00:05:13.141
излазу 1 када се добија шифра од m1. Дакле ово је стандардна

00:05:13.141 --> 00:05:19.606
дефиниција семантичке безбедности. А када пређемо на случајни кључ, користићу

00:05:19.606 --> 00:05:24.505
R0 и R1 да означимо догађај да нападач враћа 1 када добија

00:05:24.505 --> 00:05:29.125
једнократну шифру од m0 или од m1. Дакле имамо

00:05:29.125 --> 00:05:33.567
четири догађаја, W0, W1 из првобитне игре семантичке безбедности, и R0, R1

00:05:33.567 --> 00:05:38.365
из игре семантичке безбедности када пређемо на једнократну бележницу.

00:05:38.365 --> 00:05:42.985
Погледајмо сада односе између ових променљивих. Пре свега, R0 и R1 су

00:05:42.985 --> 00:05:47.427
догађаји из игре семантичке безбедности против једнократне бележнице.

00:05:47.427 --> 00:05:51.929
Дакле разлика ових вероватноћа је

00:05:51.929 --> 00:05:56.902
предност алгоритма А, или нападача А, против једнократне бележнице, што је 0.

00:05:56.902 --> 00:06:01.231
Одлично. То значи да је вероватноћа од R0

00:06:01.231 --> 00:06:05.662
једнака вероватноћи од R1. Дакле сада, поређајмо ове догађаје на делу линије

00:06:05.662 --> 00:06:10.261
између 0 и 1. Дакле овде су догађаји: W0 и W1 су догађаји који

00:06:10.261 --> 00:06:14.499
нас занимају. Желимо да покажемо да су они блиски.

00:06:14.499 --> 00:06:18.490
А то ћемо да урадимо тако што ћемо -- узгред треба да кажем

00:06:18.490 --> 00:06:22.754
да вероватноће R0 и R1, будући да су једнаке, постављам у

00:06:22.754 --> 00:06:27.237
исту тачку. Показаћемо да су и W0 и W1

00:06:27.237 --> 00:06:31.720
близу вероватноће Rb па самим тим и међусобно.

00:06:31.720 --> 00:06:35.656
Дакле сада нас

00:06:35.656 --> 00:06:39.865
занима растојање између вероватноће од Wb и вероватноће

00:06:39.865 --> 00:06:44.730
од Rb. Да сада искажем тврдњу коју ћемо да докажемо за који тренутак.

00:06:44.730 --> 00:06:49.938
Ова тврдња гласи да постоји нападач В такав, да је разлика ових двеју

00:06:49.938 --> 00:06:55.081
вероватноћа предност од В над генератором G, што важи за оба b.

00:06:55.081 --> 00:06:59.833
Са ове две тврдње теорема је доказана, зато што

00:06:59.833 --> 00:07:04.771
сада знамо да је ово растојање мање од предности В

00:07:04.771 --> 00:07:09.523
над G. То следи из тврдње број 2, а ово растојање је заправо

00:07:09.523 --> 00:07:14.401
једнако тој предности В над G,

00:07:14.401 --> 00:07:19.455
из чега произилази да је растојање између вероватноћа W0 и W1

00:07:19.455 --> 00:07:24.446
скоро два пута веће од предности В над G.

00:07:24.446 --> 00:07:29.375
Што и желимо да докажемо. Остаје још само да

00:07:29.375 --> 00:07:34.304
докажемо ово тврђење. Ако размислите како оно гласи,

00:07:34.304 --> 00:07:39.170
њиме се обухвата случај огледа 0, када

00:07:39.170 --> 00:07:43.530
заменимо псеудослучајни генератор G(k) истински случајним кључем r.

00:07:43.530 --> 00:07:48.910
У огледу 0 овде користимо псеудослучајни кључ, а овде

00:07:48.910 --> 00:07:53.593
истински случајни, и питамо се да ли нападач може да распозна

00:07:53.593 --> 00:07:58.972
разлику између њих, и желимо да докажемо да не може, зато што је генератор безбедан.

00:07:58.972 --> 00:08:03.845
Ево шта ћемо да урадимо. Докажимо тврдњу број 2.

00:08:03.845 --> 00:08:08.728
Доказаћемо да постоји PRG нападач В који има предност

00:08:08.728 --> 00:08:13.764
која је једнака управо разлици између ове две вероватноће.

00:08:13.764 --> 00:08:18.319
Пошто је ово занемарљиво, и ово је занемарљиво, а то смо и желели

00:08:18.319 --> 00:08:22.323
да докажемо. Погледајмо статистички тест В.

00:08:22.323 --> 00:08:26.514
Наш статистички тест В ће да садржи нападача А, и можемо да га саградимо

00:08:26.514 --> 00:08:31.091
како год желимо. Унутар њега користимо нападач А,

00:08:31.091 --> 00:08:35.558
и то је обичан статистички тест, који узима n-битни

00:08:35.558 --> 00:08:39.694
низ као улаз, и враћа вредности "случајно" или "није случајно",

00:08:39.694 --> 00:08:43.995
0 или 1. Погледајмо. Најпре ће да покрене

00:08:43.995 --> 00:08:48.407
нападача А, који ће да избаци две поруке, m0 и m1.

00:08:48.407 --> 00:08:54.053
Тада ће нападач В да одговори са m0 XOR низ који

00:08:54.053 --> 00:08:59.942
му је био прослеђен као улаз. Дакле статистички тест као свој

00:08:59.942 --> 00:09:05.418
излаз враћа излаз од А.

00:09:05.418 --> 00:09:10.477
Шта можемо да кажемо о предности статистичког теста

00:09:10.477 --> 00:09:15.606
над генератором? По дефиницији, она је једнака вероватноћи да, ако одаберете

00:09:15.606 --> 00:09:20.527
истински насумични низ - значи овде је r {0, 1} на n - дакле вероватноћа

00:09:20.527 --> 00:09:25.587
да В враћа 1, минус вероватноћа да, ако одаберемо псеудослучајни

00:09:25.587 --> 00:09:32.603
низ, В враћа 1. Али да размислимо шта нам ово говори.

00:09:32.603 --> 00:09:37.398
Шта можете да ми кажете о првом изразу?

00:09:37.398 --> 00:09:42.256
О овом изразу овде? По дефиницији, то је управо једнако

00:09:42.256 --> 00:09:47.366
вероватноћи од R0, зар не?

00:09:47.366 --> 00:09:52.729
Зато што у нашој игри против нападача, он нам је дао

00:09:52.729 --> 00:09:58.028
m0 и m1, и добио је шифру од m0

00:09:58.028 --> 00:10:03.919
под једнократном бележницом. Дакле ово је вероватноћа од R0.

00:10:03.919 --> 00:10:10.214
Ово је вероватноћа од R0.

00:10:10.660 --> 00:10:15.467
Шта можемо да кажемо о следећем изразу, шта можемо да кажемо о томе када

00:10:15.467 --> 00:10:19.100
В добија псеудослучајни низ у као улаз?

00:10:19.100 --> 00:10:23.493
У том случају, ово је управо оглед 0 и права игра шифре тока,

00:10:23.493 --> 00:10:29.999
зато што сада рачунамо m0 XOR G(k). А то је управо W0.

00:10:29.999 --> 00:10:33.015
А то је и требало доказати. Дакле доказ је тривијалан.

00:10:33.015 --> 00:10:39.563
Овим смо доказали тврдњу број 2, и да поновим, једном када имамо

00:10:39.563 --> 00:10:43.799
тврдњу број 2, знамо да W0 мора да буде близу W1, а то и јесте теорема,

00:10:43.814 --> 00:10:50.383
то је и требало да докажемо. Дакле сада смо утврдили да је шифра тока

00:10:50.383 --> 00:10:53.880
заиста семантички безбедна, под претпоставком да је PRG безбедан.