Шифре тока су семантички безбедне (11 min) [произвољно]

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

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

семантички безбедна. То ће бити наш циљ за овај одељак.

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

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

шифра тока коју добијамо од овог генератора

јесте семантички безбедна. Желим да нагласим да није

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

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

зато што има кратак кључ. А савршена безбедност захтева да кључеви буду исте

дужине као и порука. Тако да је ово први пример који видимо, у коме можемо

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

семантичке безбедности. Тиме се потврђује да је ово заиста

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

много пута током течаја. Добро, како доказујемо једну овакву теорију?

Почињемо од тога што претпоставимо супротно.

Показаћемо следеће - доказаћемо ову

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

Направићемо PRG нападач В који задовољава

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

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

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

има занемарљиву предност над произвољним ефикасним статистичким тестом.

Тако да је ова десна страна практично занемарљива. Али зато што је десна страна

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

Следи да нападач који посматрамо има заправо занемарљиву предност

приликом нападања шифре тока Е.

За постојећег нападача А направићемо

нападача В. Знамо да он има занемарљиву предност над генератором,

али из тога следи да А има занемарљиву предност над шифром тока.

Дакле за задато А треба да саградимо В.

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

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

одабере кључ k. А затим нападач шаље две поруке једнаке

дужине, и добија шифру поруке m0 или m1,

и на излазу даје b'. Дакле то ради нападач семантичке

безбедности. Сада ћемо да започнемо игру са овим нападачем.

И тако ћемо да докажемо нашу лему.

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

насумични низ r. Нападача се не тиче шта

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

на предност нападача. Нападача се уопште не тиче

што изазивач користи r. Али ево у чему је ствар. Ми ћемо,

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

Видите шта овде радимо. Мењамо изазивача

тако да се сада шифрат добија коришћењем

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

псеудослучајног генератора је да је његов излаз нераспознатљив од истински

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

измену. Нападач не види да смо прешли са псеудослучајног низа на

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

коју игру смо добили. Предност нападача није могла

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

Ова игра је истинска једнократна бележница. Ово је игра семантичке

безбедности против једнократне бележнице. Зато што сада нападач добија

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

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

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

зато што нападач не види разлику приликом

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

не би победио ни псеудослучајну игру. Следи да првобитна шифра тока

мора да је безбедна. Дакле ово је интуитивно изведени доказ.

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

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

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

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

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

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

да означим догађај да нападач враћа 1 када добија шифру

од m0 или од m1, редом. Дакле W0 одговара

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

излазу 1 када се добија шифра од m1. Дакле ово је стандардна

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

R0 и R1 да означимо догађај да нападач враћа 1 када добија

једнократну шифру од m0 или од m1. Дакле имамо

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

из игре семантичке безбедности када пређемо на једнократну бележницу.

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

догађаји из игре семантичке безбедности против једнократне бележнице.

Дакле разлика ових вероватноћа је

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

Одлично. То значи да је вероватноћа од R0

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

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

нас занимају. Желимо да покажемо да су они блиски.

А то ћемо да урадимо тако што ћемо -- узгред треба да кажем

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

исту тачку. Показаћемо да су и W0 и W1

близу вероватноће Rb па самим тим и међусобно.

Дакле сада нас

занима растојање између вероватноће од Wb и вероватноће

од Rb. Да сада искажем тврдњу коју ћемо да докажемо за који тренутак.

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

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

Са ове две тврдње теорема је доказана, зато што

сада знамо да је ово растојање мање од предности В

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

једнако тој предности В над G,

из чега произилази да је растојање између вероватноћа W0 и W1

скоро два пута веће од предности В над G.

Што и желимо да докажемо. Остаје још само да

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

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

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

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

истински случајни, и питамо се да ли нападач може да распозна

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

Ево шта ћемо да урадимо. Докажимо тврдњу број 2.

Доказаћемо да постоји PRG нападач В који има предност

која је једнака управо разлици између ове две вероватноће.

Пошто је ово занемарљиво, и ово је занемарљиво, а то смо и желели

да докажемо. Погледајмо статистички тест В.

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

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

и то је обичан статистички тест, који узима n-битни

низ као улаз, и враћа вредности "случајно" или "није случајно",

0 или 1. Погледајмо. Најпре ће да покрене

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

Тада ће нападач В да одговори са m0 XOR низ који

му је био прослеђен као улаз. Дакле статистички тест као свој

излаз враћа излаз од А.

Шта можемо да кажемо о предности статистичког теста

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

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

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

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

Шта можете да ми кажете о првом изразу?

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

вероватноћи од R0, зар не?

Зато што у нашој игри против нападача, он нам је дао

m0 и m1, и добио је шифру од m0

под једнократном бележницом. Дакле ово је вероватноћа од R0.

Ово је вероватноћа од R0.

Шта можемо да кажемо о следећем изразу, шта можемо да кажемо о томе када

В добија псеудослучајни низ у као улаз?

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

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

А то је и требало доказати. Дакле доказ је тривијалан.

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

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

то је и требало да докажемо. Дакле сада смо утврдили да је шифра тока

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