Семантичка безбедност (16 min)

Намера ми је да вам у следећих неколико одељака покажем да ако користимо безбедни PRG,

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

шта подразумевамо под безбедношћу шифре тока? Кад год дефинишемо безбедност,

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

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

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

јесте један шифрат шифрован коришћењем кључем који користимо. Дакле

ограничавамо нападачеву могућност на прибављање само једног шифрата.

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

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

шта подразумевамо под безбедношћу шифре? Прва дефиниција

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

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

не треба да будете у стању да прибавите тајни кључ. Али то је лоша дефиниција

зато што, погледајте следећу сјајну шифру, где шифрујемо

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

Наравно ово је сјајна шифра, не ради ништа са поруком

осим што шифрат избаци као саму поруку. Ово није нарочито добро шифровање;

међутим, на основу шифрата, тј. поруке, сироти нападач

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

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

захтевима безбедности. Дакле оваква дефиниција не би ваљала.

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

можемо да покушамо је да кажемо да можда нападача није брига

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

да нападачу буде тешко да дође до целокупног отвореног текста. Али чак и то

није довољно зато што, посматрајмо следећи начин шифровања. Рецимо

да код овог шифровања узимамо две поруке, ја ћу да користим

ове две линије да означим спајање двеју порука, m0 || m1 значи

спајање m0 и m1. Рецимо да ова шифра даје

m0 као отворену, и спаја то са шифром од m1. Можда чак и

коришћењем једнократне бележнице. Дакле овде се нападачу даје један

шифрат, а његов циљ је да дође до целокупног отвореног текста. Али

сироти нападач то не може да учини зато што, можда смо шифровали m1 коришћењем

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

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

би задовољила дефиницију, али нажалост ово очигледно није безбедно

шифровање, зато што је процурило пола отвореног текста.

m0 је потпуно доступно нападачу, тако да, мада не може да дође до

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

није безбедно. Наравно већ знамо решење за ово, говорили смо

о Шеноновој дефиницији савршене безбедности, где је Шенонова идеја била

да када нападач пресретне шифрат, не треба да сазна никакву

информацију о отвореном тексту. Не треба чак ни да сазна ни један бит

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

мали део отвореног текста; никакву информацију о отвореном тексту.

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

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

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

шифрата - ако одаберемо насумично кључ и посматрамо расподелу

шифрата, ако шифрујемо m0, добијамо потпуно исту расподелу као када

шифрујемо m1. Наслућујемо овде да ако нападач посматра шифрат,

не зна да ли је потекао из расподеле која је последица шифровања

са m0 или из расподеле која је последица шифровања са m1.

Услед тога, он не може да одреди да ли смо шифровали m0 или m1. И то важи за све

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

која порука је била шифрована. Наравно већ смо рекли да је ова дефиниција

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

никако не може да задовољи ову дефиницију. Конкретно, шифра тока

не може да задовољи ову дефиницију. Покушајмо да мало ослабимо ову дефиницију,

сетимо се претходног одељка. Можемо да кажемо да уместо да захтевамо

да две расподеле буду потпуно истоветне, ми захтевамо да

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

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

расподеле могу да буду врло различите. На основу узорка

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

из које расподеле је добио узорак. Испоставља се да је ова дефиниција

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

дакле морамо да додамо још једно ограничење, а то је да, уместо да кажемо да ова

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

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

доводи до дефиниције семантичке безбедности. Још једном, ово је семантичка

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

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

оглед 0 и оглед 1. У општем случају, посматраћемо

их као оглед (b), где b може да буде 0 или 1.

Оглед се дефинише на следећи начин, имамо нападача који

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

у свету псеудослучајних генератора. Изазивач ради

следеће, постоје два изазивача, али они

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

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

постављене на 1. Да вам покажем шта изазивач ради. Најпре

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

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

пар порука, за које нападач жели да буде изазван, и као и обично, не

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

Тада изазивач избаци шифровану m0

или шифровану m1, у огледу 0 изазивач избацује

шифровану m0, а у огледу 1 шифровану m1.

У томе је разлика између огледа.

Нападач покушава да погоди да ли је добио шифровану m0

или шифровану m1. Ево мало ознака. Дефинишимо

догађај Wb као догађај када за оглед b нападач избацује 1.

Дакле то је такав догађај, да у огледу 0 W0 значи да

је нападач избацио 1, а у огледу 1 W1 значи да је нападач избацио 1.

Сада можемо да дефинишемо предност овог нападача, и кажемо да је

предност семантичке безбедности нападача А над шемом Е

разлика између вероватноћа ова два догађаја. Другим речима

посматрамо да ли се нападач понаша различито када добије

шифровану m0 у односу на то када добије шифровану m1. Желим да будем

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

је шифровану m0, а у огледу 1 шифровану m1,

и сада нас занима да ли нападач избацује 1 или не,

у овим огледима. Ако у оба огледа нападач избацује 1 са

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

два огледа. Оглед 0 изгледа нападачу исто

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

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

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

могао да разликује ова два огледа. Да искажемо ово

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

вероватноћа, предност је број између 0 и 1. Ако је предност

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

оглед 0 од огледа 1. Међутим ако је предност блиска јединици,

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

огледа 1, што у ствари значи да је био у стању да разликује шифровање

m0 од шифровања m1. Дакле то је наша дефиниција, у ствари,

то је само дефиниција предности, а дефиниција је управо

оно што бисте и очекивали, кажемо да је шема симетричног шифровања

семантички безбедна, ако за све "ефикасне" нападаче,

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

не постоји ефикасан нападач који може да разликује шифровање m0 од шифровања m1,

и, тиме се каже, понављам, да за ове две

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

ове две расподеле. Желим да вам покажем, ово је заправо врло

елегантна дефиниција, не мора да тако изгледа одмах, али желим да вам покажем неке

последице ове дефиниције, а видећете зашто је ова дефиниција таква каква јесте.

Погледајмо неке примере. Први пример је - претпоставимо

да имамо разбијену шему шифровања, другим речима, претпоставимо да имамо нападача А

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

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

може да добије бит најмање тежине у m0. Ово је јако лоша

шема шифровања, зато што одаје бит најмање тежине из

отвореног текста самим шифратом. Желим да вам покажем да ова шема није

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

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

није семантички безбедан. Ми ћемо да користимо

нашег нападача, који може да открије битове најмање тежине, ми ћемо да

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

оглед 0 од огледа 1. Ево шта ћемо да урадимо.

Ми смо алгоритам В, а овај алгоритам В ће да користи

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

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

да ћемо да избацимо две поруке,

а које ће да имају различите битове најмање тежине.

Једна ће да се завршава са 0, а друга са 1.

И шта ће сада изазивач да уради? Он ће да нам да

шифровање било од m0 било од m1, у зависности од тога да ли смо у огледу 0

или у огледу 1. А тада ћемо само да проследимо овај шифрат нападачу,

дакле нападачу А. А које је својство нападача А? Добивши шифрат,

нападач А може да нам каже који је бит најмање тежине отвореног текста.

Другим речима, нападач ће да избаци бит најмање тежине од m0 или m1,

а то је практично бит b. И затим ћемо само да

избацимо то као наш погодак, назовимо то b'. Дакле овим

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

над семантичком безбедношћу код овог нападача? Па погледајмо: у огледу 0, која је

вероватноћа да нападач В избацује 1? Дакле у огледу 0 се увек

добија шифровање од m0, и зато нападач А увек избацује

бит најмање тежине од m0, а то је увек 0. У огледу

0, В увек избацује 0. Дакле вероватноћа да ће да избаци 1 је нула.

Међутим у огледу 1, добијамо шифровану m1. Дакле колико је вероватно да ће

нападач В да избаци 1 у огледу 1? Па, увек ће да избаци 1,

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

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

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

безбедношћу, просто сазнавање бита најмање тежине је довољно да потпуно

разбије систем - под дефиницијом семантичке безбедности. Занимљива ствар

овде је наравно да се не ради само о биту најмање тежине,

у ствари, било који бит поруке, на пример, бит највеће тежине,

седми бит, можда XOR свих битова поруке, итд,

било каква информација, било који бит отвореног текста који може да

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

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

m0 и m1, које су такве да је код једне од њих, то што сазнаје има вредност 0,

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

битова поруке - тада m0 и m1 само треба да имају

различити XOR свих битова у поруци, и нападач А би могао

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

семантички безбедна, никаква информација се не открива

ефикасном нападачу. То је управо и појам савршене тајности, али

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

Следеће што желим да вам покажем је да је једнократна бележница

семантички безбедна, и боље би било да јесте, зато што је

и више од тога, она је савршено безбедна. Погледајмо зашто ово важи.

Још једном посматрамо овакве огледе, дакле претпоставимо да нападач претендује

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

да избаци две поруке, m0 и m1, исте дужине.

Шта добија као изазов? Добија или шифровану

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

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

У огледу 0, добија шифровану m0, а у огледу 1, добија

шифровану m1. Поставља се питање, која је предност нападача А

над једнократном бележницом? Подсећам вас да је својство једнократне бележнице

да је k XOR m0 са расподелом истоветном са k XOR m1.

Другим речима, ово су потпуно подударне расподеле.

То је својство XOR - ако XOR-ујемо случајни

кључ k са било чим, m0 или m1, добијамо униформну расподелу.

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

униформну расподелу шифрата. И зато ће да се понаша на потпуно

исти начин у оба случаја, зато што добија потпуно исту расподелу на улазу.

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

безбедна. Занимљиво је то што, не само што је семантички безбедна,

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

на ефикасне нападаче. Нема нападача, колико год паметан био, који

би могао да разликује k XOR m0 од k XOR m1, зато што су ове две

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

Тиме смо завршили са дефиницијом семантичке безбедности, и следеће што ћемо

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

семантички безбедна.