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

2
00:00:04,134 --> 00:00:08,425
семантичке безбедности, можемо да докажемо да је шифра тока са безбедним PRG-ом

3
00:00:08,425 --> 00:00:12,559
семантички безбедна. То ће бити наш циљ за овај одељак.

4
00:00:12,559 --> 00:00:16,746
То је врло једноставан доказ, па хајде да погледамо. Теорија коју желимо да докажемо је

5
00:00:16,746 --> 00:00:20,932
да имајући генератор који је безбедни, псеудослучајни генератор,

6
00:00:20,932 --> 00:00:24,805
шифра тока коју добијамо од овог генератора

7
00:00:24,805 --> 00:00:28,924
јесте семантички безбедна. Желим да нагласим да није

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

9
00:00:33,085 --> 00:00:37,193
савршене безбедности. Зато што знамо да шифра тока не може да буде савршено безбедна,

10
00:00:37,193 --> 00:00:41,264
зато што има кратак кључ. А савршена безбедност захтева да кључеви буду исте

11
00:00:41,264 --> 00:00:45,321
дужине као и порука. Тако да је ово први пример који видимо, у коме можемо

12
00:00:45,321 --> 00:00:49,229
да докажемо да и шифра са кратким кључевима има безбедност, у смислу

13
00:00:49,229 --> 00:00:53,236
семантичке безбедности. Тиме се потврђује да је ово заиста

14
00:00:53,236 --> 00:00:56,943
користан појам, и у ствари, користићемо семантичку безбедност

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

16
00:01:00,750 --> 00:01:04,257
Почињемо од тога што претпоставимо супротно.

17
00:01:04,257 --> 00:01:08,264
Показаћемо следеће - доказаћемо ову

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

19
00:01:12,815 --> 00:01:18,345
Направићемо PRG нападач В који задовољава

20
00:01:18,345 --> 00:01:23,686
ову неједначину овде. А зашто нам је ова неједначина корисна? У суштини, шта ми знамо?

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

22
00:01:28,878 --> 00:01:33,053
знамо да је ова предност занемарљива, јел тако? Безбедни генератор

23
00:01:33,053 --> 00:01:37,510
има занемарљиву предност над произвољним ефикасним статистичким тестом.

24
00:01:37,510 --> 00:01:42,023
Тако да је ова десна страна практично занемарљива. Али зато што је десна страна

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

26
00:01:46,023 --> 00:01:50,767
Следи да нападач који посматрамо има заправо занемарљиву предност

27
00:01:50,767 --> 00:01:54,538
приликом нападања шифре тока Е.

28
00:01:54,538 --> 00:01:58,486
За постојећег нападача А направићемо

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

30
00:02:02,591 --> 00:02:06,036
али из тога следи да А има занемарљиву предност над шифром тока.

31
00:02:06,082 --> 00:02:10,994
Дакле за задато А треба да саградимо В.

32
00:02:10,994 --> 00:02:15,183
Нека је А нападач семантичке безбедности шифре тока. Подсећам вас

33
00:02:15,183 --> 00:02:19,320
шта то значи: постоји изазивач, који почиње тако што

34
00:02:19,320 --> 00:02:23,509
одабере кључ k. А затим нападач шаље две поруке једнаке

35
00:02:23,509 --> 00:02:27,383
дужине, и добија шифру поруке m0 или m1,

36
00:02:27,383 --> 00:02:31,226
и на излазу даје b'. Дакле то ради нападач семантичке

37
00:02:31,226 --> 00:02:34,933
безбедности. Сада ћемо да започнемо игру са овим нападачем.

38
00:02:34,933 --> 00:02:38,498
И тако ћемо да докажемо нашу лему.

39
00:02:38,498 --> 00:02:42,535
Прво што чемо да урадимо је да на страни изазивача одаберемо насумично r,

40
00:02:42,535 --> 00:02:47,500
насумични низ r. Нападача се не тиче шта

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

42
00:02:52,405 --> 00:02:56,365
на предност нападача. Нападача се уопште не тиче

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

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

45
00:03:05,042 --> 00:03:09,993
Видите шта овде радимо. Мењамо изазивача

46
00:03:09,993 --> 00:03:14,219
тако да се сада шифрат добија коришћењем

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

48
00:03:19,006 --> 00:03:23,639
псеудослучајног генератора је да је његов излаз нераспознатљив од истински

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

50
00:03:28,273 --> 00:03:33,082
измену. Нападач не види да смо прешли са псеудослучајног низа на

51
00:03:33,082 --> 00:03:37,422
истински случајан, зато што је генератор безбедан. Погледајмо сада

52
00:03:37,422 --> 00:03:41,762
коју игру смо добили. Предност нападача није могла

53
00:03:41,762 --> 00:03:46,630
да се много промени, зато што он не распознаје разлику. Али погледајмо ову игру.

54
00:03:46,630 --> 00:03:51,073
Ова игра је истинска једнократна бележница. Ово је игра семантичке

55
00:03:51,073 --> 00:03:55,803
безбедности против једнократне бележнице. Зато што сада нападач добија

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

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

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

59
00:04:08,165 --> 00:04:12,674
зато што нападач не види разлику приликом

60
00:04:12,674 --> 00:04:17,013
преласка са псеудослучајног на случајни кључ, а не може да победи случајну игру, то значи да

61
00:04:17,013 --> 00:04:21,411
не би победио ни псеудослучајну игру. Следи да првобитна шифра тока

62
00:04:21,411 --> 00:04:25,634
мора да је безбедна. Дакле ово је интуитивно изведени доказ.

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

64
00:04:29,594 --> 00:04:33,975
играјући игре са нашим изазивачем. И нећемо да се бавимо строго формалним доказима

65
00:04:33,975 --> 00:04:38,304
као што је овај што следи. Али желим да одрадим и један такав доказ,

66
00:04:38,304 --> 00:04:42,629
чисто да видите како изгледају ови докази. Добро, сада морам да уведем неке ознаке.

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

68
00:04:47,751 --> 00:04:52,937
када користимо псеудослучајни кључ, користићу W0 и W1

69
00:04:52,937 --> 00:04:58,059
да означим догађај да нападач враћа 1 када добија шифру

70
00:04:58,059 --> 00:05:02,856
од m0 или од m1, редом. Дакле W0 одговара

71
00:05:02,856 --> 00:05:07,719
излазу 1, када се добија шифра од m0, а W1 одговара

72
00:05:07,719 --> 00:05:13,141
излазу 1 када се добија шифра од m1. Дакле ово је стандардна

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

74
00:05:19,606 --> 00:05:24,505
R0 и R1 да означимо догађај да нападач враћа 1 када добија

75
00:05:24,505 --> 00:05:29,125
једнократну шифру од m0 или од m1. Дакле имамо

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

77
00:05:33,567 --> 00:05:38,365
из игре семантичке безбедности када пређемо на једнократну бележницу.

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

79
00:05:42,985 --> 00:05:47,427
догађаји из игре семантичке безбедности против једнократне бележнице.

80
00:05:47,427 --> 00:05:51,929
Дакле разлика ових вероватноћа је

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

82
00:05:56,902 --> 00:06:01,231
Одлично. То значи да је вероватноћа од R0

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

84
00:06:05,662 --> 00:06:10,261
између 0 и 1. Дакле овде су догађаји: W0 и W1 су догађаји који

85
00:06:10,261 --> 00:06:14,499
нас занимају. Желимо да покажемо да су они блиски.

86
00:06:14,499 --> 00:06:18,490
А то ћемо да урадимо тако што ћемо -- узгред треба да кажем

87
00:06:18,490 --> 00:06:22,754
да вероватноће R0 и R1, будући да су једнаке, постављам у

88
00:06:22,754 --> 00:06:27,237
исту тачку. Показаћемо да су и W0 и W1

89
00:06:27,237 --> 00:06:31,720
близу вероватноће Rb па самим тим и међусобно.

90
00:06:31,720 --> 00:06:35,656
Дакле сада нас

91
00:06:35,656 --> 00:06:39,865
занима растојање између вероватноће од Wb и вероватноће

92
00:06:39,865 --> 00:06:44,730
од Rb. Да сада искажем тврдњу коју ћемо да докажемо за који тренутак.

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

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

95
00:06:55,081 --> 00:06:59,833
Са ове две тврдње теорема је доказана, зато што

96
00:06:59,833 --> 00:07:04,771
сада знамо да је ово растојање мање од предности В

97
00:07:04,771 --> 00:07:09,523
над G. То следи из тврдње број 2, а ово растојање је заправо

98
00:07:09,523 --> 00:07:14,401
једнако тој предности В над G,

99
00:07:14,401 --> 00:07:19,455
из чега произилази да је растојање између вероватноћа W0 и W1

100
00:07:19,455 --> 00:07:24,446
скоро два пута веће од предности В над G.

101
00:07:24,446 --> 00:07:29,375
Што и желимо да докажемо. Остаје још само да

102
00:07:29,375 --> 00:07:34,304
докажемо ово тврђење. Ако размислите како оно гласи,

103
00:07:34,304 --> 00:07:39,170
њиме се обухвата случај огледа 0, када

104
00:07:39,170 --> 00:07:43,530
заменимо псеудослучајни генератор G(k) истински случајним кључем r.

105
00:07:43,530 --> 00:07:48,910
У огледу 0 овде користимо псеудослучајни кључ, а овде

106
00:07:48,910 --> 00:07:53,593
истински случајни, и питамо се да ли нападач може да распозна

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

108
00:07:58,972 --> 00:08:03,845
Ево шта ћемо да урадимо. Докажимо тврдњу број 2.

109
00:08:03,845 --> 00:08:08,728
Доказаћемо да постоји PRG нападач В који има предност

110
00:08:08,728 --> 00:08:13,764
која је једнака управо разлици између ове две вероватноће.

111
00:08:13,764 --> 00:08:18,319
Пошто је ово занемарљиво, и ово је занемарљиво, а то смо и желели

112
00:08:18,319 --> 00:08:22,323
да докажемо. Погледајмо статистички тест В.

113
00:08:22,323 --> 00:08:26,514
Наш статистички тест В ће да садржи нападача А, и можемо да га саградимо

114
00:08:26,514 --> 00:08:31,091
како год желимо. Унутар њега користимо нападач А,

115
00:08:31,091 --> 00:08:35,558
и то је обичан статистички тест, који узима n-битни

116
00:08:35,558 --> 00:08:39,694
низ као улаз, и враћа вредности "случајно" или "није случајно",

117
00:08:39,694 --> 00:08:43,995
0 или 1. Погледајмо. Најпре ће да покрене

118
00:08:43,995 --> 00:08:48,407
нападача А, који ће да избаци две поруке, m0 и m1.

119
00:08:48,407 --> 00:08:54,053
Тада ће нападач В да одговори са m0 XOR низ који

120
00:08:54,053 --> 00:08:59,942
му је био прослеђен као улаз. Дакле статистички тест као свој

121
00:08:59,942 --> 00:09:05,418
излаз враћа излаз од А.

122
00:09:05,418 --> 00:09:10,477
Шта можемо да кажемо о предности статистичког теста

123
00:09:10,477 --> 00:09:15,606
над генератором? По дефиницији, она је једнака вероватноћи да, ако одаберете

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

125
00:09:20,527 --> 00:09:25,587
да В враћа 1, минус вероватноћа да, ако одаберемо псеудослучајни

126
00:09:25,587 --> 00:09:32,603
низ, В враћа 1. Али да размислимо шта нам ово говори.

127
00:09:32,603 --> 00:09:37,398
Шта можете да ми кажете о првом изразу?

128
00:09:37,398 --> 00:09:42,256
О овом изразу овде? По дефиницији, то је управо једнако

129
00:09:42,256 --> 00:09:47,366
вероватноћи од R0, зар не?

130
00:09:47,366 --> 00:09:52,729
Зато што у нашој игри против нападача, он нам је дао

131
00:09:52,729 --> 00:09:58,028
m0 и m1, и добио је шифру од m0

132
00:09:58,028 --> 00:10:03,919
под једнократном бележницом. Дакле ово је вероватноћа од R0.

133
00:10:03,919 --> 00:10:10,214
Ово је вероватноћа од R0.

134
00:10:10,660 --> 00:10:15,467
Шта можемо да кажемо о следећем изразу, шта можемо да кажемо о томе када

135
00:10:15,467 --> 00:10:19,100
В добија псеудослучајни низ у као улаз?

136
00:10:19,100 --> 00:10:23,493
У том случају, ово је управо оглед 0 и права игра шифре тока,

137
00:10:23,493 --> 00:10:29,999
зато што сада рачунамо m0 XOR G(k). А то је управо W0.

138
00:10:29,999 --> 00:10:33,015
А то је и требало доказати. Дакле доказ је тривијалан.

139
00:10:33,015 --> 00:10:39,563
Овим смо доказали тврдњу број 2, и да поновим, једном када имамо

140
00:10:39,563 --> 00:10:43,799
тврдњу број 2, знамо да W0 мора да буде близу W1, а то и јесте теорема,

141
00:10:43,814 --> 00:10:50,383
то је и требало да докажемо. Дакле сада смо утврдили да је шифра тока

142
00:10:50,383 --> 00:10:53,880
заиста семантички безбедна, под претпоставком да је PRG безбедан.