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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

0:02:34.933,0:02:38.498
И тако ћемо да докажемо нашу лему.

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

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

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

0:02:52.405,0:02:56.365
на предност нападача. Нападача се уопште не тиче

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

0:05:47.427,0:05:51.929
Дакле разлика ових вероватноћа је

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

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

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

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

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

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

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

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

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

0:06:31.720,0:06:35.656
Дакле сада нас

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

0:08:59.942,0:09:05.418
излаз враћа излаз од А.

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

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

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

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

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

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

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

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

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

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

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

0:10:03.919,0:10:10.214
Ово је вероватноћа од R0.

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

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

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

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

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

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

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

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

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