A szerzői jog védelme a matematika eszközeivel

A szerz˝ oi jog v´ edelme a matematika eszk¨ ozeivel Avagy hogyan ne hamis´ıtsunk digit´alis dokumentumot? Szakdolgozat

M´atray P´eter matematika tan´ar szak [email protected]

T´emavezet˝o:

Grolmusz Vince egyetemi docens

E¨otv¨os Lor´and Tudom´anyegyetem Term´eszettudom´anyi Kar Sz´am´ıt´og´eptudom´anyi Tansz´ek Budapest, 2003

Tartalomjegyz´ ek 1. Bevezet´ es 1.1. A dolgozat t´em´aja . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. A dolgozat fel´ep´ıt´ese . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3 4

2. Matematikai eszk¨ oz¨ ok 2.1. Hash f¨ uggv´enyek . . . . . . . . . . . . . . . . . . . . 2.2. Titokmegoszt´as . . . . . . . . . . . . . . . . . . . . . 2.3. Egyir´any´ u f¨ uggv´enyek ´es pszeudorandom gener´atorok 2.4. Chernoff t´etele . . . . . . . . . . . . . . . . . . . . .

. . . .

6 6 7 8 9

3. Digit´ alis ujjlenyomatok 3.1. Elnevez´esek, jel¨ol´esek . . . . 3.2. N´eh´any sz´o a modellekr˝ol . 3.3. Defin´ıci´ok . . . . . . . . . . 3.4. Igazs´agos k´odok . . . . . . . 3.5. Kij´atszhatatlan k´odok . . . 3.6. A k´odhossz jav´ıt´asa . . . . . 3.7. Optim´alis ujjlenyomat-k´odok

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

11 13 13 14 16 20 28 29

4. Dinamikus alkalmaz´ asok ´ 4.1. Attekint´ es . . . . . . . . . . . . . . . 4.2. A trivi´alis megold´as . . . . . . . . . . 4.3. A s´ema fel´ep´ıt´ese . . . . . . . . . . . 4.4. A nyomoz´o s´em´ak kategoriz´al´asa . . 4.5. A legegyszer˝ ubb eset: egyetlen ´arul´o 4.6. K´et ´arul´o . . . . . . . . . . . . . . . 4.7. Tetsz˝oleges m´eret˝ u koal´ıci´ok . . . . . 4.8. T¨obb kulcsos dek´oderek . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

31 31 33 33 37 39 42 47 49

. . . . . . . .

51 51 52 53 54 54 56 59 61

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

5. Rejtjelezett m˝ usorsz´ or´ as 5.1. K´et trivi´alis s´ema . . . . . . . . . . . . . . . . . . 5.2. A s´ema fel´ep´ıt´ese . . . . . . . . . . . . . . . . . . 5.3. Defin´ıci´ok . . . . . . . . . . . . . . . . . . . . . . 5.4. N´eh´any z´er´o-¨ uzenet s´ema . . . . . . . . . . . . . . 5.4.1. Egy kombinatorikus konstrukci´o . . . . . . 5.4.2. Egyir´any´ u f¨ uggv´enyekre ´ep¨ ul˝o konstrukci´o 5.4.3. Egy sz´amelm´eleti konstrukci´o . . . . . . . 5.5. Magasabb v´edetts´eg˝ u s´em´ak . . . . . . . . . . . .

1

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

6. Digit´ alis v´ızjelek lehets´ eges alkalmaz´ asai 6.1. Ad´as-ellen˝orz´es . . . . . . . . . . . . . . 6.2. Tulajdonos azonos´ıt´asa . . . . . . . . . . 6.3. Tulajdonjog bizony´ıt´asa . . . . . . . . . 6.4. Hiteles´ıt´es . . . . . . . . . . . . . . . . . 6.5. Digit´alis ujjlenyomatok . . . . . . . . . . 6.6. M´asol´asv´edelem . . . . . . . . . . . . . . 6.7. Rejtett kommunik´aci´o . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

64 64 64 65 66 66 66 67

7. Kriptogr´ afia az iskol´ aban

68

¨ 8. Osszefoglal´ as 8.1. Tov´abbi eredm´enyek, nyitott k´erd´esek 8.1.1. Aszimmetrikus ujjlenyomatok 8.1.2. Anonim ujjlenyomatok . . . . 8.1.3. M´eg hat´ekonyabb nyomoz´as .

69 70 70 70 71

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

K¨ osz¨ onetnyilv´ an´ıt´ as

71

Hivatkoz´ asok

72

2

1.

Bevezet´ es

A k¨ ul¨onb¨oz˝o titkos´ır´asok mindig is fontos szerepet j´atszottak a t¨ort´enelemben. Sokszor csat´ak kimenetele, vagy ´eppen uralkod´ok sorsa m´ ult azon, hogy siker¨ ult-e biztons´agosan c´elba juttatni egy-egy u ¨zenetet. Ma m´ar nem csak a h´ırszerz´es, a katonas´ag vagy a diplom´acia tart ig´enyt a titkos inform´aci´ocser´ere, hanem az u ¨zleti ´elet szerepl˝oi ´es a h´etk¨oznapi ember is. A rejtjelez´es vil´aga a sz´am´ıt´og´eph´al´ozatok elterjed´es´evel belopta mag´at a mindennapi ´elet¨ unkbe. Ahogy az interneten bonyol´ıtott tranzakci´oink egyre n´elk¨ ul¨ozhetetlenebb´e v´alnak, u ´gy n¨ovekszik a rejtjelez˝o elj´ar´asok szerepe a polg´ari ´eletben. A titkos´ır´assal foglalkoz´o tudom´any´ag (kriptogr´afia) feladata, hogy megold´asokat k´ın´aljon a biztons´agos kommunik´aci´ora. Vele p´arhuzamosan fejl˝odik a k¨ ul¨onb¨oz˝o titkos´ır´asok megfejt´es´et c´elul kit˝ uz˝o kriptoanal´ızis. (E k´et ter¨ uletet egy¨ uttesen szok´as a kriptol´ ogia sz´oval illetni.) A titkos´ır´asok (´es azok megfejt´es´enek) elm´elete az egyik legizgalmasabb alkalmaz´asi ter¨ ulete a sz´am´ıt´og´eptudom´anynak, hiszen mindig is lesznek olyan titkaink, ´ amelyeket (ak´ar ´ori´asi befektet´esek ´ar´an is) meg szeretn´enk ´ovni a k¨ ulvil´agt´ol. Es mindig lesznek olyanok, akik minden lehets´eges er˝oforr´ast felhaszn´alnak az´ert, hogy megfejthess´ek titkainkat.

1.1.

A dolgozat t´ em´ aja

A dolgozat a kriptogr´afia egy speci´alis ter¨ ulet´et mutatja be, amelynek alapk´erd´ese: Hogyan lehet a szerz˝oi jogok v´edelm´et ´ at¨ ultetni digit´ alis k¨ ornyezetbe? 1 A klasszikus jog sok-sok ´eve kialakult gyakorlat alapj´an ´ıt´eli meg a szerz˝oi joggal val´o vissza´el´est. Sokszor el˝ofordul p´eld´aul, hogy egy fot´ou ¨gyn¨oks´egt˝ol csak egyetlen megjelen´esre megv´as´arolt k´epet t¨obbsz¨or is felhaszn´alnak. Ha az u ¨gyn¨oks´eg perre viszi a dolgot, akkor k¨onnyen igazolni tudja, hogy a k´ep az ¨ov´e: a negat´ıvok egy´ertelm˝ u bizony´ıt´ekk´ent szolg´alnak. Persze vannak ter¨ uletek, ahol sokkal nehezebb a helyzet. Ha egy zseni´alis fest˝o ´altal k´esz´ıtett zseni´alis hamis´ıtv´annyal van dolgunk, akkor egyr´eszt neh´ez meg´allap´ıtani, hogy a k´ep nem eredeti, m´asr´eszt rem´enytelen v´allalkoz´as felder´ıteni, hogy ki a hamis´ıt´o. M´eg ha kifinomult m´odszerekkel el is jutunk a hamis´ıt´ohoz, hogyan bizony´ıtjuk r´a, hogy val´oban ˝o k´esz´ıtette a k´opi´at? Ugyanezek a k´erd´esek felmer¨ ulnek akkor is, ha digit´alis term´ekekr˝ol van sz´o. S˝ot, a probl´ema m´eg ´eget˝obb. Olyan fest˝o, aki j´atszi k¨onnyeds´eggel hamis´ıt Picasso-t, viszonylag ritk´an sz¨ uletik. Ezzel ellent´etben egy zenei cd lem´asol´asa ´altal´aban nem 1

Az angol szakirodalomban copyright protection-nek nevezik ezt a t´emak¨ort.

3

jelent t´ ul nagy kih´ıv´ast. Ha pedig valaki tud cd-t, szoftvert, digit´alis fot´ot, vide´ot m´asolni, akkor tud bel˝ole sokat m´asolni. A digit´alis term´ekek t¨omegm´asol´asa nem ´ mindez megtehet˝o u jelent technikai probl´em´at. Es ´gy, hogy a lebuk´asnak nagyon pici az es´elye. Felmer¨ ul teh´at az ig´eny olyan eszk¨oz¨ok kifejleszt´es´ere, amelyek egy ,,digit´alis szerz˝oi jogi” per eset´en is bizony´ıt´o er˝ovel rendelkeznek. Ak´armilyen u ¨gyes is a fest˝o, a m´asolat sosem lesz t¨ok´eletes. A digit´alis k´opia azonban minden r´eszlet´eben pontos m´asa lesz az eredetinek. ´Igy teljess´eggel kiz´art, hogy azonos´ıtani lehessen a b˝ un¨ost, hiszen a m´asolatok b´armelyik jogos felhaszn´al´ot´ol sz´armazhatnak. Ez l´atsz´olag a hamis´ıt´onak kedvez: csek´ely befektet´essel az eredetivel egyez˝o min˝os´eg˝ u term´eket tud el˝o´all´ıtani, kis kock´azattal. Ez a fegyver azonban k¨onnyed´en a hamis´ıt´o ellen ford´ıthat´o. Ha minden eladott term´ekbe be´agyazunk egy-egy (k´opi´ank´ent k¨ ul¨onb¨oz˝o) jelet, ´es feljegyezz¨ uk, hogy kinek melyik p´eld´anyt adtuk el, akkor a hamis´ıt´o k¨onnyen elfoghat´o. Csak meg kell vizsg´alni, hogy a fekete piacon kaphat´o hamis´ıtv´anyba melyik jel van be´agyazva, ´es m´aris azonos´ıthat´o a m´asolatok forr´asa.

1.2.

A dolgozat fel´ ep´ıt´ ese

A dolgozat v´az´at a 3-5. r´esz alkotja. Ezt megel˝oz˝oen a 2. r´eszben ´attekintj¨ uk, hogy milyen matematikai fogalmak ker¨ ulnek felhaszn´al´asra a dolgozatban. A 3. fejezetben egy konkr´et alkalmaz´asra f´okusz´alunk: digit´ alis ujjlenyomatokr´ ol lesz sz´o. Ezek tulajdonk´eppen speci´alis k´odok, amelyek lehet˝ov´e teszik sz´amunkra azt, hogy a fent le´ırt m´odon minden eladott p´eld´anyt megjel¨olj¨ unk egy-egy egyedi k´odsz´oval. Az ilyen k´odok vizsg´alata az´ert v´alik ´erdekess´e, mert a felhaszn´al´ok sz¨ovetkezhetnek. Ha t¨obben ¨ossze´allnak, ´es u ´n. koal´ıci´ oba t¨om¨or¨ ulnek, akkor ki tudj´ak j´atszani a rendszert. Ilyenkor m´ar nem kell felt´etlen¨ ul ,,vakon” m´asolniuk a dokumentumot: ak´ar ¨ossze is hasonl´ıthatj´ak a k´opi´aikat, ´es felder´ıthetik, hogy hol van elhelyezve abban az ujjlenyomat. Mi olyan k´odot szeretn´enk konstru´alni, ´ amelyet m´eg sz¨ovetkez´essel sem lehet kij´atszani. Altal´ aban fel kell tenn¨ unk azt, hogy a koal´ıci´o az ujjlenyomat felfedezett r´esz´et ak´ar olvashatatlann´a is teheti. (P´eld´aul kit¨or¨olheti.) L´atni fogjuk, hogy ha ezt megengedj¨ uk, akkor elm´eletileg is lehetetlen olyan k´odot k´esz´ıteni, amely alapj´an 100%-os biztons´aggal elfoghat´o a koal´ıci´o egy tagja. K´enytelenek vagyunk olyan k´odokat alkalmazni, amelyek valamilyen pici  hibaval´osz´ın˝ us´eggel kij´atszhat´ok. A legklasszikusabb ilyen k´od a Boneh-Shaw-f´ele k´od, amelyet r´eszletesen bemutatunk. Megeml´ıtj¨ uk m´eg, hogy Tardos G´abornak nemr´eg siker¨ ult optim´alis hossz´ us´ag´ u v´eletlen ujjlenyomat-k´odot konstru´alnia. A 4. r´eszben ugyanezt a probl´em´at vizsg´aljuk meg egy m´as modellben: elvetj¨ uk azt a feltev´est, hogy az ujjlenyomat felfedezett r´eszeit a koal´ıci´o olvashatatlann´a teheti. Ez a l´ep´es csak n´eh´any, u ´n. dinamikus alkalmaz´ as eset´eben ´allja meg a hely´et. 4

Azok a rendszerek tartoznak ide, ahol az ujjlenyomatnak kett˝os szerepe van. Nem csup´an a hamis´ıt´o ut´ani nyomoz´ast szolg´alja, hanem a felhaszn´al´onak is sz¨ uks´ege van r´a a term´ek m˝ uk¨od´es´ehez. Az ujjlenyomat egyben egy kulcs is, amely n´elk¨ ul haszn´alhatatlan a rendszer. Ha egy felhaszn´al´o valahol olvashatatlann´a tenn´e az ujjlenyomatot, akkor egyben a kulcsot is elrontan´a, ´es ´ıgy ´ertelmetlenn´e v´alna a sokszoros´ıt´as. Ezeket a rendszereket u ´gy k´epzelj¨ uk el, hogy van egy k¨ozpont, az adatszolg´altat´o, aki a kulcsok (ujjlenyomatok) kioszt´as´at v´egzi. Minden felhaszn´al´o kap egy dek´odert, amelybe be van ´ep´ıtve az adott felhaszn´al´ohoz rendelt szem´elyes kulcs. Ez a dek´oder lehet hardver, vagy szoftver is. Az adatszolg´altat´o u ¨zeneteket ad le, amit csak az tud visszafejteni, akinek van dek´odere, m˝ uk¨od˝o kulcsokkal. Ebben a modellben hamis´ıt´asnak az min˝os¨ ul, amikor n´eh´any felhaszn´al´o ¨ossze´all, ´es megpr´ob´al ´ep´ıteni egy kal´oz dek´odert, amelybe a saj´at kulcsaikat (ujjlenyomataikat) ´ep´ıtik be. Az angol irodalom traitor tracing 2 n´even hivatkozik erre a probl´emak¨orre, ´es az ´altalunk is bemutatott alapvet˝o eredm´enyeket Chor, Fiat, Naor ´es Pinkas publik´alta. Az 5. r´esz szervesen kapcsol´odik a 4. r´eszhez, de a t´em´aja m´ar nem a szerz˝oi jog v´edelme. Egy dinamikus alkalmaz´asok eset´en felmer¨ ul˝o speci´alis kulcskioszt´asi probl´em´at t´argyalunk itt. Olyan protokollokat mutatunk be, amelyek lehet˝ov´e teszik az adatszolg´altat´o sz´am´ara, hogy lesz˝ uk´ıtse (vagy b˝ov´ıtse) azok k¨or´et, akik dek´odolni tudj´ak az ad´ast. S˝ot, mindezt dinamikusan tudja megtenni an´elk¨ ul, hogy u ´j kulcsokat kellene gener´alni a felhaszn´al´ok sz´am´ara. Ennek ´ori´asi jelent˝os´ege van. Ha ugyanis a 4. r´eszben t´argyalt rendszereket alkalmass´a tessz¨ uk erre a dinamikus kulcskezel´esre, akkor el´eg egyetlen elfogott kal´oz dek´oder ahhoz, hogy az ¨ osszes kal´oz dek´odert letiltsuk. Gondoljunk bele, hogy ez mennyivel hat´ekonyabb m´odszer, mint az ¨osszes kal´oz dek´oder felkutat´asa ´es megsemmis´ıt´ese. Ezek a rendszerek azonban m´ashol is alkalmazhat´ok. L´atni fogjuk, hogy a legterm´eszetesebben ad´od´o felhaszn´al´asi ter¨ ulet a fizet˝os telev´ız´oad´asokkal kapcsolatos. A 6. r´eszben kit´er¨ unk arra, hogy ´altal´aban milyen alkalmaz´asokra adhatnak lehet˝os´eget a t´em´aban v´egzett kriptogr´afiai kutat´asok. V´eg¨ ul a 7. r´eszben sz´olunk arr´ol, hogy milyen lehet˝os´egek k´ın´alkoznak a kriptogr´afia tan´ıt´as´ara. Az ¨osszefoglal´asban pedig ´attekintj¨ uk a bemutatott eredm´enyeket, illetve megeml´ıt¨ unk n´eh´any tov´abbi kutat´asi ter¨ uletet, nyitott probl´em´at.

2

Magyarul tal´ an az ,,´ arul´ ok lebuktat´asa” kifejez´es hangzik a legjobban.

5

2.

Matematikai eszk¨ oz¨ ok

Ebben a r´eszben megpr´ob´aljuk r¨oviden ¨osszefoglalni, hogy milyen matematikai eszk¨oz¨oket haszn´alunk a dolgozatban. A hash f¨ uggv´enyek k¨ozponti szerepet j´atszanak a kriptogr´afi´aban. El˝osz¨or ezekr˝ol ejt¨ unk n´eh´any sz´ot. Ezut´an r¨oviden sz´olunk a ´ titokmegoszt´as fogalm´ar´ol. Attekintj¨ uk az egyir´any´ u f¨ uggv´enyekkel ´es a pszeudorandom gener´atorokkal kapcsolatos legalapvet˝obb fogalmakat is, amelyeket azt´an az ad´asrejtjelez´esn´el fogunk felhaszn´alni. V´egezet¨ ul pedig bizony´ıt´as n´elk¨ ul kimondjuk Chernoff t´etel´enek k´et k¨ ul¨onb¨oz˝o alakj´at. Ez a k´et egyenl˝otlens´eg fontos szerepet j´atszik majd a k¨ ul¨onb¨oz˝o kombinatorikus val´osz´ın˝ us´egek becsl´es´eben. Hangs´ ulyozzuk, hogy ebben a r´eszben legink´abb az ´erthet˝os´egre t¨orekedt¨ unk. Az al´abb le´ırtakkal intuit´ıv k´epet k´ıv´anunk ny´ ujtani egy-egy fogalomr´ol vagy probl´em´ar´ol, ´es sok ponton eg´eszen biztosan prec´ızebb´e lehetne tenni a le´ır´ast.

2.1.

Hash f¨ uggv´ enyek

A hash f¨ uggv´enyek vizsg´alata az u ´n. hash v. has´ıt´ o t´abl´azatokkal kapcsolatban ker¨ ult el˝ot´erbe. Ezek a t´abl´azatok a t¨omb¨ok hat´ekony c´ımz´esi technik´aj´at pr´ob´alj´ak ¨otv¨ozni a dinamikus adatszerkezetek helytakar´ekoss´ag´aval. Egy hash f¨ uggv´eny egy U halmazt3 k´epez le egy j´oval kisebb halmazra: h : U → {1, . . . , t} , ahol az U -beli kulcsok sz´ama tipikusan |U | >> t. Egy has´ıt´o t´abl´azat tulajdonk´eppen nem m´as, mint egy t elem˝ u t¨omb. Ha egy x ∈ U kulcsot t´arolni szeretn´enk, akkor azt a t¨omb h(x)-edik rekesz´ebe tessz¨ uk.4 A hash f¨ uggv´enyekkel kapcsolatos alapvet˝o probl´em´at az u ¨tk¨ oz´esek jelentik. K´et k¨ ul¨onb¨oz˝o kulcs, x ´es y u ¨tk¨ozik, ha a lenyomataik (azaz a h-szerinti k´epeik) megegyeznek: h(x) = h(y). Ha x-et m´ar elt´aroltuk a t´abl´azatban, akkor az y sz´am´ara u ´j helyet kell keresni. J´o n´eh´any olyan hash f¨ uggv´enyt siker¨ ult k´esz´ıteni, amelyek v´arhat´oan kev´es u ¨tk¨oz´est produk´alnak. De term´eszetesen sok m´odszert fejlesztettek ki a kulcs¨ utk¨oz´esek felold´as´ara is. Legyen C ⊂ U olyan, hogy |C| ≤ t. Egy h hash-re azt mondjuk, hogy perfekt a C-hez, ha a h|C f¨ uggv´eny injekt´ıv.5 Azaz tetsz˝olegesen v´alasztott x, y ∈ C-re igaz, hogy x 6= y ⇒ h(x) 6= h(y) . Egy ilyen perfekt hash f¨ uggv´eny teh´at u ¨tk¨oz´esmentes a C r´eszhalmazon. A perfekt hash f¨ uggv´enyek kulcsszerepet j´atszanak a 4. ´es 5. r´esz konstrukci´oiban. Aki 3

U -t szok´ as kulcsuniverzumnak nevezni. Altal´ aban persze nem mag´ at a kulcsot t´aroljuk, hanem egy mutat´ot, amely az x kulcs´ u rekordra mutat. 5 h|C -vel a h hash C-re val´ o megszor´ıt´as´at jel¨olt¨ uk. 4´

6

r´eszletesebben szeretne t´aj´ekoz´odni a perfekt hash f¨ uggv´enyekkel kapcsolatban, az b˝os´eges forr´ast tal´alhat a [8] monogr´afi´aban. Megjegyezz¨ uk, hogy a kriptogr´afi´aban sz´eles k¨orben haszn´alt hash f¨ uggv´enyek bizonyos ´ertelemben t¨obbet tudnak azokn´al, amelyeket mi haszn´alunk. A hash f¨ uggv´enyeket legink´abb hiteles´ıt´esi c´elokra szok´as felhaszn´alni. Ilyenkor ´erdemes a mi´enkt˝ol kiss´e elt´er˝o defin´ıci´ot adni, ahol a hash nem m´as, mint egy {0, 1}∗ → {0, 1}n lek´epez´es. Eszerint a hash f¨ uggv´eny egy tetsz˝oleges m´eret˝ u digit´alis dokumentum6 hoz egy fix hossz´ u ´ert´eket rendel. Ilyen hash f¨ uggv´enyekkel p´eld´aul kimutathat´o az, hogy egy dokumentum hiteles-e, t¨ort´ent-e benne valamilyen v´altoz´as. Ha feljegyezt¨ uk az eredeti dokumentum lenyomat´at, akkor csak ¨ossze kell hasonl´ıtanunk a n´alunk l´ev˝o p´eld´any lenyomat´aval. Ha a lenyomat megegyezik, akkor a dokumentum eredeti. Ahhoz, hogy egy hash f¨ uggv´eny biztons´ agosan alkalmazhat´o legyen, n´eh´any tov´abbi felt´etelnek is meg kell felelnie: • Gyakorlatilag legyen lehetetlen egy adott z lenyomathoz olyan dokumentumot tal´alni, amelynek a lenyomata ´eppen z.7 • Ha egy dokumentumot ak´ar csak egy ,,picit” is megv´altoztatunk, a lenyomat ,,nagyon”8 v´altozzon meg. • Gyakorlatilag legyen lehetetlen k´et olyan dokumentumot tal´alni, amelynek ugyanaz a lenyomata. Meggondolhat´o, hogy a h´arom felt´etel k¨oz¨ ul a harmadik a leger˝osebb.9 Ha egy hash f¨ uggv´eny kiel´eg´ıti az utols´o felt´etelt, akkor az els˝o kett˝ot is. A 6.4 r´eszben hiteles´ıt´eshez haszn´alt hash f¨ uggv´enyeket ebben az ut´obbi, kriptogr´afiai ´ertelemben kell tekinteni.

2.2.

Titokmegoszt´ as

A titokmegoszt´as egy fontos r´eszter¨ ulete a kriptogr´afi´anak. A c´el az, hogy egy titkot u ´gy osszunk meg n j´at´ekos k¨oz¨ott, hogy a titokhoz egymaga senki ne tudjon hozz´af´erni. Kicsit ´altal´anosabbak azok a s´em´ak, amelyek 2 helyett valamilyen k ≤ n k¨ usz¨ob´ert´ekkel rendelkeznek. Egy ilyen k-k¨ usz¨ob s´em´aban b´armely k j´at´ekos meg tudja fejteni a titkot. Viszont ha enn´el kevesebben vannak, akkor k´eptelenek felt¨orni az elrejtett u ¨zenetet. 6

Ebben az esetben digit´ alis dokumentum alatt egy v´eges bitsorozatot ´ert¨ unk. Egy feladatot ,,gyakorlatilag lehetetlen” elv´egezni, ha nincs r´a polinomi´alis algoritmus. 8 A ,,nagyon” itt azt jelenti, hogy nagyj´ab´ol a bitek fel´en. 9 Azt, hogy az els˝ o k´et felt´etel nem ad elegend˝o biztons´agot, a sz¨ ulet´esnap-paradoxonhoz hasonl´o elvvel lehet igazolni. Att´ ol, hogy egy adott lenyomathoz neh´ez kulcsot tal´alni, m´eg lehet, hogy k¨onny˝ u valamilyen j´ o kulcs-lenyomat p´art tal´alni. 7

7

Most csak a legegyszer˝ ubb titokmegoszt´asi s´em´at mutatjuk be, amely a One Time Pad-re ´ep¨ ul. Legyen r ∈ {0, 1}s a titok, amelyet szeretn´enk felosztani l r´eszre u ´gy, hogy az ¨osszes r´esz-titok kelljen a visszafejt´eshez. Ezt k¨ovetkez˝o ¨otlettel tehetj¨ uk meg. V´alasszunk l bitsorozatot v´eletlenszer˝ uen {0, 1}s -b˝ol u ´gy, hogy azok bitenk´enti mod 2 ¨osszege ´eppen r legyen: r 1 ⊕ r2 ⊕ . . . ⊕ rl = r L´athat´o, hogy az r titok megfejt´es´ehez az ¨osszes ri darabra sz¨ uks´eg van. Ha ak´ar csak egyetlen r´esztitok is hi´anyzik, akkor semmit sem tudunk r-r˝ol. Hiszen – a hi´anyz´o darabt´ol f¨ ugg˝oen – r ¨osszes bitje lehet 0 ´es 1 is. Ilyen v´eletlen bitsorozatok a k¨ovetkez˝o tr¨ ukkel v´alaszthat´ok. Az els˝o l − 1 bitsorozatot v´alasszuk ki v´eletlenszer˝ uen. Jel¨olj¨ uk ezeket r1 , . . . , rl−1 -gyel. K´epezz¨ uk ezut´an az r1 ⊕ r2 ⊕ . . . ⊕ rl−1 ⊕ r = rl o¨sszeget, amellyel ad´odik az l-dik titokdarab. Elmondhat´o, hogy rl is v´eletlen, hiszen az r ´es egy v´eletlen bitsorozat ¨osszegek´ent ad´odott. Ezt a fajta titokmegoszt´ast a rejtjelez˝o kulcs ,,feldarabol´as´ara” haszn´aljuk majd a 4. ´es 5. r´eszben.

2.3.

Egyir´ any´ u f¨ uggv´ enyek ´ es pszeudorandom gener´ atorok

Egy f f¨ uggv´enyre akkor mondjuk azt, hogy egyir´ any´ u, ha ˝ot mag´at k¨onny˝ u, az inverz´et viszont neh´ez kisz´amolni. Az f f¨ uggv´enyt k¨onny˝ u kisz´amolni, ha l´etezik olyan polinomi´alis algoritmus, amely egy x bemenetre kisz´am´ıtja f (x)-et. Ez a k¨onny˝ u ir´any. A neh´ez ir´any az invert´al´as: b´armely v´eletlent haszn´al´o polinomi´alis algoritmus eset´en elhanyagolhat´o annak a val´osz´ın˝ us´ege, hogy az algoritmus egy −1 v´eletlen y bemenethez tal´al egy x ∈ f (y)-beli elemet. ´ Altal´ aban mit v´arunk el egy j´o rejtjelez˝o algoritmust´ol? Egyr´eszt azt, hogy lehessen vele gyorsan titkos´ıtani, m´asr´eszt pedig azt, hogy a rejtjelezett sz¨ovegb˝ol neh´ez legyen visszak¨ovetkeztetni az eredetire. K¨onny˝ u felfedezni a p´arhuzamot ezen elv´ar´asok, ´es az egyir´any´ u f¨ uggv´enyek defin´ıci´oja k¨oz¨ott. Nem meglep˝o teh´at, hogy az egyir´any´ us´ag k¨ozponti fogalom a modern kriptogr´afi´aban. Ennek ellen´ere nem tudni, hogy l´etezik-e egy´altal´an ilyen f¨ uggv´eny. T¨obb jel¨olt is van azonban, amelyr˝ol sejthet˝o, hogy egyir´any´ u. Ilyen p´eld´aul a diszkr´et logaritmus probl´ema vagy a faktoriz´aci´o probl´em´aja is. Ezekre j´ol m˝ uk¨od˝o, sz´eles k¨orben elterjedt rejtjelez˝o rendszerek ´ep¨ ulnek. A gyakorlatban – egyel˝ore – meg´allj´ak a hely¨ uket. De fogalmazhatn´ank u ´gy is, hogy ezen rendszerek elm´eleti biztons´aga csup´an hit k´erd´ese. A kriptogr´afia egy m´asik alapvet˝o eszk¨oze a pszeudorandom gener´ator. Intuit´ıve pszeudorandom gener´ator alatt egy olyan polinom id˝oben kisz´amolhat´o g f¨ uggv´enyt 8

´ert¨ unk, amely egy r¨ovid val´odi v´eletlen x sz´amhoz egy olyan g(x) ´ert´eket rendel, ami ,,´ ugy n´ez ki, mintha v´eletlen lenne”. Ez azt jelenti, hogy nincs olyan v´eletlent haszn´al´o polinomi´alis algoritmus, amely k¨ ul¨onbs´eget tudna tenni g(x) ´es egy val´odi v´eletlen sz´am k¨oz¨ott. A pszeudorandom gener´atorok seg´ıts´eg´evel ak´ar csak egyetlen val´odi v´eletlen magb´ol tetsz˝oleges sok ´alv´eletlent lehet el˝o´all´ıtani. Ezek az ´alv´eletlenek gyakorlatilag megk¨ ul¨onb¨oztethetetlenek a val´odi v´eletlenekt˝ol. ´Igy lehet˝ov´e v´alik az, hogy a sok v´eletlent haszn´al´o algoritmusainkat ´atalak´ıtsuk kev´es v´eletlent haszn´al´o algoritmusokk´a. Sok ´erdekes ¨osszef¨ ugg´es tal´alhat´o a pszeudorandom gener´atorok ´es az egyir´any´ u f¨ uggv´enyek k¨oz¨ott ([12]). A legfontosabb kapcsolatot fogalmazza meg a k¨ovetkez˝o t´etel. 2.1. T´ etel. Pontosan akkor l´etezik pszeudorandom gener´ ator, ha l´etezik egyir´ any´ u f¨ uggv´eny. Az ´all´ıt´as egyik ir´anya k¨onny˝ u, a m´asik meglehet˝osen neh´ez. Egy pszeudorandom gener´atorb´ol k¨onnyen lehet egyir´any´ u f¨ uggv´enyt k´esz´ıteni, a ford´ıtott ir´any azonban messze nem trivi´alis. Mutatunk egy bizony´ıt´as v´azlatot a k¨onny˝ u ir´anyra. n 2n Legyen g : {0, 1} → {0, 1} egy pszeudorandom gener´ator. Az f (x, y) = g(x) f¨ uggv´eny sz¨ uks´egk´eppen egyir´any´ u lesz (x, y ∈ {0, 1}n ). Ha nem lenne az, akkor g sem lenne pszeudorandom. Ez a k¨ovetkez˝o gondolatmenettel indokolhat´o. Tegy¨ uk fel, hogy l´etezik olyan polinom idej˝ u algoritmus, amely egy v´eletlen¨ ul v´alasztott f (x, y) ´ert´ekb˝ol meg tudja hat´arozni x-et ´es y-t. Ha ennek az algoritmusnak f (x, y) = g(x) helyett egy val´odi v´eletlen r ∈ {0, 1}n bitsorozatot adunk be, akkor elhanyagolhat´o annak az es´elye, hogy r-nek van f -inverze.10 Egy-egy bitsorozatr´ol ezzel az algoritmussal teh´at j´o es´ellyel eld¨onthet˝o, hogy g kimenete-e, avagy val´odi v´eletlen. A pszeudorandom gener´atorok az 5.4.2 konstrukci´oban j´atszanak majd szerepet. Az egyir´any´ u f¨ uggv´enyek ´es a pszeudorandom gener´atorok kriptogr´afiai vizsg´alata megtal´alhat´o [11]-ben.

2.4.

Chernoff t´ etele

A k¨ ul¨onb¨oz˝o kombinatorikus val´osz´ın˝ us´egek becsl´es´ehez sz¨ uks´eg¨ unk lesz a Chernoffkorl´atra. K´et k¨ ul¨onb¨oz˝o v´altozat´at is kimondjuk a t´etelnek. Az els˝ot a 3.18. Lem´ ıt´asban haszn´aljuk majd fel. Ezen t´etelek r´eszletes m´aban, m´ıg a m´asodikat a 4.6. All´ bizony´ıt´asa, ´es tov´abbi v´altozatok megtal´alhat´ok a [2] k¨onyv A f¨ uggel´ek´eben. 10

Mivel f a bemen˝ o 2n bitnek csup´an a fel´et haszn´alja, ez´ert legfeljebb 1/2n az es´elye annak, −1 hogy f (r) nem¨ ures.

9

2.2. T´ etel (Chernoff-korl´ at els˝ o v´ altozata). Legyenek η1 , η2 , . . . , ηb teljesen f¨ uggetlen val´ osz´ın˝ us´egi v´ altoz´ ok, ´es Prob[ ηi = 0 ] = 1/2 , Prob[ ηi = 1 ] = 1/2 . Legyen η = η1 + η2 + . . . + ηb . (η binomi´ alis eloszl´ as´ u.) Ekkor tetsz˝ oleges a > 0 eset´en   b 2 Prob η < − a < e−2a /b . 2

2.3. T´ etel (Chernoff-korl´ at m´ asodik v´ altozata). Legyenek ξ1 , ξ2 , . . . , ξl teljesen f¨ uggetlen val´ osz´ın˝ us´egi v´ altoz´ ok, ´es Prob[ ξi = 0 ] = q , Prob[ ξi = 1 ] = 1 − q . Legyen ξ = ξ1 + ξ2 + . . . + ξl . (ξ binomi´ alis eloszl´ as´ u.) Ekkor tetsz˝ oleges a > 0 eset´en   a−1 q l  e ξ ≥ aq < . Prob l aa

10

3.

Digit´ alis ujjlenyomatok

Sok term´eket ismer¨ unk, amelynek a sokszoros´ıt´asa, ut´angy´art´asa k¨onnyen megoldhat´o. A digit´alis technika elterjed´es´evel a m´asolatok k´esz´ıt´ese is egyszer˝ ubb´e, gyorsabb´a v´alt. El˝ofordul azonban, hogy vissza´elnek ezzel a lehet˝os´eggel. Olyan szem´elyek sokszoros´ıtj´ak tov´abb, ´es adj´ak el a m´asolt term´eket – jelent˝os k´art okozva ezzel a gy´art´onak –, akik arra nem jogosultak. Ezt a tev´ekenys´eget kal´ozkod´asnak h´ıvjuk. A term´eket illeg´alisan sokszoros´ıt´o felhaszn´al´ot a szakirodalom kal´ oznak, vagy ´ arul´onak nevezi. Mi a dolgozatban egys´egesen az ´arul´o kifejez´est fogjuk haszn´alni, mert ez jobban illeszkedik a k´es˝obbi fejezetek sz´ohaszn´alat´ahoz. Ha t¨obb ´arul´o sz¨ovetkezik, akkor koal´ıci´or´ ol besz´el¨ unk. Term´eszetes m´odon ad´odik az ¨otlet: minden egyes eladott term´ekbe ´agyazzunk be egy egyedi jelet. Szoftverek eset´en ezt a szerepet j´atszhatja p´eld´aul a sorozatsz´am. Ha a piacon kal´oz m´asolatokra bukkanunk, akkor el´eg megvizsg´alni az abban fellelhet˝o sorozatsz´amot, ´es m´aris azonos´ıthat´o a k´opia forr´asa, az ´arul´o. A m´odszer m˝ uk¨od´es´ehez elengedhetetlen, hogy minden eladott p´eld´any sorozatsz´am´at regisztr´aljuk a vev˝o nev´evel egy¨ utt. Az ´ıgy be´agyazott sorozatsz´amot ujjlenyomatnak nevezz¨ uk. Ez kifejez´es rendk´ıv¨ ul tal´al´o: ha valaki illeg´alis m´asolatot k´esz´ıt, akkor az ujjlenyomata (azaz: egy ˝ot egy´ertelm˝ uen azonos´ıt´o jel) rajta lesz a k´opi´akon. A rem´enyek szerint ily m´odon el lehet riasztani a felhaszn´al´okat att´ol, hogy jogosulatlan m´asolatokat k´esz´ıtsenek. Az ujjlenyomatoz´as ¨otlete nem u ´jkelet˝ u. N´eh´any sz´azaddal ezel˝ott logaritmus t´abl´azatokat v´edtek hasonl´o m´odszerekkel. Jelent´ektelen hib´akat csemp´esztek n´eh´any v´eletlenszer˝ uen kiv´alasztott logaritmus´ert´ekbe. P´eld´adul a log 3 ´ert´ek´eben a tizedesvessz˝o ut´ani 10. sz´amjegyet megv´altoztatt´ak. Ez az apr´o m´odos´ıt´as sz´amol´asi hib´at nem okozott. A t´abl´azat minden p´eld´any´at m´ask´epp jel¨olt´ek meg, ´es feljegyezt´ek, hogy melyiket kinek adt´ak el. ´Igy lehet˝ov´e v´alt egy-egy kal´oz p´eld´any forr´as´anak kinyomoz´asa. A technika megb´ızhat´os´ag´ahoz garant´alni kell azt, hogy az ujjlenyomatot se megv´altoztatni, se elt´avol´ıtani ne lehessen. Ennek ´erdek´eben az ujjlenyomatot u ´gy kell elrejteni, hogy az k´et k¨ovetelm´enynek is megfeleljen. Az egyik elv´ar´as az, hogy bel´athat´o id˝o bel¨ ul ne lehessen meg´allap´ıtani a dokumentum egy ,,r´esz´er˝ol”, hogy az ´eppen az ujjlenyomathoz tartozik-e, vagy sem. Ennek a felt´etelnek a logaritmusos t´abl´azatok ma m´ar nem feleln´enek meg: sz´am´ıt´og´eppel k¨onnyen ellen˝orizhet˝o lenne egy-egy logaritmus´ert´ek helyess´ege. Hasonl´oan, a digit´alis k´epekbe rejtett ujjlenyomatoknak nem szabad l´athat´o v´altoz´ast okozniuk a k´epen, mert ezekb˝ol k¨ovetkeztetni lehetne az ujjlenyomat hely´ere. A m´asik elv´ar´as szerint u ´gy kell be´agyazni az ujjlenyomatot, hogy az semmilyen zavart ne okozzon a term´ek funkci´oj´aban: a szoftver tov´abbra is helyesen m˝ uk¨odj¨on, a hanganyag/vide´o ne vesz´ıtsen a min˝os´eg´eb˝ol, a logaritmus t´abla haszn´alhat´o maradjon. Szoftverek eset´en p´eld´aul megtehet˝o az, hogy ,,felesleges” programr´eszeket 11

´ep´ıt¨ unk be, hogy k´es˝obb pont ezeket a r´eszeket ,,elrontva” helyezhess¨ uk el az ujjlenyomatot. Ebben a r´eszben kiz´ar´olag digit´alis dokumentumok ujjlenyomatoz´as´ar´ol esik sz´o. Digit´ alis dokumentum alatt egy v´eges Σ ´ab´ec´e f¨ol¨otti v´eges jelsorozatot ´ert¨ unk. A digit´alis dokumentum lehet p´eld´aul sz¨oveg, k´ep, hang, vide´o vagy szoftver is. Az be´agyazand´o ujjlenyomat maga is egy Σ ´ab´ec´e f¨ol¨otti sz´o. Az ujjlenyomatot ´altal´aban nem ,,eg´eszben” helyezz¨ uk el a dokumentumban, hanem bet˝ unk´ent, el˝ore meghat´arozott helyeken rejtj¨ uk el. Jelz´esnek nevezz¨ uk a dokumentum egy olyan poz´ıci´oj´at (bitj´et), ahol az ujjlenyomat egy bet˝ uje tal´alhat´o. Ezen a ponton jegyezz¨ uk meg, hogy a bit sz´ot kiss´e kiterjesztett ´ertelemben fogjuk haszn´alni. A bit ´altal´aban egy poz´ıci´ot, bet˝ ut fog jel¨olni. Ennek megfelel˝oen egy k´odsz´o 5. bitje a sz´o 5. bet˝ uj´et jelenti. El˝ofordul, hogy ezt a kifejez´est haszn´aljuk akkor is, ha az ´ab´ec´enk nem bin´aris. ´ Ujabb probl´ema mer¨ ul fel, ha t¨obb felhaszn´al´o sz¨ovetkezik. A logaritmusos p´eld´an´al maradva, ha k´et t´abl´azattulajdonos ¨ossze´all, akkor k¨onnyed´en kisz˝ urhetik az elrejtett jelz´esek egy r´esz´et. Egyszer˝ uen csak ¨ossze kell hasonl´ıtaniuk a k´et t´abl´azatot: ahol elt´er´es van, ott legal´abb az egyik¨ ukn´el biztosan egy jelz´es tal´alhat´o. Az ´ıgy kisz˝ urt poz´ıci´okra azt mondjuk, hogy az adott koal´ıci´o sz´am´ara l´ athat´ ok. A k¨ovetkez˝o ´abr´an a h´arom felhaszn´al´o az els˝o k´et jelz´est l´atja, a harmadikat nem.

az ujjlenyomat bitjei

?

?

?

1001101...

1

0

1

...0110011

1001101...

0

1

1

...0110011

1001101...

0

0

1

...0110011

3.1. ´ abra. H´arom sz¨ovetkez˝o j´at´ekos dokumentuma

12

3.1.

Elnevez´ esek, jel¨ ol´ esek

A dolgozatban a k¨ovetkez˝o sz´ohaszn´alattal fogunk ´elni: • Jelz´es: a digit´alis dokumentum azon poz´ıci´oja, ahol az ujjlenyomat egy jegy´et elrejtj¨ uk. • Ujjlenyomat: egy Σ feletti v´eges sz´o, amelynek a bet˝ uit be´agyazzuk a digit´alis dokumentumba (a jelz´eseken kereszt¨ ul). • Adatszolg´altat´o : az ujjlenyomattal ell´atott objektumok kiz´ar´olagos sz´all´ıt´oja. • Felhaszn´al´o/j´at´ekos: egy ujjlenyomattal ell´atott objektum regisztr´alt tulajdonosa. A szolg´altat´o val´oj´aban egy ujjlenyomat-k´odot defini´al, pontosan annyi k´odsz´oval, ah´any felhaszn´al´oja a rendszernek van (ezt n-nel jel¨olj¨ uk). Minden felhaszn´al´ohoz pontosan egy k´odsz´ot rendel¨ unk, amely az ˝o ujjlenyomata lesz. A felhaszn´al´o az objektum egy olyan p´eld´any´at kapja meg, amelyben a jelz´esek az ˝o k´odszav´anak megfelel˝oen lettek be´all´ıtva. T¨obb ´arul´o egy jelz´est pontosan akkor tud ´eszlelni, ha a birtokukban van k´et olyan dokumentum, amely abban a poz´ıci´oban k¨ ul¨onb¨ozik. Ilyenkor azt mondjuk, hogy az ´arul´ok l´atj´ak az adott jelz´est. Ellenkez˝o esetben l´ athatatlannak nevezz¨ uk a jelz´est. Nagyon fontos a k¨ovetkez˝o feltev´es: az objektumban elhelyezhet˝o az ujjlenyomat u ´gy, hogy a l´athatatlan jelz´eseket a felhaszn´al´ok ne tudj´ak felder´ıteni, ´es ´ıgy megv´altoztatni vagy kit¨or¨olni sem. Ez azt jelenti, hogy a felhaszn´al´ok kiz´ar´olag a saj´at dokumentumaik ¨osszehasonl´ıt´as´aval der´ıthetnek fel egy-egy jelz´est.11 Erre a tulajdons´agra, mint jel¨ol´esi felt´etelre fogunk hivatkozni, ´es k´es˝obb pontosan defini´aljuk is. A jel¨ol´esi felt´etel ´erv´enyess´eg´et a k¨ ul¨onb¨oz˝o t´ıpus´ u digit´alis dokumentumokra (f´ajlform´atumokra) egyenk´ent ellen˝orizni kell. (L´asd p´eld´aul: [6].)

3.2.

N´ eh´ any sz´ o a modellekr˝ ol

T¨obbf´ele feltev´esb˝ol is kiindulhatunk, amikor ujjlenyomat-k´odot tervez¨ unk. Alapvet˝oen n´egy k¨ ul¨onb¨oz˝o modell lehets´eges aszerint, hogy mi a v´alasz a k¨ovetkez˝o k´erd´esekre.

11

Ha ez a feltev´es nem teljes¨ ulne, akkor elk´epzelhet˝o lenne, hogy p´eld´aul egy k´epben elhelyezett ujjlenyomat (a megv´ altoztatott bitek miatt) a k´epen k¨onnyen ,,kisz´ urhat´o” k´eppontokat eredm´enyezne. Ez lehet˝ ov´e tenn´e a felhaszn´al´ok sz´am´ara, hogy l´athatatlan biteket is m´odos´ıtsanak az ujjlenyomatban.

13

• Egy l´athat´o poz´ıci´ora az ´arul´ok b´armilyen Σ-beli bet˝ ut ´ırhatnak-e, vagy csak olyat, amelyik megtal´alhat´o valamelyik¨ uk ujjlenyomat´aban ugyanazon a poz´ıci´on? • Elk´epzelhet˝o-e az, hogy az ´arul´ok egy l´athat´o jelz´est egyszer˝ uen kit¨or¨olnek, vagy olvashatatlann´a tesznek? (Azaz form´alisan egy ? ∈ / Σ ,,olvashatatlan” jelet ´ırnak arra a helyre.) Ebben a r´eszben azt a modellt vizsg´aljuk, amikor az ´arul´ok b´armilyen bet˝ ut ´ırhatnak a l´athat´o helyekre, ak´ar ?-t is. Ez meglehet˝osen val´oszer˝ u modell, mivel semmilyen korl´atoz´ast nem tesz az ´arul´ok viselked´es´ere. Azonban a m´asik h´arom modellnek is van l´etjogosults´aga. Sok esetben feltehet˝o, hogy az ´arul´ok csak a saj´at jegyeik k¨oz¨ ul v´alogathatnak a hamis´ıt´asn´al. Ez a helyzet akkor, ha egy jegy valamilyen bonyolult objektumk´ent ker¨ ul megval´os´ıt´asra: ilyenkor az ´arul´ok k´enytelenek a saj´at objektumaikat felhaszn´alni. Egy film ujjlenyomatoz´as´an´al p´eld´aul elk´epzelhet˝o egy hasonl´o megold´as: egy jelz´est az hat´aroz meg, hogy egy adott jelenet milyen kamera-be´all´ıt´asb´ol lett felv´eve. Ilyenkor a kal´ozok ¨osszev´aghatnak egy olyan filmet, amelyben a saj´at k´opi´aikban tal´alhat´o kamera-be´all´ıt´asok v´altakoznak, de ezekt˝ol elt´er˝o sz¨ogben forgatott jelenetet nem tudnak felhaszn´alni. A dinamikus alkalmaz´asokn´al l´atni fogjuk, hogy bizonyos esetekben az olvashatatlan jel (?) haszn´alata is kiz´arhat´o. P´eld´aul akkor, ha az ujjlenyomat bet˝ ui sz¨ uks´egesek a term´ek m˝ uk¨od´es´ehez (p´eld´aul kulcsk´ent szolg´alnak valamilyen rejtjelez´es visszafejt´es´ehez).

3.3.

Defin´ıci´ ok

A Σ egy s bet˝ ub˝ol ´all´o v´eges ´ab´ec´e, ahol az elemeket az 1, . . . , s eg´eszekkel azo12 nos´ıtjuk. A v, w szavak konkaten´aci´oj´at v · w-vel, n´eha egyszer˝ uen vw-vel jel¨olj¨ uk. Egy w sz´o i. bet˝ uj´ere a wi jel¨ol´essel hivatkozunk. A felhaszn´al´okat az U = {1, . . . n} halmazzal reprezent´aljuk. Defini´aljuk az ujjlenyomatok Γ halmaz´at, amelyet ujjlenyomat-k´odnak is nevez¨ unk. 3.1. Defin´ıci´ o. Az n elem˝ u, l hossz´ u szavakb´ ol ´ all´ o Γ = {w(1) , . . . , w(n) } ⊆ Σl halmazt (l, n)-k´odnak nevezz¨ uk. Az ui felhaszn´ al´ ohoz a w(i) k´ odsz´ ot rendelj¨ uk (1 ≤ i ≤ n). A Γ-ra u ´gy is hivatkozunk, mint a k´odk¨onyvre. A k´od i. k´odszava lesz az i. felhaszn´al´o ujjlenyomata, amelyet w(i) -vel jel¨ol¨ unk. Felhaszn´al´ok egy C csoportj´anak a k´odszavait ΓC -vel jel¨olj¨ uk. Mint azt eml´ıtett¨ uk, egy koal´ıci´o pontosan akkor l´at egy poz´ıci´ot, ha van k´et tagja, akiknek az adott helyen az ujjlenyomata elt´er. A koal´ıci´o ezeket a biteket tudja megv´altoztatni, amikor k´opi´akat k´esz´ıt. 12

K´es˝obb ´ att´er¨ unk a bin´ aris (Σ = {0, 1}) ´ab´ec´ere.

14

3.2. Defin´ıci´ o. Legyen Γ egy (l, n)-k´ od, ´es C = {u1 , . . . , ut } egy koal´ıci´ o. Egy i ∈ {1, . . . , l} eset´en azt mondjuk, hogy az i. poz´ıci´o l´athatatlan a C koal´ıci´ o sz´ am´ ara, ha (j) (k) b´ armely k´et uj , uk tagj´anak k´odszav´ ara wi = wi . Ellenkez˝ o esetben az i. poz´ıci´ ot a koal´ıci´o l´atja. A c´elunk az, hogy u ´gy rendelj¨ unk k´odszavakat a felhaszn´al´okhoz, hogy azok egy¨ uttesen se tudj´ak ´eszrev´etlen¨ ul hamis´ıtani az adatot. Els˝o l´ep´esben karakteriz´aljuk azon objektumok halmaz´at, amelyet egy adott koal´ıci´o hamis´ıtani tud. Amikor egy koal´ıci´o illeg´alis k´opi´at k´esz´ıt, akkor a l´athat´o poz´ıci´ok ´ert´ek´et tetsz˝olegesen be´all´ıthatja valamilyen Σ-beli ´ert´ekre. Elk´epzelhet˝o azonban az is, hogy egy jelz´es olvashatatlan ´allapotba ker¨ ul. A logaritmusos p´eld´an´al maradva: ha egy koal´ıci´o felfedezi, hogy egy adott logaritmus´ert´ekben egy jelz´es van elrejtve, akkor megteheti, hogy a hamis´ıtott t´abl´azatokban egyszer˝ uen kihagyja az adott sort. K´enytelenek ˜ = Σ ∪ {?}. vagyunk teh´at Σ-t kieg´esz´ıteni a ? olvashatatlan jellel: Σ Egy elfogott kal´ozm´asolatb´ol minket csup´an a jelz´esek ´ert´ekei ´erdekelnek. Ha ezeket egym´as mell´e ´ırjuk, akkor egy a koal´ıci´o ´altal gener´ alt ujjlenyomatot nyer¨ unk. A c´elunk az, hogy a gener´alt ujjlenyomat alapj´an legal´abb egy ´arul´ot le tudjunk buktatni. 3.3. Defin´ıci´ o. Egy l hossz´ u w = w1 w2 . . . wl sz´ o, ´es egy I = {i1 , i2 , . . . , ir } indexo. (Itt r ≤ l halmaz eset´en a w sz´o I-re val´o megszor´ıt´asa a w|I = wi1 wi2 . . . wir sz´ pozit´ıv eg´esz, ´es 1 ≤ i1 < i2 < . . . < ir ≤ l.) 3.4. Defin´ıci´ o. Legyen Γ egy (l, n)-k´ od, C pedig egy koal´ıci´ o, tov´ abb´ a R a koal´ıci´ o sz´ am´ ara l´athatatlan poz´ıci´ok halmaza! A koal´ıci´ o ´ altal gener´ alhat´ o ujjlenyomatok halmaza a k¨ovetkez˝o: ˜ l : w|R = w(u) |R } h ΓC i = {w ∈ Σ a koal´ıci´o valamely u felhaszn´al´oj´ ara. K¨onnyen meggondolhat´o, hogy a fenti defin´ıci´o j´o. Indifferens ugyanis, hogy h ΓC i-t melyik u ´arul´o k´odszava szerint k´epezz¨ uk: a defin´ıci´oban csak azok a (l´athatatlan) poz´ıci´ok szerepelnek, amelyeken az ¨osszes ´arul´o k´odszava megegyezik. ´Igy h ΓC i ´eppen azokb´ol a szavakb´ol ´all, amelyek a l´athatatlan poz´ıci´okon egybees˜ nek a koal´ıci´oval, a l´athat´o helyeken pedig valamilyen Σ-beli ´ert´eket vesznek fel. Term´eszetesen a koal´ıci´o ´altal gener´alhat´o ujjlenyomatok nem felt´etlen¨ ul lesznek val´oban k´odszavak, azaz Γ-nak elemei. A k¨ovetkez˝o p´elda azt mutatja, hogy az A ´es B milyen ujjlenyomatok gener´alhat.

15

A ujjlenyomata : B ujjlenyomata : h AB i =

3 2 1 2 ˜ Σ·2·

3 1 2 2 1 2 ˜ Σ·1·2

Mindezek ut´an m´ar meg tudjuk fogalmazni prec´ızen a jel¨ol´esi felt´etelt: egy C koal´ıci´o csak olyan objektumot tud l´etrehozni, amelybe h ΓC i-beli ujjlenyomat van be´agyazva.

3.4.

Igazs´ agos k´ odok

Naiv m´asol´asr´ol besz´el¨ unk akkor, ha egy felhaszn´al´o minden v´altoztat´as n´elk¨ ul adja tov´abb a saj´at p´eld´any´ar´ol k´esz¨ ult m´asolatot. Ha felbukkan egy illeg´alis m´asolat az u felhaszn´al´o ujjlenyomat´aval, akkor j´o lenne biztosan tudni, hogy u b˝ un¨os. Azonban u mondhatja azt, hogy egy gonosz koal´ıci´o ´aldozat´aul esett, mert ´epp az ˝o k´odszav´at ´agyazt´ak a hamis m´asolatokba. A l´etrehozand´o k´odnak teh´at egy tov´abbi tulajdons´aggal is rendelkeznie kell: egy koal´ıci´o sem lehet k´epes hamisan megv´adolni ´ egy koal´ıci´on k´ıv¨ uli felhaszn´al´ot. Altal´ aban egy enyh´ebb felt´etelt szok´as haszn´alni, amely k felhaszn´al´ora korl´atozza a koal´ıci´o m´eret´et. Ennek a k´ıv´analomnak megfelel˝o k´odokat k-igazs´agos k´odoknak nevezz¨ uk. A kiss´e furcsa elnevez´es arra utal, hogy egy hamis´ıt´asi u ¨gyben (ahol legfeljebb k ´arul´o j´atszik ¨ossze) kiz´arhat´o az, hogy valakit hamisan v´adolunk meg. Ha az ujjlenyomatokhoz haszn´alt k´od rejtve marad a felhaszn´al´ok el˝ol, akkor nagyon egyszer˝ u ilyen k´odot k´esz´ıteni: az n felhaszn´al´o v´eletlenszer˝ u v´alaszt´assal kapja meg a k´odszav´at. ´Igy (c´elzottan) egy koal´ıci´o sem tud megv´adolni senkit (aki nem tagja a sz¨ovets´egnek), hiszen nem ismert az ,,´aldozat” ujjlenyomata. Mi olyan igazs´agos k´odot szeretn´enk l´etrehozni, amely akkor is m˝ uk¨odik, ha a Γ k´odk¨onyv nyilv´anos. 3.5. Defin´ıci´ o. Egy Γ k´odra azt mondjuk, hogy k-igazs´agos, ha b´ armely legfeljebb k tag´ u C koal´ıci´ora h ΓC i ∩ Γ = ΓC . A fenti defin´ıci´o szerint egy k´od pontosan akkor k-igazs´agos, ha egy legfeljebb k tag´ u koal´ıci´o ´altal gener´alhat´o ujjlenyomatok k¨oz¨ ul ´eppen a tagok ujjlenyomatai lesznek val´oban k´odszavak. Ez garant´alja azt, hogy senki sem v´adolhat´o meg hamisan, hiszen a jel¨ol´esi felt´etel miatt C k´enytelen h ΓC i-beli ujjlenyomatot be´agyazni a hamis´ıtott dokumentumba. ´Igy a be´agyazott ujjlenyomat vagy valamelyik ´arul´o´e, vagy nem tartozik egyik legitim felhaszn´al´ohoz sem.

16

k-igazs´ agos k´ odok konstrukci´ oja Ett˝ol a pontt´ol kiz´ar´olag bin´aris k´odok vizsg´alat´ara szor´ıtkozunk. El˝osz¨or defini´alunk egy nagyon rossz (azaz: hossz´ u) k´odot, amely teljesen igazs´agos. Majd ennek a k´odnak a seg´ıts´eg´evel k´esz´ıt¨ unk egy kev´esb´e igazs´agos, de j´ol haszn´alhat´o k´odot. A bin´aris (Σ = {0, 1}) ´ab´ec´e feletti n-igazs´agos k´od legyen az az (n, n)-k´od, amely a pontosan egy 1-est tartalmaz´o n hossz´ u bin´aris szavakb´ol ´all. E k´odot jel¨olj¨ uk Φ(n)-nel. P´eld´aul Φ(3) = {100, 010, 001}. Kimondhatjuk a k¨ovetkez˝o nyilv´anval´o ´all´ıt´ast: ´ ıt´ 3.6. All´ as. A Φ(n) k´od n-igazs´ agos. ´ ıt´ 3.7. All´ as. Ha n ≥ 3, akkor egy n-igazs´ agos k´ od hossza legal´ abb n. Bizony´ıt´ as. Legyen Φ egy n-igazs´agos k´od. Mivel n felhaszn´al´o van, pontosan n darab n − 1 tag´ u koal´ıci´o alak´ıthat´o: Ci legyen az a koal´ıci´o, amelynek csak ui nem tagja (1 ≤ i ≤ n). Legyen pi egy olyan poz´ıci´o, amely Ci sz´am´ara l´athatatlan, de Ci ∪ {ui } sz´am´ara m´ar l´athat´o! Ha ilyen pi nem l´etezne, akkor Ci meg tudn´a gyan´ us´ıtani ui -t, ´es ´ıgy Φ nem lehetne n-igazs´agos. Bel´atjuk, hogy a pi -k p´aronk´ent k¨ ul¨onb¨oz˝o bitpoz´ıci´okat jel¨olnek az ujjlenyomatk´odban. K¨ovetkez´esk´eppen a k´od hossza legal´abb n. Tegy¨ uk fel, hogy ps = pt (s 6= t), ´es jel¨olje p ezt a k¨oz¨os poz´ıci´ot. Legyen uk egy us -t˝ol ´es ut -t˝ol k¨ ul¨onb¨oz˝o felhaszn´al´o! Tudjuk, hogy a Cs koal´ıci´o nem l´atja a p poz´ıci´ot. Mivel ennek a koal´ıci´onak uk ´es ut tagjai, ez´ert az ujjlenyomataik (t) (k) (s) (k) megegyeznek a p helyen: wp = wp . Hasonl´oan ad´odik a wp = wp egyenl˝os´eg, amib˝ol k¨ovetkezik, hogy wp(s) = wp(t) . Tudjuk, hogy Cs sz´am´ara l´athatatlan a ps = p poz´ıci´o. Az im´ent levezett¨ uk, hogy us ´es ut ujjlenyomata ezen a helyen megegyezik. Ez azt jelenti, hogy a ps hely a Cs ∪ {us } koal´ıci´o sz´am´ara is l´athatatlan. Ez pedig ellentmond ps v´alaszt´as´anak. ´ ıt´asb´ol k¨ovetkezik, hogy a Φ(n) k´od hossza optim´alis. Ez ¨orvendetes, Az 3.7. All´ de maga a k´od ett˝ol m´eg nem lesz j´ol haszn´alhat´o: a hossza line´aris a felhaszn´al´ok sz´am´aban. Ez´ert a Φ(n) seg´ıts´eg´evel olyan r¨ovidebb k´odokat fogunk k´esz´ıteni, amelyek ¨or¨oklik Φ(n) ,,igazs´ag´erzet´et”. 3.8. Defin´ıci´ o. Legyen Ω = {v (1) , . . . , v (n) } egy r bet˝ us ´ ab´ec´e f¨ ol¨ otti (L, n)-k´ od! Azt mondjuk, hogy Ω egy (L, n, d)r -hibajav´ıt´o k´od, ha b´ armely k´et k´ odszava k¨ oz¨ ott a Hamming-t´avols´ag legal´abb d. (K´et sz´ o Hamming-t´ avols´ aga azoknak a poz´ıci´ oknak a sz´ ama, ahol a k´et sz´o elt´er.) 17

A k¨ovetkez˝okben defini´aljuk egy hibajav´ıt´o k´od, ´es egy (l, r) k´od kompoz´ıci´oj´at. Legyen Γ = {w(1) , . . . , w(r) } egy (l, r)-k´od ´es Ω egy (L, n, d)r -hibajav´ıt´o k´od! L´athat´o, hogy Γ-nak ´epp annyi szava van, mint ah´ any bet˝ us az Ω k´od ´ab´ec´eje. Ez lehet˝os´eget ad arra, hogy (term´eszetes m´odon) megfeleltess¨ uk egym´asnak Γ szavait, ´es a hibajav´ıt´o k´od ´ab´ec´ej´enek bet˝ uit. Ezt a bijekci´ot alapul v´eve a k´et k´odot a k¨ovetkez˝o m´odon ´ep´ıtj¨ uk ¨ossze. Minden Ω-beli v sz´ot ,,forgassunk ´at” t¨obb Γ-beli sz´o konkaten´aci´oj´av´a u ´gy, hogy v bet˝ uit egyenk´ent helyettes´ıts¨ uk a megfelel˝o Γ-beli sz´oval! Az ´ıgy nyert (lL, n)˜ k´odot Γ-val jel¨olj¨ uk. Foglaljuk ¨ossze a konstrukci´ot: 3.9. Defin´ıci´ o. Legyen Γ egy (l, r)-k´ od, Ω egy (L, n, d)r -hibajav´ıt´ o k´ od! A k´et k´ od kompoz´ıci´oj´an a ˜ = { w(v1 ) · w(v2 ) · . . . · w(vL ) | v = v1 v2 . . . vL ∈ Ω } Γ ˜ elemeit w˜ (1) , . . . , w˜ (n) -nel jel¨ (lL, n)-k´odot ´ertj¨ uk. A Γ olj¨ uk. ˜ egy szava L darab l hossz´ L´athat´o, hogy a Γ us´ag´ u blokkb´ol ´ep¨ ul fel. Minden ˜ ol blokk egy Γ-beli sz´ot tartalmaz. Az n felhaszn´al´o a k´odszavait ebb˝ol az u ´j Γ-b´ (i) kapja majd. Az ui felhaszn´al´o k´odszava w˜ lesz.

v=

v1

    / 

w˜v =

w(v1 )

∈Ω

v2

vL



S S S S w S

   

w(v2 )

w(vL )

˜ ∈Γ

3.2. ´ abra. Kompoz´ıci´o 3.10. Lemma. Legyen Γ egy k-igazs´ agos (l, r)-k´ od, Ω pedig egy o
(L, n, d)r -hibajav´ıt´ 1 ˜ ˜ od is k´ od, ´es jel¨ole Γ a kett˝oj¨ uk kompoz´ıci´ oj´ at! Ha d > L 1 − k , akkor az Γ k´ k-igazs´ agos. ´ ıt´asunk igaBizony´ıt´ as. Legyen C egy legfeljebb k tagot sz´aml´al´o koal´ıci´o! All´ zol´as´ahoz be kell l´atni, hogy D E ˜ ˜=Γ ˜C . ΓC ∩ Γ 18

Gondot csak a ⊆ ir´any jelent, a ⊇ tartalmaz´as nyilv´anval´o, hiszen az ´arul´ok tudj´ak gener´alni a saj´at k´odszavaikat. ˜ Jel¨olje w˜ (1) , . . . , w˜ (k) az ´arul´ok Γ-beli k´odszavait. Legyen v (i) ∈ Ω az a sz´o, (i) amelyb˝ol a kompoz´ıci´o sor´an a w˜ sz´ot nyert¨ uk (1 ≤ i ≤ k). Indirekt m´odon tegy¨ uk fel, hogy a C koal´ıci´o tud gener´alni egy olyan w˜ k´odsz´ot, amely egy koal´ıci´on k´ıv¨ uli u felhaszn´al´ohoz tartozik. Jel¨olje v ∈ Ω azt a sz´ot, amelyb˝ol w-t ˜ nyert¨ uk: v = v1 v2 . . . vL (v1 ) (v2 ) w . . . w(vL ) w˜ = w B´armely i = 1, . . . , k eset´en v ´es v (i) legal´abb L (1 − 1/k) helyen elt´er, mert az Ω-beli Hamming-t´avols´ag nagyobb, mint L (1 − 1/k). Ebb˝ol k¨ovetkezik, hogy v ´es v (i) kevesebb, mint L/k poz´ıci´oban egyezik meg. ´Igy kell lennie egy 1 ≤ p ≤ L poz´ıci´onak, ahol v k¨ ul¨onb¨ozik az ¨osszes v (i) -t˝ol: vp 6= vpi

(i = 1, . . . , k) .

Ebb˝ol r¨ogt¨on ad´odik az, hogy a w˜ sz´o p. blokkja sem azonos egyik w˜ (i) sz´o p. blokkj´aval sem. Az persze el˝ofordulhat, hogy a w˜ (i) szavak p. blokkja k¨oz¨ ul n´eh´any megegyezik, de ez nem okoz probl´em´at. Tudjuk, hogy ezek a blokkok mind Γ-beliek. Mivel Γ k-igazs´agos, ez´ert az ´arul´ok a p. blokk alapj´an nem tudj´ak gener´alni w˜ p. blokkj´at. Ebb˝ol pedig l´athat´o, hogy mag´at w-t ˜ sem tudj´ak el˝o´all´ıtani, ami pedig ellentmond´as.

Felhaszn´alunk egy [3]-b´ol sz´armaz´o lemm´at. Eszerint, ha az Ω hibajav´ıt´o k´od k´odszavait v´eletlenszer˝ uen v´alasztjuk, akkor j´o k´odot nyer¨ unk. 3.11. Lemma. Legyen n ´es r pozit´ıv eg´esz! Ekkor l´etezik olyan (L, n, d)2r -hibajav´ıt´ o k´ od, amelyben L = 8r log n, ´es a minim´ alis t´ avols´ ag d > L(1 − 1/r). 3.12. T´ etel. Legyen n ´es k pozit´ıv eg´esz! Ekkor l´etezik k-igazs´ agos (l, n)-k´ od, ahol l = 16k 2 log n. Bizony´ıt´ as. Haszn´aljuk fel a 3.11. Lemm´at r = k helyettes´ıt´essel! Ad´odik, hogy l´etezik egy Ω (L, n, d)2k -hibajav´ıt´o k´od, ahol L = 8k log n, ´es d > L(1−1/k). Legyen ˜ k´od ezen Ω ´es a Φ(2k) k´od kompoz´ıci´oja! aΓ ˜ egy k-igazs´agos k´od n felhaszn´al´ohoz, ´es a k´odszavak A 3.10. Lemma miatt a Γ 2 hossza 2kL = 16k log n.

A konstrukci´o explicitt´e t´etel´ehez egy konkr´et hibajav´ıt´o k´odot kell alkalmaznunk. Ilyen k´odok konstrukci´oja megtal´alhat´o [1]-ben. A 3.11. Lemm´aban tal´alhat´o korl´at ily m´odon nem ´erhet˝o el, explicit k´odokkal csup´an l = k 2 log2 n hossz´ us´ag´ u k´odok nyerhet˝ok. 19

3.5.

Kij´ atszhatatlan k´ odok

Az el˝oz˝o r´eszben megmutattuk, hogyan lehet igazs´agos k´odokat konstru´alni. Ha az ujjlenyomatok egy ilyen igazs´agos k´odb´ol ker¨ ulnek ki, akkor az ´arul´ok nem tudj´ak ´artatlan felhaszn´al´ok ujjlenyomatait belehamis´ıtani a kal´oz k´opi´akba. Ez azonban kev´es a rendszer m˝ uk¨od´es´ehez: meg kell val´os´ıtani az ´arul´ok ut´ani nyomoz´ast. Tegy¨ uk fel, hogy lefoglalunk egy illeg´alis p´eld´anyt, amelyben az x ujjlenyomatot tal´aljuk. Maga x nagy val´osz´ın˝ us´eggel nem lesz val´odi k´odsz´o: az ´arul´ok valamilyen strat´egia szerint megv´altoztatt´ak/olvashatatlann´a tett´ek a saj´at ujjlenyomataik l´athat´o bitjeit, ´es ´ıgy nyert´ek x-et. A mi feladatunk az, hogy meghat´arozzunk legal´abb egy ´arul´ot, aki biztosan ludas x gener´al´as´aban. Tulajdonk´eppen egy A nyomoz´o algoritmusra van sz¨ uks´eg, amely az x sz´o alapj´an megadja a kal´ozcsapat (legal´abb) egy tagj´at. A-t tekinthetj¨ uk egy A : {0, 1, ?}l → {1, . . . , n} f¨ uggv´enynek, 13 ahol n a felhaszn´al´ok sz´am´at jel¨oli. (K´es˝obb l´atunk majd olyan nyomoz´o algoritmus, amely nem egy, hanem t¨obb felhaszn´al´ot is meggyan´ us´ıthat.) 3.13. Defin´ıci´ o. Azt mondjuk, hogy a Γ (l, n)-k´ od tot´alisan k-biztos, ha van olyan l A : {0, 1, ?} → {1, . . . , n} nyomoz´ o algoritmus, amelyre teljes¨ ul a k¨ ovetkez˝ o felt´etel: minden legfeljebb k tag´ u C koal´ıci´ o´ altal gener´ alt x sz´ ora A(x) ∈ C. Vegy¨ uk ´eszre, hogy az ilyen Γ k´odok sz¨ uks´egk´eppen k-igazs´agosak is. Mi t¨ort´enne akkor, ha az U = {u1 , . . . , un } halmaznak lenne k´et diszjunkt r´eszhalmaza (k´et potenci´alis koal´ıci´o), amelyek gener´alni tudj´ak ugyanazon x sz´ot? Ha ezt az x-et olvasn´ank ki egy kal´oz k´opi´ab´ol, akkor bajban lenne a nyomoz´o algoritmus: elm´eletileg meg´allap´ıthatatlan, hogy a k´et felhaszn´al´oi csoport k¨oz¨ ul val´ oj´ aban melyik dobta piacra a hamis´ıtv´anyokat. Nyert¨ unk teh´at egy sz¨ uks´eges felt´etelt, amelynek minden tot´alisan k-biztos k´od meg kell, hogy feleljen. 3.14. Lemma. Ha Γ egy tot´alisan k-biztos k´ od, akkor a C1 , . . . , Cm legfeljebb k tag´ u koal´ıci´ okra a k¨ovetkez˝o ´all´ıt´as igaz: C1 ∩ . . . ∩ Cm = ∅

h ΓC1 i ∩ . . . ∩ h ΓCm i = ∅

=⇒

A tot´alisan biztos k´odok l´atsz´olag kit˝ un˝o eszk¨oz¨ok az ´arul´ok ut´ani nyomoz´asban. Az el˝oz˝o lemma seg´ıts´eg´evel sajnos kimutathat´o egy ´ori´asi hi´anyoss´aguk: nem l´eteznek. 3.15. T´ etel. Ha n ≥ 3 ´es k ≥ 2, akkor nem l´etezik tot´ alisan k-biztos k´ od. Bizony´ıt´ as. Minden tot´alisan k-biztos k´od egyben tot´alisan (k − 1)-biztos is. ´Igy el´eg bel´atni azt, hogy nem l´etezik tot´alisan 2-biztos k´od. Legyen Γ egy (l, n)-k´od! 13

Ezek a nyomoz´ o f¨ uggv´enyek polinom id˝oben kisz´am´ıthat´ok lesznek. A f¨ uggv´eny-jel¨ol´est csak az egyszer˝ ubb t´ argyal´ as kedv´e´ert vezett¨ uk be.

20

Mutatunk h´arom olyan k´ettag´ u koal´ıci´ot, amelyek mind tudj´ak gener´alni ugyanazt a sz´ot. Legyen u1 , u2 , u3 h´arom k¨ ul¨onb¨oz˝o felhaszn´al´o a w(1) , w(2) , w(3) k´odszavakkal, ´es a h´arom koal´ıci´o a k¨ovetkez˝o: C1 = {u2 , u3 },

C2 = {u1 , u3 },

C3 = {u1 , u2 } .

Az x ∈ {0, 1}l sz´o egy poz´ıci´oj´ara azt a bet˝ ut ´ırjuk, amelyik a legt¨obbsz¨or fordul el˝o a w(1) , w(2) , w(3) szavak adott hely´en. Ha ilyen nincs (vagyis a h´arom k´odsz´o az adott helyen p´aronk´ent k¨ ul¨onb¨oz˝o ´ert´ek˝ u), akkor ?-et ´ırjunk x-be. K¨onnyen ellen˝orizhet˝o, hogy x ∈ h ΓC1 i ∩ h ΓC1 i ∩ h ΓC3 i, ´es az is l´athat´o, hogy C1 ∩ C2 ∩ C3 = ∅. Ha Γ k´od tot´alisan 2-biztos lenne, akkor ellentmond´asba keveredn´enk a 3.14. Lemm´aval. Ez sajnos egy el´eg komoly negat´ıv eredm´eny: lehetetlen olyan ujjlenyomat-k´odot alkotni, amellyel 100%-os biztons´aggal elfoghat´ok az ´arul´ok. K´enytelenek vagyunk al´abb adni, ´es megel´egedni olyan s´em´akkal, amelyekben a nyomoz´as valamilyen el˝ore r¨ogz´ıtett  es´ellyel hib´azhat. Az eddig t´argyalt modellben nem szerepelt v´eletlen: egy el˝ore ler¨ogz´ıtett k´odb´ol adott sorrend szerint osztottuk ki az ujjlenyomatokat. Az u ´j modellben az adatszolg´altat´o haszn´alhat egy r v´eletlen bitsorozatot is. A m´odszer kulcsa az, hogy r titokban marad. Ezeket a gondolatokat fogalmazzuk meg a k¨ovetkez˝o defin´ıci´oban. 3.16. Defin´ıci´ o. A Γ : {1, . . . , n} × {0, 1}∗ → Σl lek´epez´est (l, n)-ujjlenyomat s´em´ anak nevezz¨ uk. Γ egy felhaszn´ al´ ohoz ´es egy r ∈ {0, 1}∗ v´eletlen bitsorozathoz rendel egy l hossz´ u ujjlenyomatot (k´ odsz´ ot). Azt a s´em´ at, amelyben az adatszolg´ altat´ o az r v´eletlent haszn´alja, Γr -rel jel¨ olj¨ uk. Az A nyomoz´o algoritmus (hasonl´oan a fentiekhez) egy elfogott x ujjlenyomat alapj´an ´allap´ıtja meg az ´arul´ok szem´ely´et – nagy val´osz´ın˝ us´eggel helyesen. 3.17. Defin´ıci´ o. Azt mondjuk, hogy a Γr ujjlenyomat s´ema (, k)-biztos, ha van olyan A nyomoz´o algoritmus, amelyre teljes¨ ul a k¨ ovetkez˝ o felt´etel: egy legfeljebb k tag´ u C koal´ıci´o ´altal gener´alt x ujjlenyomatra teljes¨ ul, hogy Prob[ A(x) ∈ C ] > 1 − , ahol a val´osz´ın˝ us´eg az r bitjeit˝ol ´es a koal´ıci´ o ´ altal haszn´ alt v´eletlen v´ alaszt´ asokt´ ol f¨ ugg.

21

Kij´ atszhatatlan k´ odok konstrukci´ oja A k¨ovetkez˝okben bemutatott gondolatmenet nagyon hasonl´o lesz ahhoz, amit az igazs´agos k´odok konstrukci´oj´an´al l´attunk. El˝osz¨or l´etrehozunk egy tetsz˝oleges pozit´ıv -nal m˝ uk¨od˝o (, n)-biztos k´odot. Ez a k´od meglehet˝osen hossz´ u: a k´odszavak O(1) n bitb˝ol ´allnak. Ezen jav´ıtand´o, ¨ossze´ep´ıtj¨ uk egy m´asik k´oddal, ´es ´ıgy nyer¨ unk O(1) egy (, k)-biztos k´odot, amelynek a hossza k log n. Az n-biztos k´odunk a k¨ovetkez˝o: legyen a cm az az n magass´ag´ u 0 − 1 vek´ tor, amelynek pontosan az els˝o m bitje 1, a t¨obbi 0. Irjuk fel egym´as mell´e a c1 , c2 , . . . , cn−1 vektorokat, mindegyiket d-szer!14 Az ´ıgy kapott k´odot nevezz¨ uk el Φ(n, d)-nek. Al´abb l´athat´o a Φ(4, 3) k´od, ahol a n´egy felhaszn´al´o A, B, C, D, ujjlenyomataik pedig a t´abl´azat n´egy sora.

A B C D

: : : :

111111111 000111111 000000111 000000000

´ Err˝ol a Φ(n, d) k´odr´ol fogjuk bel´atni, hogy (, n)-biztos. Erezhet˝ o, hogy a nyomoz´o algoritmus  hibaval´osz´ın˝ us´ege d ´ert´ek´et˝ol f¨ ugg majd. Van egy fontos mozzanat, amely drasztikusan megnehez´ıti az ´arul´ok dolg´at. A szolg´altat´o, miel˝ott be´agyazn´a az ujjlenyomatokat a term´ekbe, megkeveri azokat. Ez a kever´es a k¨ovetkez˝ot jelenti: a szolg´altat´o v´alaszt egy v´eletlen π ∈ Sym(l) permut´aci´ot, ´es az ui felhaszn´al´o p´eld´any´aba a w(i) k´odsz´o helyett a πw(i) -t helyezi el. Fontos, hogy minden felhaszn´al´o eset´eben ugyanazon π permut´aci´o ker¨ ul alkalmaz´asra. Az elj´ar´as l´enyege, hogy π rejtve marad a felhaszn´al´ok el˝ol. Tulajdonk´eppen ez a permut´aci´o felel meg az ujjlenyomat s´ema defin´ıci´oj´aban szerepl˝o r v´eletlennek. Ezzel a m´odszerrel el´erhet˝o az, hogy a felhaszn´al´oknak semmi inform´aci´ojuk ne legyen arr´ol, hogy az objektum egy jelz´ese a k´od melyik bitj´enek felel meg. ´Igy ha egy koal´ıci´o l´at is n´eh´any bitet, k´eptelen meg´allap´ıtani a k¨oz¨ott¨ uk l´ev˝o helyes sorrendet. A c´elunk az, hogy a Φ(n, d) k´odhoz mutassunk egy olyan  hib´aj´ u A nyomoz´o algoritmust, amely egy tetsz˝oleges C koal´ıci´o ´altal gener´alt x ujjlenyomat alapj´an lebuktat legal´abb egy ´arul´ot. Prob[ A(x) ∈ C ] > 1 −  . 14

Ez a d teljesen f¨ uggetlen a kor´ abban l´atott hibajav´ıt´o k´odok minim´alis t´avols´ag´at´ol.

22

Ha azt mondjuk, hogy az x sz´ot a C koal´ıci´o gener´alta, akkor x-re u ´gy kell gondolni, mintha a bitjeit m´ar ,,visszakevert¨ uk” volna π −1 -gyel. Vagyis a kal´ozok val´oj´aban nem az x sz´ot gener´alt´ak, hanem a πx-et. Bevezet¨ unk n´eh´any u ´j jel¨ol´est: 1. Bm legyen azon poz´ıci´ok (oszlopindexek) halmaza, ahol cm t´ıpus´ u oszlop ´all. 2. Minden 2 ≤ i ≤ n − 1-re legyen Ri = Bi−1 ∪ Bi . 3. Jel¨olj¨ uk s-sel a s´ ulyf¨ uggv´enyt: y ∈ {0, 1}∗ eset´en s(y) =

P

yi .

B2 B3 z }| { z }| { 1: 2: 3: 4: 5: 6:

1111 0000 0000 0000 0000 0000

1111 1111 1111 1111 0000 1111 0000 0000 0000 0000 0000 0000 | {z }

1111 1111 1111 1111 0000 0000

1111 1111 1111 1111 1111 0000

R3 3.3. ´ abra. Az Ri ´es Bi jelent´ese

L´athat´o, hogy Bm ´eppen d elem˝ u, m´ıg Ri m´erete 2d. Az Ri halmaz intuit´ıv jelent´ese a k¨ovetkez˝o: ´eppen azon poz´ıci´ok vannak Ri -ben, amelyek k¨oz¨ott kiz´ ar´ olag ui tud k¨ ul¨onbs´eget tenni. Rajta k´ıv¨ ul ezeken a helyeken mindenki vagy csak 0-t, vagy csak 1-t l´at. Ezt a t´enyt fogjuk felhaszn´alni arra, hogy adott esetben bizony´ıtsuk ui b˝ un¨oss´eg´et. Miel˝ott megadn´ank az algoritmust, megpr´ob´alunk intuit´ıv k´epet adni arr´ol, hogy m´ert fog m˝ uk¨odni. Tegy¨ uk fel, hogy egy C koal´ıci´o gener´al egy x sz´ot. A π permut´aci´onak k¨osz¨onhet˝oen az ´arul´ok nem tudj´ak, hogy egy felfedezett jelz´es az eredeti k´odsz´o melyik bitj´et reprezent´alja. Csup´an a jelz´es ´ert´ek´et ismerik. Ha egy ui felhaszn´al´o nem tagja a koal´ıci´onak, akkor (az el˝oz˝o bekezd´es szerint) a tagok ujjlenyomatait vizsg´alva lehetetlen k¨ ul¨onbs´eget tenni az Ri oszlopok k¨oz¨ott. Ak´armilyen strat´egia szerint ´all´ıtj´ak is be az ´arul´ok az x|Ri biteket, az abban tal´alhat´o 1-esek durv´an egyenl˝oen fognak eloszlani x|Bi−1 ´es x|Bi k¨oz¨ott. Ez annak k¨osz¨onhet˝o, hogy amikor az ´arul´ok x|Ri egy bitj´et 1-re ´all´ıtj´ak, fogalmuk sincs arr´ol, hogy ez a bit Bi−1 -hez vagy Bi -hez tartozik-e. (Ez tal´an onnan l´athat´o a legink´abb, 23

hogy az ´arul´ok ´altal a val´os´agban gener´alt ujjlenyomatot mi ut´olag megkeverj¨ uk egy v´eletlen π −1 permut´aci´oval.) Ha egy megtal´alt x ujjlenyomaton azt l´atjuk, hogy az x|Ri 1-esei nem egyenl˝oen vannak sz´etosztva x|Bi−1 ´es x|Bi k¨oz¨ott, akkor val´osz´ın˝ us´ıthetj¨ uk, hogy i ludas a csal´asban. A hib´az´as val´osz´ın˝ us´ege d ´ert´ek´enek (teh´at x|Ri hossz´anak) n¨ovel´es´evel cs¨okkenthet˝o. 1. Algoritmus. Input: x ∈ {0, 1, ?}l Output: T ⊆ {0, 1, . . . , n} x-ben minden ? ´ at´ ır´ asa 0-ra. Ha s(x|B1 ) > 0, akkor ki: "Az 1. felhaszn´ al´ o ´ arul´ o". Ha s(x|Bn−1 ) < d, akkor ki: "Az n. felhaszn´ al´ o ´ arul´ o". Ciklus i=2-t¨ ol n-1-ig b:= s(x|Ri ) r 2n b b log , akkor ki: 6. Ha s(x|Bi−1 ) < − 2 2  1. 2. 3. 4. 5.

"Az i. felhaszn´ al´ o ´ arul´ o". 7. Ciklus v´ ege. Megjegyezz¨ uk, hogy az algoritmus nem egyetlen felhaszn´al´ot fog meggyan´ us´ıtani, hanem a felhaszn´al´ok egy T csoportj´at. Ezzel tulajdonk´eppen a 3.17. Defin´ıci´ot ´altal´anos´ıtottuk. Amiatt, hogy elt´ert¨ unk a nyomoz´o algoritmus eredeti defin´ıci´oj´at´ol, az algoritmus helyess´eg´enek igazol´as´ahoz k´et dolgot is kell bel´atnunk. Egyr´eszt azt, hogy T legfeljebb 1 −  es´ellyel tartalmaz ´artatlan felhaszn´al´ot, m´asr´eszt azt, hogy T nem¨ ures. Ennek megfelel˝oen az (, n)-biztoss´ag (´atmenetileg) u ´gy ´ertend˝o, hogy a nyomoz´o algoritmus kimenetk´ent U -nak egy nem¨ ures r´eszhalmaz´at adja, nem pedig egyetlen felhaszn´al´ot. A Φ(n, d) k´od (, n)-biztoss´ag´anak igazol´as´at eszerint fogjuk k´et r´eszre bontani. El˝osz¨or bel´atjuk, hogy nagy val´osz´ın˝ us´eggel nem hib´azik az algoritmus, ezut´an bizony´ıtjuk azt, hogy az algoritmus mindenk´eppen meggyan´ us´ıt valakit. 3.18. Lemma. Ha  > 0 ´es d = 2 n2 log(2n/), akkor a Φ(n, d) k´ odot haszn´ alva b´ armely C koal´ıci´o ´altal gener´alt x ujjlenyomatra teljes¨ ulj, hogy Prob[ A(x) ⊆ C ] > 1 −  .

24

Bizony´ıt´ as. Vezess¨ uk be a T = A(x) jel¨ol´est! Alulr´ol szeretn´enk megbecs¨ ulni d-t, hogy a Φ(n, d) k´odra ´erv´enyes legyen az ´all´ıt´as. Az algoritmus a k¨ovetkez˝o ¨otletre ´ep¨ ul. Az els˝o d poz´ıci´oban az els˝o felhaszn´al´ot lesz´am´ıtva mindenki csupa 0-t l´at. Ha az elfogott ujjlenyomat els˝o d hely´en ak´ar csak egyetlen 1-es is el˝ofordul, akkor biztosak lehet¨ unk az els˝o felhaszn´al´o v´etkess´eg´eben. Hasonl´oan buktathat´o le az utols´o felhaszn´al´o, ha az utols´o d bit nem csupa 1. A k¨oztes j´at´ekosokat m´as krit´eriumok alapj´an gyan´ us´ıtjuk meg. Ha az els˝o blokk csupa 0, az utols´o pedig csupa 1, akkor blokkr´ol blokkra haladva (balr´ol jobbra) ´atlagosan d/(n − 2)-vel n˝o az 1-esek sz´ama. Ha egy ponton legal´abb ekkora ugr´ast tapasztalunk, akkor az adott felhaszn´al´ot meggyan´ us´ıtjuk. (Vegy¨ uk ´eszre, hogy az sem okoz gondot, ha az els˝o vagy az utols´o felhaszn´al´o b˝ un¨os, hiszen ekkor az ´atlagos n¨oveked´es kisebb lesz, mint d/(n − 2).) Az nyomoz´asi elv m¨og¨ott az a t´eny ´all, hogy az (i−1)-dik ´es az i-dik blokk k¨oz¨ott kiz´ar´olag az i-dik j´at´ekos tud k¨ ul¨onbs´eget tenni. ´Igy ha ˝o nem ´arul´o, akkor a koal´ıci´o teljesen v´eletlenszer˝ uen helyezi el az 1-eseket a k´et blokkban. Ennek k¨osz¨onhet˝oen nagy val´osz´ın˝ us´eggel nagyj´ab´ol azonos sz´am´ u 1-es ker¨ ul az (i − 1)-dik ´es az i-dik blokkba. Ha azt l´atjuk, hogy az i-dik blokkban j´oval t¨obb 1-es van, mint az azt megel˝oz˝oben (vagyis az ´atlagosn´al nagyobb a n¨oveked´es), akkor felt´etelezhetj¨ uk, hogy ui b˝ un¨os. A k¨ovetkez˝okben prec´ızebb´e tessz¨ uk a fent megfogalmazottakat. Tegy¨ uk fel, hogy valamilyen k¨ozb¨ uls˝o 2 ≤ i ≤ n − 1-re ui ∈ T . Elegend˝o azt bel´atni, hogy egy tetsz˝oleges ui felhaszn´al´o eset´en az algoritmus legfeljebb /n es´ellyel t´eved: Prob[ ui ∈ / C]≤

 , n

ugyanis ebb˝ol m´ar k¨ovetkezik, hogy Prob[ van olyan felhaszn´al´o, akit ´artatlanul v´adoltunk ] = Prob[ T 6⊆ C ] ≤  vagyis Prob[ nincs olyan felhaszn´al´o, akit ´artatlanul v´adoltunk ] = Prob[ T ⊆ C ] ≥ 1 −  . Tegy¨ uk fel, hogy a meggyan´ us´ıtott ui ´artatlan. Mivel π-t egyenletes eloszl´as szerint v´alasztottuk Sym(l)-b˝ol, az x|Ri -beli egyeseket tekinthetj¨ uk u ´gy, mintha v´eletlenszer˝ uen lenn´enek elhelyezve. (Az 1-esek sz´ ama az ´arul´ok strat´egi´aj´at´ol f¨ ugg, de a helye nem.) Jel¨olje b = s(x|Ri ) az egyesek sz´am´at x|Ri -ben. Legyen ξ az a val´osz´ın˝ us´egi v´altoz´o, amely megsz´amolja az x|Bi−1 -beli egyeseket, felt´eve hogy x|Ri -ben ¨osszesen b darab 1-es van. B´armely max(0, b − d) ≤ r ≤ min(b, d) eg´esz sz´amra

25

d

d



-



-

01100111001011110101001 10010110101001011010100 | {z } r darab 1-es |

{z

}

b darab 1-es 3.4. ´ abra. Az 1-esek egy lehets´eges eloszl´asa x|Ri -ben

   d d r b−r   . Prob[ ξ = r ] = 2d b ξ egy olyan hipergeometrikus eloszl´as´ u val´osz´ın˝ us´egi v´altoz´o, amelynek a v´arhat´o ´ert´eke E(ξ) = b/2 . (Ez azt jelenti, hogy az x|Ri -beli 1-eseknek v´arhat´oan a fele esik x|Bi−1 -be.) A bevezet˝o okoskod´as alapj´an akkor gyan´ us´ıtjuk meg ui -t, ha

≥

d n−2

(b − ξ) − ξ ≥

d n−2

s (x|Bi ) − s x|Bi−1




ξ ≤

d b − . 2 2(n − 2)

(∗)

Vagyis a k¨ovetkez˝o val´osz´ın˝ us´eget kell fel¨ ulr˝ol becs¨ uln¨ unk:   b d Prob[ ui b˝ un¨osnek lett kiki´altva ] = Prob ξ < − . 2 2(n − 2) Ehhez vegy¨ unk egy η binomi´alis eloszl´as´ u val´osz´ın˝ us´egi v´altoz´ot, amely megadja, hogy b darab 1-esb˝ol h´any ker¨ ul az (i − 1)-dik blokkba, ha minden 1-es 1/2 val´osz´ın˝ us´eggel ker¨ ul az (i − 1)-dik vagy az i-dik blokkba. A becsl´eshez sz¨ uks´eg van a k¨ovetkez˝o ´all´ıt´asra:

26

´ ıt´ 3.19. All´ as. Ha b ≤ d, akkor minden 0 ≤ r ≤ b eg´esz sz´ amra Prob[ ξ = r ] ≤ 2 Prob[ η = r ] . Bizony´ıt´ as. Az ´all´ıt´as a k¨ovetkez˝ot jelenti:    d d   b 1 r b−r   ≤ 2 2d r 2b b (d − r)! (d − b + r)! 2 (2d)! · ≥1 · b 2 (2d − b)! d! d!

2 (2d) (2d − 1) (2d − 2) . . . (2d − b + 1) ≥ 1. (2d) (2d − 2) . . . (2d − 2r + 2) (2d) (2d − 2) . . . (2d − 2b + 2r + 2) Ennek az egyenl˝otlens´egnek a baloldala pedig ´atalak´ıthat´o egy olyan szorzatt´a, amelyben minden t´enyez˝o legal´abb 1: 2 (2d − b + 1) 2d 2d − 1 2d − 2 · · · ... 2d 2d 2d − 2 2d − 2 Ki kell emeln¨ unk, hogy az el˝oz˝o ´all´ıt´as csak akkor igaz, ha b ≤ d. Ez azonban a szimmetria miatt nem jelent val´odi megszor´ıt´ast. Ha ugyanis az egyesek sz´ama b > d, akkor ugyanez a levezet´es elv´egezhet˝o u ´gy, hogy az 1-esek helyett a 0-kal sz´amolunk, mert l´athat´o, hogy Prob[ b darab egyesb˝ol ´eppen r ker¨ ul az (i − 1)-dik blokkba ] = = Prob[ 2d − b darab null´ab´ol ´eppen d − r ker¨ ul az (i − 1)-dik blokkba ] . ´ ıt´ast, a m´asodik l´ep´eshez pedig a A becsl´es els˝o l´ep´es´ehez felhaszn´alhatjuk a 3.19. All´ Chernoff-korl´at els˝o v´altozat´at (2.2. T´etel), ´ıgy azt kapjuk, hogy b´armely a > 0-ra:     b b 2 Prob ξ < − a ≤ 2 Prob η < − a ≤ 2 e−2a /b . 2 2 27

Olyan a-t (azaz tulajdonk´eppen d-t) keres¨ unk, amelyre 2 e−2a

2 /b

= /n,rhiszen ´ıgy b 2n legfeljebb /n es´ellyel v´adoljuk meg az ´artatlan ui -t. Ad´odik, hogy a = log , 2  amelyet visszahelyettes´ıtve azt kapjuk, hogy "

b Prob ξ < − 2

r

2n b log 2 

# ≤ 2e− log(2n/) =

 . n

Ez az eredm´eny pontosan azt jelenti, hogy egy ´artatlan felhaszn´al´ot legfeljebb /n es´ellyel gyan´ us´ıt meg az algoritmusunk. Ebb˝ol pedig k¨ovetkezik, hogy a teljes T = A(x) halmazba legfeljebb  val´osz´ın˝ us´eggel ker¨ ul be ´artatlan szem´ely. A d ´ert´ek´et pedig a-b´ol ´es a (∗) egyenlet alapj´an kapjuk meg: d = 2 n2 log(2n/) .

3.20. Lemma. Ha a Φ(n, d) k´odot haszn´ aljuk, ´es d = 2n2 log(2n/), akkor egy x elfogott ujjlenyomatra, mint bemenetre az 1. Algoritmus kimenete nem¨ ures, azaz T 6= ∅. Bizony´ıt´ as. Tegy¨ uk fel, hogy a lemma ´all´ıt´asa hamis, ´es T = ∅! Ez azt jelenti, hogy sem az els˝o, sem az utols´o j´at´ekost nem gyan´ us´ıtottuk meg, teh´at x els˝o d bitje csupa 0, utols´o d bitje csupa 1. Mivel k¨oztes felhaszn´al´ot sem gyan´ us´ıtottunk meg, ez´ert blokkonk´ent kevesebb, mint d/(n − 2)-vel n¨ovekszik az egyesek sz´ama x-ben. Ez pedig ellentmond´as, hiszen ´ıgy n − 2 l´ep´esben nem lehet a csupa 0 blokkot csupa 1 blokkra cser´elni. Az Φ(n, d) k´od vizsg´alat´anak eredm´enyeit foglaljuk ¨ossze a k¨ovetkez˝o t´etelben. 3.21. T´ etel. Tetsz˝olegesen v´alasztott  > 0 eset´en a Φ(n, d) k´ od (, n)-biztos, ha 2 d = 2n log(2n/). A k´od n darab k´ odsz´ ot tartalmaz, amelyek hossza (n − 1) d = 3 O(n log n).

3.6.

A k´ odhossz jav´ıt´ asa

A Φ(n, d) k´od kij´atszhatatlan ugyan, de m´egsem praktikus a hossza miatt. Ebben a r´eszben bizony´ıt´as n´elk¨ ul le´ırjuk, hogy mik´epp lehet cs¨okkenteni a k´od hossz´at. V´eg¨ ul adunk egy als´o becsl´est az (, k)-biztos k´odok hossz´ara.

28

A Φ(m, d) k´od hossz´an a k-igazs´agos k´odokn´al l´atott m´odszerrel fogunk jav´ıtani: Φ(m, d)-b˝ol kompoz´ıci´oval nyer¨ unk egy r¨ovidebb (, k)-biztos k´odot. Az ¨ossze´ep´ıt´eshez egy Ω-val jel¨olt (L, n)-k´odot fogunk haszn´alni. ´ Alljon az ´ab´ec´enk m bet˝ ub˝ol, ´es gener´aljuk le az ¨osszes lehets´eges L hossz´ u sz´ot, majd egyenletes eloszl´as szerint v´eletlenszer˝ uen v´alasszunk ki k¨oz¨ ul¨ uk n darabot: ez lesz az Ω k´od. L´athat´o, hogy az Ω ´ab´ec´eje ´eppen annyi elem˝ u, mint ah´any szava Φ(m, d)-nek van. Ez a kor´abban l´atottakhoz hasonl´oan m´odot ad arra, hogy ¨ossze´ep´ıts¨ uk a k´et k´odot. Az Ω minden egyes szav´at bet˝ unk´ent forgassuk ´at egy´ ˜ egy Φ(m, d)-beli sz´oba. Igy nyer¨ unk egy Γ k´odot, amelynek minden szava ´eppen L darab Φ(m, d)-beli sz´ob´ol ´ep¨ ul fel. (Ezeket a darabokat blokkoknak nevezz¨ uk.) A ˜ k´et alapul vett k´od m´ereteib˝ol k¨ovetkezik, hogy Γ-nak n eleme van, ´es a k´odszavai l = L(m − 1)d hossz´ uak. Az ujjlenyomatok be´agyaz´asa el˝ott az adatszolg´altat´o v´alaszt L darab v´eletlen permut´aci´ot: π1 , . . . , πL ∈ Sym(l). Az ui felhaszn´al´o w˜ (i) k´odszav´anak minden egyes blokkj´at megkeveri a megfelel˝o permut´aci´oval, ´es az ´ıgy nyert sz´ot ´ep´ıti be a dokumentumba. A πi permut´aci´ok most is titokban maradnak, ´es maga az Ω k´od is rejtve marad a felhaszn´al´ok el˝ol. 3.22. T´ etel. Legyen k ≤ n pozit´ıv eg´esz,  > 0, tov´ abb´ a m = 2k, L = 2k log(2n/) 2 ´es d = 2m log(4mL/)! Ha a fent ismertetett m´ odon elk´esz´ıtj¨ uk a Φ(m, d) ´es az ˜ ˜ k´ Ω k´ od Γ-val jel¨olt kompoz´ıci´oj´at, akkor egy (, k)-biztos k´ odot nyer¨ unk. A Γ od n 4 k´ odsz´ ot tartalmaz, amelyek hossza l = O ( k log(1/) log(n/)). ˜ Az 1. Algoritmus felhaszn´al´as´aval fogunk nyomoz´o algoritmust szerkeszteni a Γ k´odhoz. Az elj´ar´as helyess´eg´enek bizony´ıt´asa megtal´alhat´o [3]-ban. Jel¨olj¨ uk x-szel az elfogott ujjlenyomatot. Bontsuk fel x-et a kor´abban eml´ıtett m´odon L darab blokkra, ´es mindegyik blokkra futtassuk le az 1. Algoritmust. A (blokkonk´enti) kimenetek k¨oz¨ ul tetsz˝olegesen v´alasszunk egyet-egyet: az i. blokk eset´en jel¨olj¨ uk ezt yi -vel. Mindegyik yi egy felhaszn´al´ot jel¨ol, ´ıgy 1 ´es n k¨oz´e esik. ´ Ertelmezz¨ uk ezeket az yi -ket u ´gy, mintha az Ω ´ab´ec´ej´enek lenn´enek bet˝ ui. ´Igy ¨ossze´all egy y = y1 y2 . . . yL sz´o. Ezut´an keress¨ unk Ω-b´ol egy olyan v sz´ot, amely a lehet˝o legt¨obb helyen egyezik y-nal. Ki´altsuk ki b˝ un¨osnek azt az u felhaszn´al´ot, akinek a k´odszava ´eppen w˜v .15

3.7.

Optim´ alis ujjlenyomat-k´ odok

Boneh ´es Shaw [3] cikk´eben a k¨ovetkez˝o als´o becsl´est adt´ak bin´aris ujjlenyomatk´odok hossz´ara: 15

˜ w ˜v azt a Γ-beli sz´ ot jel¨ oli, amelyet a v ∈ Ω sz´ob´ol vezett¨ unk le a kompoz´ıci´o sor´an.

29

3.23. T´ etel. Legyen Γ egy bin´aris (l, n)-ujjlenyomat s´ema! Ha Γ (, k)-biztos, akkor a k´ od hossza: 1 l ≥ (k − 3) log √ . k Tardos G´abornak ([19]) siker¨ ult ezt az als´o korl´atot jelent˝osen jav´ıtania, ´es bel´atnia azt, hogy a becsl´ese ´eles. A r¨ovidebb k´odok el˝o´all´ıt´as´ahoz l´enyegesen t¨obb v´eletlent kell alkalmazni, mint a fent t´argyalt Boneh-Shaw-f´ele k´odban. Eddig csup´an arra haszn´altuk a v´eletlent, hogy egy determinisztikusan el˝o´all´ıtott k´odm´atrix oszlopait megkeverj¨ uk. A Tardos-f´ele optim´alis hossz´ us´ag´ u k´od eset´en az eg´esz k´odm´atrix v´eletlenszer˝ uen van kit¨oltve. Bizony´ıt´as n´elk¨ ul k¨oz¨olj¨ uk a legjelent˝osebb eredm´enyeket: a k´odhosszra vonatkoz´o f¨ols˝o ´es als´o becsl´est. 3.24. T´ etel. L´etezik olyan bin´aris (l, n)-ujjlenyomat s´ema, amely (, k)-biztos, ´es a k´ od hossza: n l = 100 k 2 log .  3.25. T´ etel. Legyen Γ egy tetsz˝ oleges Σ ´ ab´ec´e feletti (l, n)-ujjlenyomat s´ema! Legyen tov´abb´a 3 ≤ k ≤ n eg´esz, ´es 0 <  < n/(100 k a ) valamilyen a > 1 konstanssal. Ha Γ eleget tesz az (i) ´es (ii) felt´eteleknek, akkor a k´ od hossza l ≥ da k 2 log

n , 

ahol da > 0 egy kiz´ar´olag a-t´ol f¨ ugg˝ o konstans. (i) B´armely legfeljebb k − 1 tag´ u C koal´ıci´ o ´ altal gener´ alt x ujjlenyomatra igaz, hogy Prob[ A(x) 6⊆ C ] <  , ahol A a s´em´ahoz tartoz´o nyomoz´ o algoritmust jel¨ oli. (ii) B´armely legfeljebb k tag´ u koal´ıci´ o´ altal gener´ alt x ujjlenyomatra igaz, hogy Prob[ C ∩ A(x) = ∅ ] < 0,99 . L´athat´o, hogy az als´o becsl´es´ehez az (, k)-biztoss´agn´al gyeng´ebb felt´etelek is elegend˝oek. Az (i) felt´etel azt mondja, hogy legfeljebb k − 1 m´eret˝ u koal´ıci´ok eset´en nagy val´osz´ın˝ us´eggel nem gyan´ us´ıtunk meg ´artatlan j´at´ekost. Ennek a felt´etelnek egy (, k)-biztos k´od biztosan megfelel, hiszen az legfeljebb k m´eret˝ u koal´ıci´okra is tudja ugyanezt. A (ii) felt´etel pedig azt mondja ki, hogy legal´abb 1% az es´elye annak, hogy meggyan´ us´ıtunk egy ´arul´ot. Ha egy pillanatra -t null´anak k´epzelj¨ uk, akkor ez a m´asodik felt´etel arr´ol sz´ol, hogy ak´ar 99% is lehet annak az es´elye, hogy a nyomoz´o algoritmus kimenete u ¨res. Mindebb˝ol l´athat´o, hogy az als´o becsl´eshez haszn´alt felt´etelek j´oval laz´abbak, mint az (, k)-biztoss´ag felt´etelei. 30

4.

Dinamikus alkalmaz´ asok

A most k¨ovetkez˝o r´eszben egy kicsit v´altoztatunk a modellen. Az alapprobl´ema tov´abbra is az, hogy valamilyen bizalmas adatot t¨obb felhaszn´al´ohoz szeretn´enk eljuttani u ´gy, hogy egy esetleges ´arul´as eset´en le tudjunk buktatni legal´abb egy ´arul´ot. Ebben a r´eszben azonban nem digit´alis ujjlenyomatokat alkalmazunk. A digit´alis adatot eleve titkos´ıtva tov´abb´ıtjuk a felhaszn´al´okhoz, akik rendelkeznek egy-egy kulccsal, ami lehet˝ov´e teszi sz´amukra a visszafejt´est. Dek´ odernek fogjuk nevezni azt az egys´eget, amely a desifr´ıroz´ast v´egzi, azaz (a felhaszn´al´o kulcs´aval) a titkos´ıtott u ¨zenetb˝ol l´etrehozza a ny´ılt u ¨zenetet. A mi szempontunkb´ol teljesen indifferens a dek´oder fizikai megval´os´ıt´asa: lehet hardver vagy szoftver is.

4.1.

´ Attekint´ es

Ebben a rendszerben a jogos felhaszn´al´okon k´ıv¨ ul senki nem f´er hozz´a a ny´ılt ada´ ok tokhoz, hiszen kulcs n´elk¨ ul nem lehet desifr´ırozni a rejtjelezett u ¨zenetet. Arul´ felbukkan´asa azonban most is elk´epzelhet˝o: • egy jogos felhaszn´al´o tov´abb tudja adni a m´ar visszafejtett u ¨zenetet, illetve • t¨obb jogos felhaszn´al´o ¨ossze´allhat, ´es ´ep´ıthet egy kal´oz dek´odert, amelybe a saj´at kulcsaikat ´ep´ıtik be, hogy m˝ uk¨odj¨on. Minden felhaszn´al´o ugyanazt az u ¨zenetet kapja meg, ezekben nincs elrejtve ujjlenyomat. ´Igy a ny´ılt u ¨zenet tov´abbad´asa eset´en kriptogr´afiai (matematikai) m´odszerekkel lehetetlen lebuktatni az ´arul´ot, hiszen a kisziv´argott ny´ılt u ¨zenet b´armelyik jogos felhaszn´al´ot´ol sz´armazhatott. ´Igy az al´abb ismertetett s´em´aval semmire sem megy¨ unk a nyomoz´as sor´an, ha egy ´arul´o mag´at a ny´ılt u ¨zenetet adja tov´abb. A m´odszer csak akkor haszn´alhat´o, ha a visszafejt´eshez sz¨ uks´eges kulcs sziv´arog ki. R¨ogt¨on felmer¨ ul a k´erd´es, hogy melyek azok az esetek, amikor a ,,hagyom´anyos” kal´ozkod´as (azaz: m´asol´as) ´ertelmetlen, ´es ´ıgy eleve csak a kulcs tov´abbad´asa j¨ohet sz´oba? Olyan alkalmaz´asokra kell gondolni, ahol az ´arul´oknak nincs lehet˝os´eg¨ uk arra –vagy egyszer˝ uen nem ´eri meg nekik–, hogy a ny´ılt adatokat tov´abb´ıts´ak a kal´ozoknak. Ez lehet p´eld´aul az´ert, mert az adatok folyamatosan v´altoznak, ´es t´ ul dr´aga lenne az ´arul´oknak egy ,,´atj´atsz´o” infrastrukt´ ur´at ki´ep´ıteni. Ez a helyzet p´eld´aul egy fizet˝os telev´ız´ocsatorn´an´al, ahol dek´odert kell venn¨ unk, hogy n´ezhess¨ uk az ad´ast. (Dek´oder n´elk¨ ul csak zajos k´epet lehet l´atni.) Az ´arul´oknak egyszer˝ uen nem ´eri meg fel´all´ıtani egy ´atj´atsz´o´allom´ast, ´es kal´oz-sz´or´asba kezdeni, hogy a m´ar dek´odolt ad´ast tov´abb´ıthass´ak. Ilyenkor az ´arul´asnak csak az a form´aja k´epzelhet˝o el, amikor n´eh´any jogosult felhaszn´al´o saj´at maga ´ep´ıt egy kal´oz dek´odert. A c´ımben kiss´e ¨onk´enyesen haszn´altuk a dinamikus jelz˝ot. Ezzel ´eppen az olyan alkalmaz´asokra k´ıv´antunk utalni, ahol az adatok nem statikusak, ´ıgy az ´arul´oknak nem ´eri meg a ny´ılt u ¨zenetet tov´abbj´atszani. 31

Egy fontos felt´ etelez´ es Tegy¨ uk fel, hogy egy vagy t¨obb felhaszn´al´o fabrik´al egy kal´oz dek´odert, amelybe a saj´at kulcsai k¨oz¨ ul ´ep´ıt be n´eh´anyat. A c´elunk az, hogy a dek´oderrel t¨ort´en˝o k´ıs´erletezget´es alapj´an legal´abb egy felhaszn´al´ot azonos´ıtani tudjunk, aki biztosan adott kulcsot a dek´oderbe. Egy nagyon fontos felt´etelez´es h´ uz´odik meg a h´att´erben: feltessz¨ uk a kal´oz dek´oderr˝ol, hogy tudunk vele k´ıs´erletezni. Ez azt jelenti, hogy fekete dobozk´ent haszn´alva tetsz˝oleges bemen˝o adatokkal tudjuk tesztelni, hogy milyen kimenetet szolg´altat. Feltessz¨ uk, hogy a dek´oderbe nincs be´ep´ıtve semmilyen ¨onmegsemmis´ıt˝o mechanizmus, ´es azt sem ´eszleli, hogy most ´epp k´ıs´erletez¨ unk vele, ´es nem a ,,szok´asos” ad´ast fejti vissza. L´atni fogjuk, hogy ez a fajta k´ıs´erletez´es el´eg lesz ahhoz, hogy a dek´oderb˝ol kinyerj¨ uk a kulcsokat. Teh´at egy hardveres dek´oder eset´en nincs sz¨ uks´eg arra, hogy sz´etszedj¨ uk, ´es megvizsg´aljuk a benne tal´alhat´o ´aramk¨or¨oket; hasonl´oan, szoftveres dek´oder eset´en nincs sz¨ uks´eg a forr´ask´odra, hogy sikeresen meghat´arozzuk a dek´oder ´altal haszn´alt kulcsokat. T´erj¨ unk vissza egy pillanatra az ujjlenyomat-k´odokhoz. Az ebben a r´eszben bemutatott rendszerek is ugyanazon az elven m˝ uk¨odnek, mint az ujjlenyomat-k´odok. Az ujjlenyomat szerep´et itt a kulcsok j´atssz´ak. Ebben a modellben hamis´ıt´asnak az min˝os¨ ul, ha egy, vagy t¨obb felhaszn´al´o megpr´ob´al kal´oz dek´odert ´ep´ıteni. Egy ilyen dek´oderbe k´enytelenek az eredeti kulcsokat be´ep´ıteni, k¨ ul¨onben az eszk¨oz nem tudn´a dek´odolni az ad´ast. A kor´abbi modell sz´ohaszn´alat´aval ´elve mindez azt jelenti, hogy az ´arul´ok nem ´ırhatnak ?-t a l´athat´o poz´ıci´okra. A nyomoz´ast is az elfogott dek´oderben tal´alhat´o kulcsok alapj´an v´egezz¨ uk majd. Mint l´atni fogjuk, ebben a gyeng´ebb modellben m´ar lehet olyan rendszert ´ep´ıteni, amelynek 100%-os a megb´ızhat´os´aga. Hat´ ekonys´ agi ´ es kriptogr´ afiai param´ eterek Az adatszolg´altat´o titkos´ıtott form´aban osztja sz´et az adatot, amit felhaszn´al´oi oldalon egy dek´oder fejt vissza. Ehhez a m˝ uvelethez kulcs(ok)ra van sz¨ uks´eg. A rendszer biztons´aga egy kriptogr´afiai param´etert˝ol f¨ ugg. Ez nem m´as, mint az u ¨zenetek rejtjelez´es´ehez haszn´alt kulcs hossza, amit s-sel jel¨ol¨ unk. (L´atni fogjuk, hogy ez a kulcshossz egy szimmetrikus titkos´ıt´o algoritmushoz tartozik. A rendszerben sok m´as kulcs is el˝ofordul. Funkci´ojukban ezek teljesen m´as kulcsok, de a hosszuk mindig s.) Fontos, hogy az alkalmazott technik´ak hat´ekonyak legyenek, ´ıgy figyelemmel kell lenn¨ unk h´arom tov´abbi param´eterre is: • Egy jogos felhaszn´al´o (dek´oder) t´ ar- ´es id˝ oig´enye. A t´arig´eny a felhaszn´al´onak osztott kulcsok ¨osszhossza, az id˝oig´eny pedig az egy u ¨zenetblokk visszafejt´es´ehez sz¨ uks´eges m˝ uveletek sz´ama. Term´eszetesen a dek´odol´ashoz sz¨ uks´eg van m´eg helyre ezen fel¨ ul, de ez a t´arig´eny elhanyagolhat´o. Ezek a param´eterek 32

a gyakorlati alkalmaz´asokban er˝osen korl´atozottak. A dek´oderek fizikailag nem lehetnek t´ ul nagyok, ´es val´os id˝oben kell tudniuk visszafejteni az ad´ast. • Az adatszolg´altat´o t´ar- ´es id˝ oig´enye. A t´arig´eny a rendszer futtat´as´ahoz sz¨ uks´eges ¨osszes adat t´arol´asa, az id˝oig´eny pedig az egy u ¨zenetblokk ¨ossze´all´ıt´as´ahoz sz¨ uks´eges m˝ uveletek sz´ama. Ezek kev´esb´e fontos param´eterek, hiszen az adatszolg´altat´o oldal´an l´enyeg´eben nincs t´arkorl´atoz´as, ´es a k´odol´as is elv´egezhet˝o j´oval az ad´as el˝ott. • Kommunik´aci´os t¨obblet. Az a plusz, amennyivel megn¨ovekszik az u ¨zenetcso16 magok hossza a hagyom´anyosan rejtjelezett ad´as´ehoz k´epest.

4.2.

A trivi´ alis megold´ as

Elk´epzelhet˝o egy olyan konstrukci´o, amelyben minden felhaszn´al´o egyetlen visszafejt˝o kulcsot kap. A szolg´altat´o ilyenkor minden adatcsomagot n k¨ ul¨onb¨oz˝o kulccsal rejtjelez, ´es minden j´at´ekosnak az ˝o kulcs´aval visszafejthet˝o u ¨zenetet k¨ uldi el. Ebben a rendszerben elfoghat´ok az ´arul´ok: ha egy felhaszn´al´o el´arulja a kulcs´at valakinek, akkor a kulcs alapj´an k¨onnyed´en (´es 100%-os biztons´aggal) meg´allap´ıthat´o a szem´elye (hiszen azzal a kulccsal csak ˝o rendelkezett). Ezt nevezz¨ uk trivi´alis s´em´anak. Igaz ugyan, hogy egy j´at´ekosnak csup´an egyetlen kulcsot kell t´arolnia, a gyakorlatban ez a m´odszer m´egsem alkalmazhat´o, mert a szolg´altat´onak az eredeti adatok n-szeres´et kell tov´abb´ıtania. Ezt az ´ori´asi kommunik´aci´os t¨obbletet a k¨ovetkez˝o tr¨ ukkel lehet lejjebb szor´ıtani. Titkos´ıtsuk az adatot, de csak egyetlen kulccsal, ´es mag´at a titkos´ıt´o kulcsot rejtjelezz¨ uk sok k¨ ul¨onb¨oz˝o kulccsal! ´Igy az u ¨zenet¨ unk k´et r´eszb˝ol fog ´allni: a titkos´ıtott adatb´ol, ´es titkos´ıt´o kulcs rejtjelezett p´arj´ab´ol.

4.3.

A s´ ema fel´ ep´ıt´ ese

A k¨ovetkez˝o ´altal´anos form´aban ´ırjuk le a s´em´at: az adatszolg´altat´o gener´al egy metakulcsot, amely ´all egy A kulcshalmazb´ol, ´es egy P : {1, . . . , n} → P(A) lek´epez´esb˝ol, ahol P(A) az A hatv´anyhalmaza. Az A kulcsuniverzum tartalmazza az ¨osszes lehets´eges kulcsot, ami a rendszerben felhaszn´al´asra ker¨ ulhet, ezek tipikusan v´eletlen bitsorozatok. A P f¨ uggv´eny reprezent´alja a kulcskioszt´ast: egy adott felhaszn´al´ohoz hozz´arendel n´eh´any kulcsot A-b´ol. A P (u) ⊂ A halmaz jel¨oli az u felhaszn´al´o kulcsait. Egy u ¨zenet a nyomoz´o s´em´aban k´et r´eszb˝ol ´all: egy titkos´ıt´ o blokkb´ ol, ´es egy enged´elyez˝o blokkb´ol. A titkos´ıt´o blokk tartalmazza az ´erdemi u ¨zenetet (pl. az esti 16

Azaz amikor egyetlen fix kulcs van, amit az ¨osszes j´at´ekos ismer, ´es ami mindv´egig v´altozatlan marad.

33

film egy 2 m´asodperces darabj´at) egy r v´eletlen kulccsal rejtjelezve. Ezt a titkos´ıt´ast valamilyen szimmetrikus kulcs´ u kriptorendszer v´egzi (pl. 3DES). Az enged´elyez˝o blokk szerepe pedig az, hogy seg´ıts´eg´evel a jogos felhaszn´al´ok a saj´ at kulcsaik seg´ıt´ s´eg´evel megkapj´ak r-t. Igy r birtok´aban ki tudj´ak nyerni az adatot a titkos´ıt´o blokkb´ol. A 4.5. ´es 4.6. ´abr´an EB-vel jel¨olt¨ uk az enged´elyez˝o blokkot, ´es TB-vel a titkos´ıt´o blokkot. Az adatszolg´altat´o a sug´arzott ad´ast blokkokra osztja, ´es blokkonk´ent titkos´ıtva k¨ uldi el. L´enyeges, hogy minden adatblokk rejtjelez´es´ehez u ´j ´es v´eletlen r kulcsot kell haszn´alni.

az ad´ as csomagjai

Szolg´ altat´ o

-

EB

TB

EB

TB

EB

TB . . .

EB

TB

- dek´ oder

?

ny´ ılt ¨ uzenet

4.5. ´ abra. A rendszer sematikus rajza

34

EB

A dek´ oder kulcsai -

TB

?

?

Kulcsviszszafejt´ es

r

Szimmetrikus dek´ odol´ o

Dek´ oder

?

ny´ ılt ¨ uzenet

4.6. ´ abra. A dek´oder m˝ uk¨od´ese A nyomoz´o rendszert funkcion´alisan h´arom j´ol elk¨ ul¨on¨ ul˝o r´eszre lehet bontani. Minden esetben e h´arom egys´eg m˝ uk¨od´es´et ´ırjuk majd le. • Inicializ´al´o s´ema: az adatszolg´altat´onak a m˝ uk¨od´es megkezd´ese el˝ott l´etre kell hoznia egy α metakulcsot: gener´alnia kell egy A kulcshalmazt, ´es defini´alnia kell a P kulcskioszt´o f¨ uggv´enyt. K´es˝obb, egy-egy u ´j felhaszn´al´o csatlakoz´asakor ezen α metakulcs alapj´an adja ki az ad´as visszafejt´es´ehez sz¨ uks´eges kulcsokat. Ezeket az el˝ok´esz´ıt˝o l´ep´eseket nevezz¨ uk inicializ´al´asnak. • Rejtjelez˝o s´ema: ez a ,,rendes” m˝ uk¨od´es´et le´ır´o r´esz. Itt kell megadni, hogy a szolg´altat´o mik´epp ´all´ıtja ¨ossze az enged´elyez˝o blokkot, azaz hogyan rejti el az adat titkos´ıt´as´ahoz haszn´alt r kulcsot. Term´eszetesen az is ide tartozik, hogy egy jogos felhaszn´al´o hogyan tudja visszafejteni az ad´ast. L´athat´o, hogy a komponens tulajdonk´eppen k´et r´eszre bomlik: egy k´ odol´ o ´es egy dek´ odol´ o ∗ ∗ s´em´ara. A szolg´altat´o oldal´an fut az Eα : {0, 1} → {0, 1} k´odol´o algoritmus, az u felhaszn´al´on´al pedig a DP (u) : {0, 1}∗ → {0, 1}∗ dek´odol´o algoritmus. Tetsz˝oleges m ∈ {0, 1}∗ u ¨zenet eset´en DP (u) (Eα (m)) = m. Mind a k´odol´as, mind a dek´odol´as k´et l´epcs˝oben zajlik. A szolg´altat´o blokkonk´ent k¨ uldi az adatokat. Egy blokkot el˝osz¨or titkos´ıt, majd a titkos´ıt´o kul35

csot elrejti az enged´elyez˝o blokkban. Felhaszn´al´oi oldalon el˝osz¨or ebb˝ol az enged´elyez˝o blokkb´ol kell kinyerni a kulcsot, ´es csak ezut´an lehet visszafejteni az u ¨zenetet. • Nyomoz´o algoritmus: v´eg¨ ul be kell l´atni, hogy a s´ema nyomozhat´o. Ehhez konstru´alni kell egy nyomoz´o algoritmust, amely egy lefoglalt kal´oz dek´oder alapj´an meg´allap´ıtja valamelyik ´arul´o szem´ely´et. (Az algoritmus fekete dobozk´ent k´ıs´erletezik a dek´oderrel: an´elk¨ ul, hogy sz´et kellene szedni.) Az ´altalunk vizsg´alt s´em´akban az A mindig egy m´atrix lesz, a P f¨ uggv´eny pedig ´ minden felhaszn´al´ohoz soronk´ent egy elemet (kulcsot) rendel A-b´ol. Atmenetileg jel¨olj¨ uk l-lel a sorok, t-vel az oszlopok sz´am´at A-ban. (Ez a k´et ´ert´ek a felhaszn´al´ok ´es a lehets´eges ´arul´ok sz´am´at´ol f¨ ugg majd.) A m´atrix minden eleme egy v´eletlen kulcs lesz: ai,j ∈ {0, 1}s , ahol s titkos´ıt´o blokkok l´etrehoz´as´ahoz haszn´alt szimmetrikus kriptorendszer kulcshossza. Jel¨olj¨ uk Ai -vel az A kulcsm´atrix i. sor´at: Ai = {ai,1 , ai,2 , . . . , ai,t }. A kulcskioszt´o f¨ uggv´eny a k¨ovetkez˝o alak´ u lesz: P : {1, . . . , n} → A1 × A2 × . . . × Al lek´epez´es. Ennek megfelel˝oen, ha azt mondjuk, hogy az ,,u felhaszn´al´o i. kulcsa”, akkor a P (u) i. komponens´ere gondolunk: az u azon kulcsa, amely az A kulcsm´atrix i. sor´ab´ol sz´armazik.

a1,1

a1,2

...

a1,t

a2,1

a2,2

...

a2,t

...

al,t

..

al,1

.

al,2

4.7. ´ abra. Az A kulcsm´atrix

36

4.4.

A nyomoz´ o s´ em´ ak kategoriz´ al´ asa

A nyomoz´o s´em´akat k´et szempont szerint oszt´alyozzuk. Rugalmass´ ag A nyomoz´o s´em´ak k´et csoportra oszthat´ok aszerint, hogy milyen hat´ asfok´ u dek´oderek ellen m˝ uk¨odnek hat´ekonyan. A rejtjelez˝o s´em´aban haszn´alt algoritmusokr´ol feltessz¨ uk, hogy biztons´agosak. Ez intuit´ıven azt jelenti, hogy a dek´odernek kulcsok n´elk¨ ul nincs jobb fejt´esi strat´egi´aja, mint a kimer´ıt˝o keres´es. Ha ez val´oban teljes¨ ul, akkor k¨onnyen meghat´arozhat´o az a q(t) val´osz´ın˝ us´eg, amellyel felt¨orhet˝o egy u ¨zenetblokk, ha t id˝o ´all rendelkez´esre. (Mindez annyit jelent, hogy b´armely kulcsok n´elk¨ ul fut´o dek´oder legfeljebb q(t) ar´anyban fejti helyesen az u ¨zenetblokkokat.) P´eld´aul a One Time Pad eset´en a kulcs ismerete n´elk¨ ul val´oban nincs jobb strat´egia a tippel´esn´el. Ha s hossz´ u a rejtjelezett u ¨zenet, akkor 2s f´ele lehet az eredeti. L´enyeg´eben mi is a One Time Pad-et haszn´aljuk a kulcsok rejtjelez´es´ehez. Egy adott kal´oz dek´oderrel csak akkor foglalkozunk, ha enn´el a q(t)-n´el hat´arozottan jobb ar´anyban fejti az u ¨zenetblokkokat. Egy ilyen dek´odert m˝ uk¨ od˝ o dek´ odernek nevez¨ unk (arra utalva, hogy t¨obbet tud a semmin´el). Ellenkez˝o esetben egyr´eszt tot´alisan haszn´alhatatlan a dek´oder (mivel ´ertelmesen alacsony id˝okorl´at mellett q(t) nagyon pici), m´asr´eszt k¨onnyen el˝ofordulhat, hogy egyetlen kulcsot sem tartalmaz, ´ıgy nincs mit kinyomozni. Az viszont igaz, hogy egy m˝ uk¨od˝o dek´oder sz¨ uks´egk´eppen tartalmaz kulcsokat. Az el˝ofordul´o kal´oz dek´oderek fejt´esi ar´anya szerint k´etf´ele nyomoz´o s´em´at k¨ ul¨onb¨oztet¨ unk meg: a teljesen rugalmasnak nevezz¨ uk az olyan s´em´at, amelyben minden m˝ uk¨ od˝ o kal´oz dek´oder gy´art´oja lebukik (pontosabban az ´arul´o koal´ıci´ob´ol legal´abb egy szem´ely). Ez teljes biztons´agot ad az adatszolg´altat´onak, ´es olyan esetekben ´erdemes alkalmazni, amikor az adatok t¨ored´ek´enek kisziv´arg´asa is k´art okoz. M´asr´eszt viszont elk´epzelhet˝o az, hogy nem kell t¨or˝odn¨ unk a m˝ uk¨od˝o, de ,,rossz” sz´azal´ekban fejt˝o dek´oderekkel. A telev´ızi´os p´eld´an´al maradva: ha egy dek´oder csup´an 70%-´at fejti vissza az ad´asnak, akkor – noha biztosan tartalmaz kulcsokat – nem ´erdemes foglalkozni vele, hiszen haszn´alhatatlan. Az esti film ´elvezhetetlen, ha minden perc´eb˝ol 18 m´asodperc zaj. Egy ilyen kal´oz dek´oder´ert senki nem adna p´enzt. Konstru´alhat´ok olyan s´em´ak is, amelyek csak egy bizonyos k¨ usz¨obn´el jobb ar´anyban fejt˝o dek´oderek eset´en m˝ uk¨odnek, azaz p´eld´aul csak a 99%-n´al jobban fejt˝o dek´oderek eset´en lehets´eges a nyomoz´as. Ezeket k¨ usz¨ ob s´em´ aknak nevezz¨ uk. El˝ony¨ uk az, hogy az u ¨zenetek ler¨ovid¨ ulnek, ´es a visszafejt´eshez kevesebb m˝ uveletre van sz¨ uks´eg.

37

Titkoss´ ag Egy kriptogr´afiai s´ema kidolgoz´as´an´al mindig felvet˝odik a k´erd´es: a rendszer mely r´eszei legyenek publikusak? Az elm´elet szerint a rendszer biztons´ag´at a kulcsok titkoss´aga szavatolja; a t¨obbi komponensr˝ol (pl. a rejtjelez˝o s´ema, nyomoz´o algoritmus) felt´etelezni kell, hogy k¨ozismert. Ez az u ´gynevezett Kerckhoffs-elv. A mi eset¨ unkben ez azt jelenti, hogy a rejtjelez˝o s´ema is nyilv´anos az Eα k´odol´o ´es a DP (u) dek´odol´o algoritmussal egy¨ utt. A dek´odol´o algoritmus azonban a felhaszn´al´o kulcsait´ol f¨ ugg, teh´at minden felhaszn´al´o eset´en m´as. Ha ezt nyilv´anoss´a tessz¨ uk, akkor ezzel egy¨ utt k¨ozkinccs´e v´alik a P kulcskioszt´o f¨ uggv´eny is. Ebben az esetben nyilv´ anos s´em´ar´ol besz´el¨ unk. Maguk a kulcsok (vagyis az A elemei) term´eszetesen nem publikusak, csak az, hogy melyik felhaszn´al´o melyik kulcsokat kapta. A gyakorlatban azonban sokszor titkos s´em´ akat alkalmaznak, amikor titokban ´ marad, hogy melyik felhaszn´al´o mely kulcsokkal rendelkezik. Altal´ aban ´erdemes ilyen s´em´akat haszn´alni, mert biztosan nem gyeng´ebbek ny´ılt t´arsaikn´al. A h´atr´anyuk az, hogy n´eh´any u ´jabb biztons´agi k¨ovetelm´eny el´e ´all´ıtj´ak az adatszolg´altat´ot. Ebben a dolgozatban nem tekintj¨ uk ´at az ¨osszes s´emat´ıpust. Els˝ok´ent egy olyan rendszert vizsg´alunk, amelyben egy ´arul´o sz˝ urhet˝o ki. Ez egy ny´ılt, teljesen rugalmas s´ema lesz. Ut´ana k¨ ul¨on eml´ıtj¨ uk a k´et ´arul´os esetet, amelyre egy titkos, teljesen rugalmas s´em´at alkotunk meg. V´eg¨ ul pedig megvizsg´aljuk a probl´em´at teljes ´altal´anoss´ag´aban, nagyobb koal´ıci´okra is. Ez az s´ema titkos, ´es teljesen rugalmas. Bizonyos technikai neh´ezs´egeket elker¨ ulend˝o, egy kicsit leegyszer˝ us´ıtj¨ uk a probl´em´at. Mint k´es˝obb l´atni fogjuk, az ´altalunk vizsg´alt s´em´ak mind olyanok, hogy ha egy dek´oder m˝ uk¨odik, akkor k´epes az ad´as 100%-os visszafejt´es´ere is. Ez term´eszetesen nem jelenti azt, hogy a dek´oder val´oban 100%-osan fejt. A bemutatott s´em´akban b´armelyik m˝ uk¨od˝o kal´oz dek´oder eset´en sikeresen v´egrehajthat´o a nyomoz´as. Ak´ar abban az esetben is, ha a dek´oder nagyon rosszul fejt (de ann´al jobban, mintha a szimmetrikus kulcs´ u rejtjelez˝ot t¨orn´e fel). Az egyszer˝ ubb t´argyal´as kedv´e´ert csak az olyan dek´oderekkel foglalkozunk, amelyek val´oban 100%-osan fejtenek. Ez a megszor´ıt´as legink´abb a defin´ıci´oban okoz v´altoz´ast, a s´em´akban nem. A teljesen ´altal´anos s´ema-defin´ıci´o megtal´alhat´o [4]-ben. K´et defin´ıci´oban foglaljuk ¨ossze a nyomoz´o s´em´akkal szembeni elv´ar´asainkat. Az els˝o defin´ıci´oban az ´altal´anos,  hib´aj´ u s´em´akat hat´arozzuk meg. 4.1. Defin´ıci´ o. Legyen C egy tetsz˝ oleges legfeljebb k tagb´ ol ´ all´ o koal´ıci´ o, ´es tegy¨ uk fel, hogy C fabrik´al egy kal´oz dek´ odert, amely a rendszerben leadott u ¨zeneteket hib´ atlanul tudja fejteni. Az inicializ´al´o s´ema, rejtjelez˝o s´ema, nyomoz´o algoritmus alkotta h´ armast (, k)-biztos nyomoz´o s´em´ anak nevezz¨ uk, ha a nyomoz´ o algoritmus legal´ abb 1 −  val´osz´ın˝ us´eggel meg tud hat´ arozni egy C-beli felhaszn´ al´ ot. 38

Mint eml´ıtett¨ uk, ebben a modellben lehet˝os´eg ny´ılik olyan s´em´ak konstru´al´as´ara, amelyek 100%-os biztons´aggal nyomoznak. Ezt r¨ogz´ıti az al´abbi defin´ıci´o. 4.2. Defin´ıci´ o. Egy nyomoz´o s´em´ at (tot´ alisan) k-biztosnak nevez¨ unk, ha tetsz˝ oleges legfeljebb k tag´ u koal´ıci´o ´altal fabrik´ alt kal´ oz dek´ oder alapj´ an biztosan elfoghat´ o egy tagja a koal´ıci´onak.

4.5.

A legegyszer˝ ubb eset: egyetlen ´ arul´ o

Kiindul´ask´ent vizsg´aljuk meg a lehet˝o legegyszer˝ ubb esetet, amikor legfeljebb k = 1 ´arul´o van! Megadunk egy ny´ılt, teljesen rugalmas s´em´at, amelyben biztosan elfoghat´o az ´arul´o. Inicializ´ al´ o s´ ema A rendszerben ¨osszesen n felhaszn´al´o van, ´ıgy egy felhaszn´al´ot log n bittel tudunk azonos´ıtani. A kulcsuniverzum legyen a k¨ovetkez˝o: A = {a01 , a11 , a02 , a12 , . . . , a0log n , a1log n } , ahol aji ∈ {0, 1}s v´eletlen bitsorozat.

a01

a11

a02

a12

.. .

a0log n

a1log n

4.8. ´ abra. A kulcsm´atrix A kulcsokat u ´gy osztjuk ki, hogy minden felhaszn´al´o pontosan egy kulcsot kapjon a kulcsm´atrix minden egyes sor´ab´ol. Tegy¨ uk fel, hogy az u felhaszn´al´o azonos´ıt´oja

39

a b1 b2 b3 . . . blog n bitsorozat (bi ∈ {0, 1}). Ekkor az u felhaszn´al´o kulcsai legyenek a k¨ovetkez˝ok: blog n P (u) = (ab11 , ab22 , . . . , alog n) . L´athat´o, hogy mindenkin´el log n darab kulcs lesz. Rejtjelez˝ o s´ ema Egy adatblokk tov´abb´ıt´asa a k¨ovetkez˝ok´eppen t¨ort´enik. A szolg´altat´o v´alaszt egy r ∈ {0, 1}s v´eletlen kulcsot, majd ezzel a kulccsal, ´es a szimmetrikus kulcs´ u krip´ torendszerrel rejtjelezi az adatot. Igy el˝o´allt a rejtjelez˝o blokk, amely a val´odi tartalmat hordozza. Ezut´an a kulcsm´atrix minden sor´ahoz v´alaszt egy v´eletlen bitsorozatot (¨osszesen log n darabot), amelyek mind ugyanolyan hossz´ uak, mint r, ´es a bitenk´enti ¨osszeg¨ uk ´eppen r: r1 ⊕ r2 ⊕ . . . ⊕ rlog n = r . Minden ri -b˝ol (1 ≤ i ≤ log n) nyer¨ unk k´et u ´jabb bitsorozatot u ´gy, hogy az A 0 ´ kulcsm´atrix i. sor´anak mindk´et elem´ehez hozz´aadjuk. Igy kapjuk ei -t ´es e1i -t: e0i = ri ⊕ a0i e1i = ri ⊕ a1i Az ´ıgy l´etrej¨ov˝o E m´atrix lesz maga az enged´elyez˝o blokk, amelyet az r kulccsal titkos´ıtott u ¨zenettel egy¨ utt k¨ uld¨ unk el. Az enged´elyez˝o blokk m´ereteit tekintve pont olyan, mint az A kulcsm´atrix. Ahhoz, hogy a s´ema m˝ uk¨od˝ok´epes legyen, minden felhaszn´al´onak vissza kell tudnia fejteni az u ¨zenetet. N´ezz¨ uk, hogy ez mi´ert lehets´eges: az u felhaszn´al´o a saj´at kulcsaival ki tudja nyerni a rejtjelez˝o blokkb´ol az ri -ket (1 ≤ i ≤ log n), hiszen ri = eui i ⊕ aui i , ´es a jobboldalon ´all´o tagokat u ismeri: eui i -t az enged´elyez˝o blokkb´ol olvassa ki, aui i pedig az i. kulcsa. Ha megvannak az ri -k, akkor bitenk´enti ¨osszead´assal ad´odik r, amellyel m´ar visszafejthet˝o az u ¨zenet. Param´ eterek Egy felhaszn´al´onak ¨osszesen log n darab kulcsot kell t´arolnia (ami ¨osszesen s log n bitet vesz ig´enybe), ´es egy blokk visszafejt´es´ehez log n + 1 m˝ uveletre van sz¨ uks´eg. (Itt ,,m˝ uvelet” alatt k´et s hossz´ u bin´aris sz´am mod 2 ¨osszead´as´at ´ertj¨ uk.) A kommunik´aci´os t¨obblet s log n bit, ami a log n darab titkos´ıtott kulcs enged´elyez˝o blokkban t¨ort´en˝o tov´abb´ıt´as´ab´ol ad´odik.

40

e01

e11

e02

e12

.. .

e0log n

e1log n

4.9. ´ abra. Az enged´elyez˝o blokk Nyomoz´ o s´ ema Be kell l´atnunk, hogy ebben a s´em´aban a mag´anyos ´arul´ok mindig lebuknak. Tegy¨ uk fel teh´at, hogy egy felhaszn´al´o k´esz´ıt egy kal´oz dek´odert, amelybe jobb h´ıj´an a saj´at kulcsait ´ep´ıti be (hisz m´as kulcsot nem ismer). Felt´etelezhetj¨ uk, hogy az ¨osszes kulcs´at be´ep´ıti a dek´oderbe, ugyanis ha pl. az i. kulcs´at kihagyn´a, akkor a dek´oder az enged´elyez˝o blokk i. sor´ab´ol k´eptelen lenne vissza´all´ıtani ri -t. Ekkor mag´ar´ol az r kulcsr´ol sincs semmilyen inform´aci´oja, hiszen a dek´oder csak r ⊕ ri -t ismeri. Ebb˝ol pedig ri n´elk¨ ul nem lehet kital´alni r-t (a legjobb m´odszer a tal´algat´as lenne). Az r kulcs hi´any´aban pedig a dek´oder k´eptelen visszafejteni a titkos´ıt´o blokk tartalm´at, azaz: a dek´oder nem m˝ uk¨odik. Elmondhatjuk teh´at, hogy egy kal´oz dek´odernek rendelkeznie kell legal´abb egy kulccsal minden sorb´ol. Ellenkez˝o esetben • vagy nem m˝ uk¨odik a dek´oder, • vagy mag´at a rejtjelez˝o s´em´at t¨ori fel (azaz: nincs sz¨ uks´ege az r kulcsra). Ezt a k´et lehet˝os´eget egyar´ant kiz´artuk kor´abban. Az egyetlen feltev´es¨ unk a lefoglalt kal´oz dek´oderr˝ol, hogy tudunk k´ıs´erletezni vele: fekete dobozk´ent haszn´alva k¨ ul¨onb¨oz˝o bemen˝o adatokkal tudjuk futtatni an´elk¨ ul, hogy a dek´oder ´eszleln´e azt, hogy ´eppen k´ıs´erletez¨ unk vele. log n darab k´ıs´erletet fogunk v´egrehajtani. Mindegyik k´ıs´erletben egy szab´alyos titkos´ıt´o ´es egy m´odos´ıtott enged´elyez˝o blokkot fogunk beadni. Ezut´an megfigyelj¨ uk, hogy kimenetk´ent mikor jelenik meg helyesen az ´altalunk rejtjelezett u ¨zenet, ´es mikor kapunk zagyvas´agot. Ennek megfelel˝oen minden k´ıs´erletn´el be´all´ıtunk egy xi v´altoz´ot 0-ra vagy 1-re. Ez fogja jelezni, hogy a dek´oder i. kulcsa a0i avagy a1i . 41

Az i. k´ıs´erlet a k¨ovetkez˝o k´eppen zajlik: az enged´elyez˝o blokkban az e0i hely´ere egy v´eletlen bitsorozatot ´ırunk, azaz ,,letakarjuk” e0i -t. Ha az ´ıgy k´epzett u ¨zenetet helyesen dek´odolja a szerkezet, akkor levonhatjuk azt a k¨ovetkeztet´es, hogy a dek´oder i. kulcsa nem a0i , hanem a1i , teh´at be´all´ıtjuk xi = 1-et. Ha a k´ıs´erlet sor´an nem az eredeti u ¨zenetet kapjuk vissza, akkor meg´allap´ıthatjuk, hogy a dek´oder az 0 ai kulccsal ,,szeretett volna” fejteni, ´es be´all´ıtjuk xi = 0-t. Ezt elv´egezz¨ uk minden i = 1, . . . , log n-re, majd a kapott xi -ket ¨osszeolvasva meg´allap´ıthatjuk az ´arul´o azonos´ıt´oj´at: x = x1 x2 . . . xlog n az ´arul´o. Az ismertetett s´em´ar´ol elmondhatjuk, hogy ny´ılt, hiszen a P publikuss´a t´etele semmivel sem k¨onny´ıti meg az egy szem ´arul´o helyzet´et. Nincs v´alaszt´asi lehet˝os´ege: csak a saj´at kulcsait tudja felhaszn´alni. Foglaljuk ¨ossze ezeket az eredm´enyeket egy t´etelben. 4.3. T´ etel. L´etezik olyan 1-biztos ny´ılt nyomoz´ o s´ema, ahol egy felhaszn´ al´ onak log n kulcsot kell t´arolnia, egy blokk visszafejt´es´ehez log n + 1 m˝ uvelet sz¨ uks´eges, ´es az enged´elyez˝o blokk log n titkos´ıtott kulcsot tartalmaz.

4.6.

K´ et ´ arul´ o

Miel˝ott r´at´ern´enk az ´altal´anos esetre, vizsg´aljunk meg egy k = 2-re is m˝ uk¨od˝o rendszert. A s´ema hasonl´o lesz az el˝oz˝oh¨oz, azzal a k¨ ul¨onbs´eggel, hogy a legfeljebb k´et tag´ u koal´ıci´okat is le tudjuk majd buktatni. Az el˝oz˝o s´em´aban ez nem teljes¨ ult. L´assuk mi´ert! Tegy¨ uk fel, hogy a k = 1-es s´em´aban sz¨ovetkezik k´et j´at´ekos: u ´es v. Nagyon nagy val´osz´ın˝ us´eggel u ´es v azonos´ıt´oja legal´abb k´et biten elt´er. (Egy adott u-hoz ¨osszesen log n darab olyan felhaszn´al´o van, akinek az azonos´ıt´oja csup´an egy biten t´er el u azonos´ıt´oj´at´ol.) Ez lehet˝ov´e teszi azt, hogy olyan kulcsokat u ¨ltessenek a kal´oz dek´oderbe, amely alapj´an egy harmadik, ´artatlan felhaszn´al´ot gyan´ us´ıt meg a nyomoz´o algoritmus. (Pl.: minden sorb´ol u kulcsait helyezik el a dek´oderben, kiv´eve egyetlen olyan sort, ahol viszont v – u-´et´ol k¨ ul¨onb¨oz˝o – kulcs´at ´ep´ıtik be). E kulcskioszt´as alapj´an sem u-t, sem v-t nem lehet egy´ertelm˝ uen meggyan´ us´ıtani. Viszont igaz az, hogy a be´ep´ıtett kulcsok egy harmadik, ´artatlan f´el kulcsaival egyeznek meg, aki ily m´odon gyan´ uba keveredett.) A probl´ema abb´ol ad´odik, hogy k¨onnyen el˝ofordulhat, hogy egy u-t´ol ´es v-t˝ol k¨ ul¨onb¨oz˝o, ´artatlan j´at´ekosnak nagyon sok k¨oz¨os kulcsa van u-val ´es v-vel. A c´elunk az, hogy b´armely j´at´ekos-p´arosnak lehet˝oleg kev´es k¨oz¨os kulcsa b´armelyik felhaszn´al´oval. A most k¨ovetkez˝o s´ema ilyen, ez´altal k´et j´at´ekos sosem tud meggyan´ us´ıtani egy harmadikat, aki nem volt tagja a koal´ıci´ojuknak. Ehhez term´eszetesen n¨ovelni kell az A m´atrix m´eret´et.

42

Inicializ´ al´ o s´ ema Mint mindig, most is az inicializ´al´o s´ema le´ır´as´aval kezdj¨ uk. Megadjuk a szolg´altat´o metakulcs´at, vagyis az A kulcsm´atrixot ´es a P lek´epez´est, amely a kulcsok kioszt´as´at v´egzi. Az A m´atrixnak most 8 oszlopa lesz. (Hogy mi´ert pont ennyi, azt k´es˝obb l´atni fogjuk.) A sorok sz´am´at csak a gondolatmenet legv´eg´en hat´arozzuk meg, egyel˝ore bevezet¨ unk helyette egy l param´etert. K´es˝obb l´atni fogjuk, hogy az l ´ert´eke att´ol f¨ ugg majd, hogy milyen t´eved´esi val´osz´ın˝ us´eget enged¨ unk meg a nyomoz´o algorit¨ musnak. A j´at´ekosoknak u ´jfent egy kulcsot adunk minden egyes sorb´ol. Osszesen teh´at l kulcs lesz egy felhaszn´al´on´al. A kulcskioszt´ast azonban nem tudjuk olyan egyszer˝ uen v´egezni, mint az el˝oz˝o esetben. Vezess¨ uk be az Ai = {ai,1 , ai,2 , . . . , ai,8 } jel¨ol´est, amellyel az A m´atrix i. sor´ara hivatkozunk. Minden felhaszn´al´onak l kulcsa lesz, minden Ai -b˝ol pontosan egy. Azt, hogy egy felhaszn´al´o melyik kulcsot kapja Ai -b˝ol, v´eletlenszer˝ uen d¨onts¨ uk el. Ennek ´erdek´eben minden sorhoz v´alasszunk v´eletlenszer˝ uen ´es f¨ uggetlen¨ ul egy-egy hash f¨ uggv´enyt: h1 , h2 , . . . , hl . Az i. sor hash f¨ uggv´enye minden felhaszn´al´ohoz v´alaszt egy v´eletlen kulcsot az adott sor 8 elem´eb˝ol: hi : {1, 2, . . . , n} → Ai . A hash f¨ uggv´enyeket a felhaszn´al´ok nem ismerik. ´Igy ez a s´ema titkos, mert nem ¨ tudhatj´ak, hogy ki melyik kulcsokat kapta a kulcsm´atrixb´ol. Osszefoglalva, a kulcskioszt´as a k¨ovetkez˝o: P (u) = (h1 (u), h2 (u), . . . , hl (u)) . Rejtjelez˝ o s´ ema A titkos´ıt´o ´es enged´elyez˝o blokk ¨ossze´all´ıt´asa pontosan ugyan´ ugy zajlik, mint ahogy azt kor´abban l´attuk. A szolg´altat´o egy r v´eletlen kulccsal rejtjelezi az adatot: ez lesz a titkos´ıt´o blokk. Majd v´alaszt l darab v´eletlen ri -t u ´gy, hogy az r 1 ⊕ r2 ⊕ . . . ⊕ rl = r teljes¨ ulj¨on. Az ri darabot rejtjelezi az Ai ¨osszes kulcs´aval (1 ≤ i ≤ l) : ei,1 = ri ⊕ ai,1 ei,2 = ri ⊕ ai,2 .. . ei,8 = ri ⊕ ai,8 ´Igy ¨ossze´all az (ei,j ) enged´elyez˝o blokk (1 ≤ i ≤ l , 1 ≤ j ≤ 8), ami a titkos´ıt´o blokk el´e ker¨ ul. 43

K¨onnyen meggondolhat´o, hogy ez a s´ema is m˝ uk¨od˝ok´epes. Egy jogos felhaszn´al´o vissza tudja fejteni a titkos´ıt´o blokkba rejtett u ¨zenetet. Az u j´at´ekosnak minden Ai b˝ol van egy hi (u) kulcsa. Ezt a kulcsot bitenk´ent hozz´aadva az enged´elyez˝o blokk i. sor´anak megfelel˝o elem´ehez megkaphat´o ri . Ezt elv´egezve az ¨osszes sorra, ´es az eredm´enyeket bitenk´ent ¨osszegezve el˝o´all maga az r kulcs, amellyel m´ar visszafejthet˝o a titkos´ıt´o blokk tartalma. Param´ eterek L´athat´o, hogy a m´atrix minden sor´ab´ol egy kulcsot kap minden felhaszn´al´o, teh´at ¨osszesen l kulcsot kell t´arolnia. A kommunik´aci´os t¨obblet, ami az enged´elyez˝o blokk m´eret´evel egyezik meg: 8l. Egy blokk visszafejt´es´ehez l + 1 m˝ uveletre van sz¨ uks´eg. Egy m˝ uvelet itt is k´et s hossz´ u bitsorozat mod 2 ¨osszead´as´at jelenti. Nyomoz´ o s´ ema A legegyszer˝ ubb s´em´ahoz hasonl´oan most is elmondhat´o, hogy egy kal´oz dek´odernek rendelkeznie kell legal´abb egy kulccsal minden sorb´ol. Ellenkez˝o esetben • vagy nem m˝ uk¨odik a dek´oder, • vagy mag´at a rejtjelez˝o s´em´at t¨ori fel. Ha a dek´oder nem k´epes dek´odolni az ad´ast, akkor nem ´erdemes foglalkoznunk azzal, hogy ki gy´artotta. Azt pedig feltett¨ uk, hogy a haszn´alt titkos´ıt´as biztons´agos, azaz kulcs n´elk¨ ul nem t¨orhet˝o fel. Ism´et k´ıs´erletezni fogunk a dek´oderrel annak ´erdek´eben, hogy kinyerj¨ uk bel˝ole a kulcsokat. Az egyszer˝ us´eg kedv´e´ert el˝osz¨or tegy¨ uk fel azt, hogy a dek´oder pontosan egy kulcsot ismer minden sorb´ol. Ezek a kulcsok a k´et ´arul´o (u ´es v) kulcsai k¨oz¨ ul ker¨ ulnek ki, teh´at a dek´oder i. kulcsa vagy hi (u) ∈ Ai vagy hi (v) ∈ Ai . A k´ıs´erletek sor´an a dek´odernek szab´alyos titkos´ıt´o, ´es m´odos´ıtott enged´elyez˝o blokkokat fogunk beadni, ´es azt vizsg´aljuk, hogy mikor fejt helyesen. Az i. kulcsot a k¨ovetkez˝o m´odszerrel csaljuk ki: 1. Az enged´elyez˝o blokk i. sor´anak legels˝o elem´et ´ırjuk fel¨ ul egy v´eletlen bitsorozattal. Ha az ´ıgy ¨ossze´all´ıtott u ¨zenetet a dek´oder helyesen fejti vissza, akkor meg´allap´ıthajuk, hogy nem az ai,1 kulccsal dolgozik, mert ei,1 n´elk¨ ul is megfejtette si -t. 2. ´Irjuk fel¨ ul ei,1 mellett ei,2 -t is. Ha a dek´oder tov´abbra is zavartalanul m˝ uk¨odik, akkor bizton ´all´ıthatjuk, hogy nem az ai,2 kulccsal dolgozik az i. sorban. .. . 44

8. V´eg¨ ul az ei,1 , ei,2 , . . . , ei,8 is le van takarva. Ekkor a dek´oder biztosan nem tud fejteni, hiszen az enged´elyez˝o blokk i. sora teljes eg´esz´eben hi´anyzik. A k´ıs´erletez´es sor´an kellett lennie egy 1 ≤ d ≤ 8 indexnek, amikor ,,elromlott” a dek´oder. Kijelenthetj¨ uk, hogy a dek´oder rendelkezik az ai,d kulccsal. Jel¨olj¨ uk fi -vel ezt az i. sorb´ol kinyert kulcsot.

e1,1

e1,2

e1,3

e1,4

e1,5

e1,6

e1,7

e1,8

e2,1

e2,2

e2,3

e2,4

e2,5

e2,6

e2,7

e2,8

ei,6

ei,7

ei,8

el,6

el,7

el,8

.. . v´ eletlen bitsorozat

.. . el,1

el,2

el,3

el,4

el,5

4.10. ´ abra. Az enged´elyez˝o blokk az i. kulcs kinyer´es´enek egy f´azis´aban L´athat´o, hogy ezzel a m´odszerrel mind az l kulcs felfedhet˝o. Nevezz¨ uk F -nek a ´ kinyert kulcsok halmaz´at. Ekkor fi = F ∩ Ai . Ori´asi hiba lenne kiki´altani ´arul´onak azt a felhaszn´al´ot, akinek a kulcshalmaza ´epp F . Egyr´eszt nem biztos, hogy ilyen felhaszn´al´o egy´altal´an van. M´asr´eszt ha valaki egy az egyben a saj´at kulcsait ´ep´ıten´e egy kal´oz dek´oderbe, akkor feltehet˝oen nem is rendelkezne el´eg intelligenci´aval egy ilyen dek´oder meg´ep´ıt´es´ehez. Egy picit finom´ıtani kell teh´at a k = 1 esetben ismertetett elj´ar´ason. Minden i-re meg tudjuk hat´arozni, hogy mely j´at´ekosok rendelkeznek az fi kulccsal. Ezek lesznek a gyan´ us´ıtottak, ˝ok ´eppen a h−1 al´ok. A i (fi )-beli felhaszn´ dek´oder i. kulcsa kiz´ar´olag t˝ol¨ uk sz´armazhatott, valamelyik¨ uk biztosan b˝ un¨os. Ezeknek a felhaszn´al´oknak adjunk egy-egy fekete pontot. Mindegyik fi -nek megfelel˝oen osszuk ki a fekete pontokat. Ha k´eszen vagyunk, ¨osszes´ıts¨ unk! Azt a j´at´ekost ki´altsuk ki ´arul´onak, akinek a legt¨obb legt¨obb fekete pontja gy˝ ult ¨ossze! ´ ıt´ 4.4. All´ as. Legyen  pozit´ıv val´ os sz´ am. Ha az l ´ert´ek´et 4 log(n/)-nak v´ alasztjuk, akkor annak a val´osz´ın˝ us´ege, hogy a megjel¨ olt felhaszn´ al´ o´ artatlan, legfeljebb .

45

Bizony´ıt´ as. Jel¨olj¨ uk C-vel a kal´oz dek´odert k´esz´ıt˝o koal´ıci´ot (C = {u, v}), w pedig legyen egy ´artatlan felhaszn´al´o: w ∈ / C. Azt kell teh´at bel´atnunk, hogy Prob[ a nyomoz´as sor´an w-t gyan´ us´ıtjuk ] ≤ /n Ebb˝ol m´ar ad´odik (mivel kevesebb, mint n ´artatlan felhaszn´al´o van), hogy Prob[ a nyomoz´as sor´an ´artatlan szem´elyt gyan´ us´ıtunk ] ≤  Mivel a dek´odert legfeljebb k´et j´at´ekos k´esz´ıtette, ´es abban l kulcs van, ez´ert valamelyik j´at´ekos legal´abb l/2 kulccsal gazdag´ıtotta a dek´odert. Ez a j´at´ekos a nyomoz´o algoritmus fut´asa alatt legal´abb l/2 fekete pontot kap. A c´elunk az, hogy bel´assuk: eleny´esz˝o annak az es´elye, hogy egy ´artatlan felhaszn´al´onak l/2 fekete pontot adunk. Arr´ol van teh´at sz´o, hogy nagyon pici val´osz´ın˝ us´eggel lesz egy ´artatlan felhaszn´al´onak a sorok fel´eben k¨oz¨os kulcsa b´armely k´et j´at´ekossal. ´Igy nagy val´osz´ın˝ us´eggel semelyik k´et j´at´ekos nem tud egy ´artatlant gyan´ uba keverni. A lehet˝os´eg azonban nem z´arhat´o ki, mivel a kulcsokat v´eletlenszer˝ uen osztjuk ki. Ahogy n¨ovelj¨ uk a kulcsok sz´am´at, azaz l-et, u ´gy cs¨okken az ilyen v´eletlen egybees´esek lehet˝os´ege. Becs¨ ulj¨ uk meg l ´ert´ek´et! Jel¨olj¨ uk wi -vel a w ´artatlan j´at´ekos i. kulcs´at. A hi hash f¨ uggv´enyt v´eletlen¨ ul v´alasztottuk, teh´at wi -re gondolhatunk u ´gy, mintha egyenletes eloszl´as szerint v´alasztottuk volna az Ai -b˝ol. Ugyanez elmondhat´o az ui = hi (u) ´es a vi = hi (v) kulcsokra is. Annak a val´osz´ın˝ us´ege, hogy wi egybeesik fi -vel ´eppen 1/8, hiszen Ai -ben 8 kulcs van. Most becs¨ ulj¨ uk meg annak a val´osz´ın˝ us´eg´et, hogy w-t meggyan´ us´ıtja az algoritmus. Prob[ w-t meggyan´ us´ıtjuk ] =  = Prob[ w kulcsai legal´abb l/2 sorban egybeesnek fi -vel ] ≤ Azt szeretn´enk, ha ez a val´osz´ın˝ us´eg legfeljebb /n lenne:    l/2  l 1 ≤ . 8 n l/2     ea b a Felhaszn´alva az ≤ egyenl˝otlens´eget ad´odik, hogy b b  l/2 4 n ≥ , e  amib˝ol m´ar l´atszik, hogy az l = 4 log(n/) v´alaszt´as j´o.

46

  l/2 l 1 8 l/2

Ebb˝ol a bizony´ıt´asb´ol nem der¨ ult ki, hogy mi´ert ´epp 8 oszlopa van a kulcsm´atrixnak. Az egyik ok az, hogy ezzel a v´alaszt´assal k¨onnyen lehetett sz´amolni, ´es a nyert (4/e)l/2 ≥ n/ egyenl˝otlens´eg is megoldhat´o. Az igazi ok azonban az, hogy ´ıgy k¨onny˝ u megfelel˝o hi hash f¨ uggv´enyeket tal´alni. Ezt a k¨ovetkez˝o r´eszben l´atjuk be. Miel˝ott azonban r´at´ern´enk az ´altal´anos esetre, foglaljuk ¨ossze a k = 2 esetre vonatkoz´o eredm´enyeinket a k¨ovetkez˝o t´etelben. 4.5. T´ etel. Tetsz˝oleges  pozit´ıv sz´ amhoz l´etezik olyan (, 2)-biztos titkos nyomoz´ o s´ema, amelyben egy felhaszn´al´onak ¨ osszesen 4 log(n/) kulcsot kell t´ arolnia, egy u ¨zenetblokk visszafejt´es´ehez 4 log(n/) + 1 m˝ uveletre van sz¨ uks´eg, ´es egy enged´elyez˝ o blokk 32 log(n/) titkos´ıtott kulcsot tartalmaz.

4.7.

Tetsz˝ oleges m´ eret˝ u koal´ıci´ ok

Itt tulajdonk´eppen a k = 2 esetet ´altal´anos´ıtjuk, teh´at csak annyit tudunk, hogy k ≤ n. Az A m´atrixnak 4k oszlopa lesz, ´es u ´jfent l-lel jel¨olj¨ uk a sorok sz´am´at. Vezess¨ uk be az Ai = {ai,1 , ai,2 , . . . , ai,4k } jel¨ol´est, amellyel az A m´atrix i. sor´ara hivatkozunk. Minden felhaszn´al´onak l kulcsa lesz, minden Ai -b˝ol pontosan egy. Azt, hogy egy felhaszn´al´o melyik kulcsot kapja Ai -b˝ol, v´eletlenszer˝ uen d¨onts¨ uk el. Ennek ´erdek´eben minden sorhoz v´alasszunk v´eletlenszer˝ uen ´es f¨ uggetlen¨ ul egy-egy hash f¨ uggv´enyt: h1 , h2 , . . . , hl . Az i. sor hash f¨ uggv´enye minden felhaszn´al´ohoz v´alaszt egy v´eletlen kulcsot az adott sor 4k elem´eb˝ol: hi : {1, 2, . . . , n} → Ai . A hash f¨ uggv´enyeket a felhaszn´al´ok nem ismerik, ez a s´ema is titkos. ´Igy nem ¨ tudhatj´ak, hogy ki melyik kulcsokat kapta a kulcsm´atrixb´ol. Osszefoglalva, a kulcskioszt´as a k¨ovetkez˝o: P (u) = (h1 (u), h2 (u), . . . , hl (u)) . Rejtjelez˝ o s´ ema A titkos´ıt´o ´es enged´elyez˝o blokk ¨ossze´all´ıt´asa pontosan ugyan´ ugy zajlik, mint ahogy azt kor´abban l´attuk. A szolg´altat´o egy r ∈ {0, 1}s v´eletlen kulccsal rejtjelezi az adatot: ez lesz a titkos´ıt´o blokk. Majd v´alaszt l darab v´eletlen ri -t u ´gy, hogy az r 1 ⊕ r2 ⊕ . . . ⊕ rl = r teljes¨ ulj¨on. Az ri darabot rejtjelezi az Ai ¨osszes kulcs´aval (1 ≤ i ≤ l) : ei,1 = ri ⊕ ai,1 ei,2 = ri ⊕ ai,2 .. . ei,4k = ri ⊕ ai,4k 47

´Igy ¨ossze´all az (ei,j ) enged´elyez˝o blokk (1 ≤ i ≤ l , 1 ≤ j ≤ 4k), ami a titkos´ıt´o blokk el´e ker¨ ul. K¨onnyen meggondolhat´o, hogy ez a s´ema is m˝ uk¨od˝ok´epes, vagyis egy jogos felhaszn´al´o vissza tudja fejteni a titkos´ıt´o blokkba rejtett u ¨zenetet. Az u j´at´ekosnak minden Ai -b˝ol van egy hi (u) kulcsa. Ezt a kulcsot bitenk´ent hozz´aadva az enged´elyez˝o blokk i. sor´anak megfelel˝o elem´ehez megkaphat´o ri . Ha mindegyik ri -t ismerj¨ uk, akkor r is k¨onnyen sz´amolhat´o, ´es az r kulccsal m´ar visszafejthet˝o a titkos´ıt´o blokkban tal´alhat´o rejtjelezett adat. Param´ eterek L´athat´o, hogy egy felhaszn´al´o a m´atrix minden sor´ab´ol egy kulcsot kap, teh´at ¨osszesen l kulcsot kell t´arolnia. A kommunik´aci´os t¨obblet, ami az enged´elyez˝o blokk m´eret´evel egyezik meg: 4 k l. Egy blokk visszafejt´es´ehez l +1 m˝ uveletre van sz¨ uks´eg. Nyomoz´ o s´ ema A kor´abbi esetekhez hasonl´oan most is elmondhat´o, hogy egy kal´oz dek´odernek rendelkeznie kell legal´abb egy kulccsal minden sorb´ol. A kulcsokat pont ugyan´ ugy lehet kinyerni a dek´oderb˝ol, mint azt a k = 2 esetben l´attuk. Legyen F a kinyert kulcsok halmaza, ´es fi a dek´oder i. kulcsa: fi = F ∩ Ai . A ´arul´onak ism´et azt ki´altsuk ki, aki a legt¨obb fi kulccsal rendelkezik. ´ ıt´ 4.6. All´ as. Legyen  pozit´ıv sz´ am. Ha az l param´eter ´ert´ek´et u ´gy v´ alasztjuk meg, hogy l > 4k/3 log(n/) legyen, akkor a megjel¨ olt felhaszn´ al´ o legfeljebb  es´ellyel lesz artatlan. ´ Bizony´ıt´ as. Jel¨olj¨ uk C-vel a kal´oz dek´odert k´esz´ıt˝o koal´ıci´ot, w pedig legyen egy ´artatlan felhaszn´al´o: w ∈ / C. Azt kell bel´atnunk, hogy Prob[ a nyomoz´as sor´an w-t gyan´ us´ıtjuk meg ] ≤ /n . Mivel kevesebb, mint n ´artatlan felhaszn´al´o van, ez´ert ebb˝ol ad´odik, hogy Prob[ a nyomoz´as sor´an ´artatlan szem´elyt gyan´ us´ıtunk meg ] ≤  Mivel a dek´odert legfeljebb k j´at´ekos k´esz´ıtette, ´es abban l kulcs van, ez´ert valamelyik j´at´ekos legal´abb l/k kulccsal gazdag´ıtotta a dek´odert. Ez a j´at´ekos a nyomoz´o algoritmus fut´asa alatt legal´abb l/k fekete pontot kap. A c´elunk az, hogy bel´assuk: eleny´esz˝o annak az es´elye, hogy egy ´artatlan felhaszn´al´onak l/k fekete pontot adunk. Ehhez az kell, hogy egy ´artatlan felhaszn´al´onak csak kis val´osz´ın˝ us´eggel legyen a so´ rok k-ad r´esz´eben k¨oz¨os kulcsa b´armelyik C koal´ıci´oval. Igy nagy val´osz´ın˝ us´eggel semelyik k j´at´ekos nem tud egy ´artatlant gyan´ uba keverni. 48

´ Ujfent jel¨olj¨ uk wi -vel a w j´at´ekos i. kulcs´at. Annak a val´osz´ın˝ us´ege, hogy wi egybeesik fi -vel ´eppen 1/4k, hiszen Ai -ben 4k kulcs van. i = 1, . . . , l-re legyen ξi olyan 0-1 val´osz´ın˝ Puls´egi v´altoz´o, amely pontosan akkor 1, ha wi = fi . Az ¨osszes kulcsot tekintve i=1 ξi egyez´es van. Ennek a v´arhat´o ´ert´eke l/4k. Szeretn´enk fel¨ ulr˝ol becs¨ ulni annak a val´osz´ın˝ us´eg´et, hogy w enn´el a v´arhat´o ´ert´ekn´el t¨obb fekete pontot kap. A k¨ovetkez˝o egyenl˝otlens´eg-l´anc utols´o el˝otti l´ep´es´en´el felhaszn´aljuk Chernoff-korl´at m´asodik v´altozat´at (2.3. T´etel) a = 4, illetve q = 1/4k helyettes´ıt´essel. Itt az a = 4 helyettes´ıt´es matematikai jelent´ese az, hogy a v´arhat´o ´ert´ek n´egyszerese lesz a k¨oz¨os kulcsok sz´ama. Prob[ w-t b˝ un¨osnek tal´aljuk ] ≤ Prob[ w legal´abb l/k fekete pontot kap ] = = Prob[ w kulcsai legal´abb l/k esetben egyeznek a dek´oder kulcsaival ] = # " # " l  3 l/4k l X 1X 1 e l = Prob ξi ≥ 4 < < 2−3l/4k , Prob ξi ≥ 4 k l 4k 4 i=1 i=1 ahol a legutols´o egyenl˝otlens´eg abb´ol k¨ovetkezik, hogy e3 < 25 . Ha azt szeretn´enk, hogy a nyomoz´o algoritmus legfeljebb n/ es´ellyel gyan´ us´ıtsa meg w-t, akkor l-et u ´gy kell megv´alasztani, hogy a 2−3l/4k ≤ /n egyenl˝otlens´eg teljes¨ ulj¨on. Innen ad´odik, hogy l > 4k/3 log(n/). Ekkor b´armely k´et tag´ u koal´ıci´ora igaz, hogy legfeljebb  es´ellyel tudja elterelni mag´ar´ol a gyan´ ut. A nyomoz´o s´em´akkal kapcsolatos vizsg´al´od´asunk legf˝obb eredm´eny´et mondjuk ki a k¨ovetkez˝o t´etelben. 4.7. T´ etel. Ha  pozit´ıv sz´am, akkor l´etezik olyan (, k)-biztos titkos nyomoz´ o s´ema, amelyben egy felhaszn´al´onak ¨osszesen 4k/3 log(n/) kulcsot kell t´ arolnia, egy u ¨zenetblokk visszafejt´es´ehez 4k/3 log(n/) + 1 m˝ uveletre van sz¨ uks´eg, ´es egy enged´elyez˝ o 2 blokk 16k /3 log(n/) titkos´ıtott kulcsot tartalmaz.

4.8.

T¨ obb kulcsos dek´ oderek

A fent bemutatott eredm´enyek arra a felt´etelez´esre ´ep¨ ulnek, hogy a dek´oder az A kulcsm´atrix minden sor´ab´ol egyetlen kulcsot tartalmaz. Ez a megszor´ıt´as sajnos egy´altal´an nem val´oszer˝ u: az ´arul´ok saj´at kedv¨ uk szerint d¨onthetik el, hogy egyegy sorba mely tagok kulcs´at, vagy kulcsait ´ep´ıtik be. K¨onnyen el˝ofordulhat, hogy soronk´ent t¨obb kulcsot is be´agyaznak, ´es a dek´oder valamilyen vez´erl´esi strat´egia 49

szerint d¨onti el, hogy egy adott sorban mikor melyik kulccsal fejt. Ebben az esetben bizony neh´ezkess´e v´alhat a kulcsok kinyer´ese. Sajnos az i. kulcs (fi ) meghat´aroz´asa nem megy egy l´ep´esben. Ha a kor´abban ismertetett m´odszerrel prob´aln´ank kinyerni a kulcsokat, akkor k´etf´elk´eppen is hib´azhatn´ank. Egyr´eszt el˝ofordulhat az, hogy a dek´oder ´epp akkor v´alt kulcsot az adott sorban, amikor mi kitakarjuk az addig haszn´alt kulcsot. ´Igy megeshet az, hogy nem vesz¨ unk ´eszre egy kulcsot, amelyet ismer a dek´oder. M´asr´eszt az is elk´epzelhet˝o, hogy egy kulcsr´ol u ´gy t˝ unik, hogy a dek´oder haszn´alja, holott az be sincs ´ep´ıtve. Ez u ´gy lehets´eges, hogy a dek´oder ´eppen akkor v´alt egy olyan kulcsra, amelyet m´ar kor´abban kitakartunk, amikor eggyel tov´abbl´eptetj¨ uk a kitakar´ast. A probl´ema u ´gy hidalhat´o ´at, hogy az i. sorhoz tartoz´o fi meghat´aroz´as´ahoz t¨obb k´ıs´erletet is elv´egz¨ unk. A nulladik k´ıs´erletsorozatban szab´alyos u ¨zenetcsomagokat k¨ uld¨ unk a dek´odernek. Ekkor a dek´oder 100%-osan fejt. Ennek megfelel˝oen legyen p0 = 1. A k¨ovetkez˝o l´ep´esben takarjuk ki az enged´elyez˝o blokk adott sor´anak els˝o elem´et. Az ´ıgy m´odos´ıtott adatcsomagokkal v´egezz¨ unk ,,sok” k´ıs´erletet, ´es jel¨olje p1 a dek´oder sikeres fejt´eseinek relat´ıv gyakoris´ag´at. Hasonl´oan a kor´abban l´atottakhoz, takarjunk ki egyre t¨obb kulcsot az enged´elyez˝o blokkb´ol, ´es mindig jegyezz¨ uk fel a pi relat´ıv gyakoris´agot. Ha az A m´atrix egy sor´aban t kulcs van, akkor ¨osszesen t + 1 darab p ´ert´ek¨ unk lesz. Tudjuk azt, hogy p0 = 1, ´es pt = 0, hiszen a ´ t. k´ıs´erletsorozatban a teljes i. sort kitakarjuk. Atlagosan teh´at 1/t-vel cs¨okken a pi -k ´ert´eke. Ha valamilyen j-re azt tapasztaljuk, hogy pj − pj+1 > 1/t, akkor meg´allap´ıthatjuk, hogy a dek´oder ebben a sorban ismeri a j. kulcsot. (A hiba lehet˝os´ege elm´eletileg ´ıgy sem z´arhat´o ki, ha egy sorban t¨obb kulcs is van. B´armennyi (v´eges sz´am´ u) k´ıs´erletet v´egz¨ unk is, mindig lesz olyan dek´oder-strat´egia, amivel f´elrevezethet˝ok lesz¨ unk.)

50

5.

Rejtjelezett m˝ usorsz´ or´ as

A nyomoz´o s´em´ak lehet˝ov´e tett´ek sz´amunkra azt, hogy felder´ıts¨ uk egy elfogott kal´oz dek´oder forr´as´at. Az ´arul´okat ´ıgy felel˝oss´egre vonhatjuk, az ´altaluk gy´artott kal´oz dek´oderek azonban zavartalanul m˝ uk¨odnek tov´abb. Az ujjlenyomat-k´odok ´es a nyomoz´o s´em´ak c´elja els˝osorban az, hogy elrettentse a felhaszn´al´okat az illeg´alis m´asol´ast´ol, illetve hogy bizony´ıt´ekokat szolg´altasson az ´arul´ok ellen, ha b´ır´os´agi t´argyal´asra ker¨ ul sor. Ezek a rendszerek teh´at ¨onmagukban nem k´epesek enyh´ıteni azt a k´art, amelyet a kal´oz dek´oderek terjeszt´ese okoz. R´eszben erre a probl´em´ara adnak megold´ast a Fiat ´es Naor ´altal bemutatott ad´ asrejtjelez˝ o s´em´ ak ([4]). Egy ilyen s´ema seg´ıts´eg´evel az adatszolg´altat´o dinamikusan tudja v´altoztatni azon felhaszn´al´ok halmaz´at, akik k´epesek fogni az ad´ast. Az ad´asrejtjelez´es seg´ıts´eg´evel el´erhet˝o az, hogy kiz´ar´olag egy T ⊆ U csoport tudja dek´odolni az ad´ast, a T -n k´ıv¨ uli felhaszn´al´ok nem. Az bemutat´asra ker¨ ul˝o s´em´ak ´ori´asi el˝onye az, hogy a T halmaz dinamikusan, n´eh´any speci´alis u ¨zenet lead´as´aval megv´altoztathat´o. Akt´ıv felhaszn´al´onak h´ıvjuk azt, aki az ´eppen enged´elyezett T halmazban van. Mindenki m´ast inakt´ıv felhaszn´al´onak nevez¨ unk. Ha az adatszolg´altat´o felfedez egy kal´oz dek´odert, akkor azon t´ ul, hogy jogi l´ep´eseket tesz az ´arul´ok ellen, lehet˝os´ege van letiltani a kal´oz dek´odert. Egyszer˝ uen ki kell iktatni az elfogott ´arul´okat az akt´ıv felhaszn´al´ok k¨or´eb˝ol. Egy ilyen rendszert term´eszetesen nem csak nyomoz´o s´em´ak mellett lehet haszn´alni. Egy ad´asrejtjelez˝o s´ema ¨onmag´aban is sok helyen alkalmazhat´o. Az egyik legterm´eszetesebben ad´od´o felhaszn´al´asi ter¨ uletet az olyan fizet˝os telev´ızi´ocsatorn´ak alkotj´ak, amelyekn´el minden film´ert k¨ ul¨on d´ıjat kell fizetni. (Az ilyen TV-ket az angol nyelv˝ u irodalomban pay per view TV -nek h´ıvj´ak.) Ha a szolg´altat´o ad´asrejtjelez˝o s´em´at haszn´al, akkor nincs m´as dolga, mint minden film el˝ott be´all´ıtani az akt´ıv vev˝ok halmaz´at aszerint, hogy ki fizetett el˝o az adott m˝ usorra. ´ Erdemes ilyen rendszereket alkalmazni akkor is, ha nem egy-egy m˝ usorsz´amra, hanem k¨ ul¨onb¨oz˝o csomagokra lehet el˝ofizetni. Ez esetben sokkal egyszer˝ ubb´e v´alhat egy-egy felhaszn´al´o csomag-v´alt´as´anak regisztr´al´asa, vagy roppant k¨onnyed´en le lehet tiltani valakit, ha jelent˝osebb tartoz´ast halmoz fel.

5.1.

K´ et trivi´ alis s´ ema

A kor´abbi fejezetekkel ¨osszhangban a rendszerben regisztr´alt felhaszn´al´ok halmaz´at U -val, sz´amukat pedig n-nel jel¨olj¨ uk. A nyomoz´o s´em´akhoz hasonl´oan most is egyegy dek´odert kap minden felhaszn´al´o. Az egyik nyilv´anval´o megold´as az, ha az U minden egyes r´eszhalmaz´ahoz hozz´arendel¨ unk egy egyedi kulcsot, amelyet mindenki megkap, aki tagja az adott r´eszhalmaznak. Az adatszolg´altat´onak nincs m´as dolga, mint az akt´ıv felhaszn´al´ok halmaz´ahoz rendelt kulccsal rejtjelezni az ad´ast. Ezt az ad´ast kiz´ar´olag az akt´ıv 51

j´at´ekosok tudj´ak visszafejteni, hiszen a rejtjelez´eshez haszn´alt kulcsot csak ˝ok ismerik. Ebben a s´em´aban minden felhaszn´al´onak 2n−1 darab kulcsot kell t´arolnia. Ezeket a kulcsokat a dek´oderekben kell t´arolni, ´ıgy fontos, hogy lehet˝oleg ne legyen ilyen sok bel˝ol¨ uk. L´etezik olyan megold´as is, amely a t´arig´eny szempontj´ab´ol sokkal hat´ekonyabb. Adjunk mindenkinek egyetlen kulcsot! Egy u ´j akt´ıv halmaz kijel¨ol´es´ehez el˝osz¨or v´alasztani kell egy v´eletlen kulcsot (amellyel az ad´as rejtjelez´ese zajlik majd). Ezt a k¨oz¨os kulcsot egyenk´ent k´odoljuk el az akt´ıv tagok kulcsaival, majd k¨ uldj¨ uk el egym´as ut´an ezeket a titkos´ıtott u ¨zeneteket. A k¨oz¨os kulcsot csak az akt´ıv tagok k´epesek visszafejteni, ´ıgy a tov´abbi ad´ast (a filmet) ezzel rejtjelezhetj¨ uk. L´athat´o, hogy az els˝o megold´ashoz k´epest a kulcsok sz´ama drasztikusan cs¨okkent (2n−1 helyett 1 kulcs/f˝o), m´ıg az akt´ıv halmazt kijel¨ol˝o u ¨zenetek sz´ama jelent˝osen megn˝ott (0 helyett annyi, ah´any akt´ıv felhaszn´al´o van). A k¨ovetkez˝okben olyan s´em´akat mutatunk be, amelyek elfogadhat´o egyens´ ulyt teremtenek e k´et param´eter k¨oz¨ott.

5.2.

A s´ ema fel´ ep´ıt´ ese

Az ad´asrejtjelez˝o rendszerek n´egy egys´egb˝ol ´ep¨ ulnek fel. Ezek egy¨ uttesen biztos´ıtj´ak azt, hogy a s´ema u ´gy m˝ uk¨odj¨on, ahogy azt elv´arjuk. • Inicializ´al´as: ak´arcsak a nyomoz´o s´em´ak eset´eben, a szolg´altat´onak mindenek el˝ott el kell k´esz´ıtenie a dek´odereket, amelyek k´es˝obb a felhaszn´al´okhoz ker¨ ulnek. Minden dek´oderben m´as kulcsok vannak elhelyezve. • Halmazkijel¨ol´es: ez a l´ep´es az akt´ıv halmaz l´etrehoz´as´anak els˝o f´azisa. A szolg´altat´onak le kell adnia egy u ¨zenetet, amely minden felhaszn´al´oval tudatja, hogy melyik az u ´j akt´ıv halmaz. Ez egy ny´ılt u ¨zenet, amely legrosszabb esetben n bites. Reprezent´aci´ot´ol f¨ ugg˝oen megoldhat´o kevesebb bittel is. (P´eld´aul t¨om¨or´ıt´essel: kihaszn´alva azt, hogy bizonyos halmazok ritk´abban, m´asok viszont s˝ ur˝ un ker¨ ulnek akt´ıv szerepk¨orbe.) A halmazkijel¨ol´essel nem foglalkozunk, mert ez minden esetben egyetlen u ¨zenetet jelent, amelynek a hossza er˝osen f¨ ugg az ´abr´azol´ast´ol. • Akt´ıv kulcs kioszt´asa: az akt´ıv halmaz l´etrehoz´as´anak m´asodik f´azisa, ´es egyben az ad´asrejtjelez˝o s´em´ak legl´enyegesebb pontja. Ez a komponens ´ırja le, hogy a halmazkijel¨ol˝o u ¨zenet sz´or´asa ut´an milyen tov´abbi u ¨zenetek sug´arz´as´ara van m´eg sz¨ uks´eg ahhoz, hogy a kijel¨olt akt´ıv halmaz minden tagja el tudja k´esz´ıteni az akt´ıv kulcsot. • Rejtjelez´es: miut´an minden akt´ıv felhaszn´al´o birtok´aban van a k¨oz¨os kulcsnak, ezzel a kulccsal (´es valamilyen szimmetrikus kulcs´ u rejtjelez˝o rendszerrel) elkezd˝odhet a t´enyleges adatok rejtjelez´ese ´es tov´abb´ıt´asa. 52

A bemutatott s´em´ak hat´ekonys´ag´at k´et param´eterrel m´erhetj¨ uk. Az egyik a dek´oderekben t´arolt kulcsok sz´ama. Minden esetben abb´ol a feltev´esb˝ol indulunk ki, hogy a szimmetrikus k´odol´o algoritmus s hossz´ u kulcsot haszn´al. (s egy biztons´agi param´eter.) A rendszerben el˝ofordul´o ¨osszes kulcs hossza s, ´ıgy elegend˝o azt vizsg´alni, hogy h´any darab kulcs van egy-egy dek´oderben. A m´asik fontos t´enyez˝o az akt´ıv kulcs l´etrehoz´as´ahoz sz¨ uks´eges u ¨zenetek sz´ama. Ha ez az ´ert´ek nagyon nagy, akkor el˝ofordulhat az, hogy k´et film k¨oz´e j´okora sz¨ unetet kell beiktatni, am´ıg az akt´ıv dek´oderek u ´jra tudj´ak gener´alni az u ´j akt´ıv kulcsot.

     

 

e D D  D  D  

     

' $

 

u1

 XXXX  XXX XXX z X

u2 . . .

akt´ ıv j´ at´ ekosok

ut

D D

& % D D

ut+1 . . .

D D D D

inakt´ ıv j´ at´ ekosok

un

adatszolg´ altat´ o

5.11. ´ abra. A rendszer m˝ uk¨od´es´enek v´azlata

5.3.

Defin´ıci´ ok

5.1. Defin´ıci´ o. Legyen C ⊆ U egy tetsz˝ oleges koal´ıci´ o! Azt mondjuk, hogy egy ad´ asrejtjelez˝o s´ema v´edett a C koal´ıci´ oval szemben, ha tetsz˝ oleges T ⊆ U \ C akt´ıv halmaz eset´en a C koal´ıci´o nem tudja el˝ o´ all´ıtani az akt´ıv kulcsot a rendszerben leadott u ¨zenetek alapj´an. ´ Altal´ aban sz¨ uks´egtelen az ¨osszes lehets´eges felhaszn´al´oi csoport ellen v´edekezni. A s´em´ak hat´ekonys´aga drasztikusan javulhat, ha csak a legfeljebb k m´eret˝ u koal´ıci´ok ellen tessz¨ uk ellen´all´ov´a a rendszert. 5.2. Defin´ıci´ o. Azt mondjuk, hogy egy ad´ asrejtjelez˝ o s´ema k-biztos, ha b´ armely legfeljebb k m´eret˝ u koal´ıci´o ellen v´edett. 53

Tov´abb n¨ovelhet˝o a hat´ekonys´ag, ha egy s´em´at u ´gy tervez¨ unk meg, hogy az csak v´eletlen koal´ıci´okkal szemben legyen v´edett. Egy ilyen s´ema eset´eben lehetnek olyan k tag´ u koal´ıci´ok, amelyek fel tudj´ak t¨orni a rendszert, de egy v´eletlen ¨osszet´etel˝ u koal´ıci´o nagy val´osz´ın˝ us´eggel tov´abbra sem tudja megszerezni az akt´ıv kulcsot. Ezek a s´em´ak a gyakorlatban ugyanolyan j´ol haszn´alhat´ok, mint a k-biztos t´arsaik. 5.3. Defin´ıci´ o. Egy ad´asrejtjelez˝ o s´em´ ar´ ol azt mondjuk, hogy (, k)-biztos, ha egy egyenletes eloszl´as szerint v´eletlen¨ ul v´ alasztott k tag´ u koal´ıci´ o ellen legal´ abb 1 −  es´ellyel v´edett. Ez ut´obbi defin´ıci´o illusztr´al´as´ara n´ezz¨ unk egy p´eld´at. Tegy¨ uk fel, hogy van egy (0, 001, 500)-biztos s´em´ank. Ha valaki elhat´arozza, hogy vesz 500 dek´odert, ´es megpr´ob´alja felt¨orni a s´em´at, akkor 99, 9%, hogy a k´ıs´erlet kudarcba fullad. Ugyanis a dek´odereket nem ˝o v´alasztja, hanem az adatszolg´altat´o osztja sz´et. A szolg´altat´o pedig megteheti, hogy v´eletlen sorrendben adja ki a dek´odereket.

5.4.

N´ eh´ any z´ er´ o-¨ uzenet s´ ema

Az els˝o s´em´aink u ´gynevezett z´er´ o-¨ uzenet s´em´ ak. Ezekben egy´altal´an nincs sz¨ uks´eg a halmazkijel¨ol˝o u ¨zeneten t´ ul tov´abbi u ¨zenetre ahhoz, hogy az akt´ıv kulcs az akt´ıv felhaszn´al´ok birtok´aba ker¨ ulj¨on. Teh´at az akt´ıv halmaz l´etrehoz´as´anak m´asodik f´azisa elmarad: csup´an abb´ol az inform´aci´ob´ol, hogy melyik az akt´ıv halmaz, minden akt´ıv tag tudni fogja a k¨oz¨os kulcsot. Ha visszagondolunk, az els˝o trivi´alis s´em´ank is ilyen volt. Ebben a r´eszben h´arom k¨ ul¨onb¨oz˝o 1-biztos s´em´at defini´alunk. A h´arom s´ema nagyon k¨ ul¨onb¨oz˝o hat´ekonys´ag´ u lesz aszerint, hogy milyen er˝os felt´etelekb˝ol indulunk ki. Az els˝o s´ema m˝ uk¨od´es´ehez semmilyen el˝ofelt´etel nem sz¨ uks´eges, ´es l´atni fogjuk, hogy k¨onnyen ´altal´anos´ıthat´o, hogy nagyobb k-ra is k-biztos legyen. A m´asodik s´ema m˝ uk¨od´ese azon a feltev´esen alapszik, hogy l´etezik egyir´any´ u f¨ uggv´eny, a harmadik pedig abb´ol indul ki, hogy az ¨osszetett modulus szerinti gy¨okvon´as nehezen elv´egezhet˝o feladat. Az al´abbiakban ismertetett s´em´ak jelent˝os´ege az, hogy a k´es˝obbiekben ezekb˝ol ´ep´ıtkezve fogunk egy nagyobb koal´ıci´ok ellen is v´edett rendszert ´ep´ıteni. 5.4.1.

Egy kombinatorikus konstrukci´ o

Az al´abbi s´ema ¨otlete a k¨ovetkez˝o. Rendelj¨ unk minden felhaszn´al´ohoz egy-egy kulcsot. Az u j´at´ekos kulcs´anak – kiss´e meglep˝o m´odon – nem az funkci´oja, hogy ´ enged´elyezze a dek´odol´ast u sz´am´ara. Epp ellenkez˝oleg: ez a kulcs teszi majd lehet˝ov´e, hogy letiltsuk u-t. Ez persze azt is jelenti, hogy u nem ismerheti a saj´at kulcs´at. 54

5.4. T´ etel. L´etezik olyan 1-biztos s´ema, amelyben minden felhaszn´ al´ onak n kulcsa van, ´es nincs sz¨ uks´eg k¨ ul¨on u ¨zenetre az akt´ıv kulcs gener´ al´ as´ ahoz. Bizony´ıt´ as. Rendelj¨ unk minden ui ∈ U felhaszn´al´ohoz egy v´eletlen ri ∈ {0, 1}s kulcsot, ´es hasonl´oan v´alasszunk egy n + 1-dik r0 kulcsot is. A kulcsok halmaz´at jel¨olj¨ uk R-rel: R = {r0 , r1 , . . . , rn } . Az ui j´at´ekos kapja meg az ¨osszes R \ {ri }-beli kulcsot. Ha ´ıgy j´arunk el az inicializ´al´as sor´an, akkor egy 1-biztos z´er´o-¨ uzenet s´em´at nyer¨ unk. Tegy¨ uk fel, hogy ki szeretn´enk jel¨olni a T -t akt´ıv halmaznak. Miut´an leadtuk a halmazkijel¨ol˝o u ¨zenetet, T ¨osszes tagja tudni fogja, hogy mely felhaszn´al´ok nem tagjai T -nek. Ezen felhaszn´al´ok kulcsait az ¨osszes T -beli j´at´ekos ismeri. A kT akt´ıv kulcs legyen az U \ T -beli felhaszn´al´ok kulcsainak bitenk´enti mod 2 ¨osszege. Vil´agos, hogy ezt minden akt´ıv j´at´ekos el tudja k´esz´ıteni. Rajtuk k´ıv¨ ul viszont senki, mivel egy inakt´ıv j´at´ekos sem ismeri a saj´at kulcs´at, amely viszont sz¨ uks´eges kT el˝oa´ll´ıt´as´ahoz. Megjegyezz¨ uk, hogy az r0 kulcs n´elk¨ ul lehetetlen lenne egyszerre az ¨osszes felhaszn´al´onak sug´arozni. Az r0 -t ´ıgy tekinthetj¨ uk az ,,¨ ures koal´ıci´o” kulcs´anak. (Minden adatszolg´altat´o ´alma egy ilyen u ¨res koal´ıci´o.)

Ez a s´ema k¨onnyen k-biztoss´a ,,duzzaszthat´o”. A felhaszn´al´okb´ol ´all´o egyelem˝ u halmazok mellett figyelembe kell venn¨ unk az ¨osszes legfeljebb k elem˝ u C r´eszhalmaz´at U -nak. Az ¨osszes ilyen halmazhoz rendel¨ unk egy v´eletlen kC ∈ {0, 1}s kulcsot, amit azt´an minden U \ C-beli j´at´ekos megkap. Egy kijel¨olt T halmaz k¨oz¨os kT kulcsa u ´gy k´epezhet˝o, hogy az ¨osszes legfeljebb k m´eret˝ u C ⊆ U \ T koal´ıci´ohoz tartoz´o kC kulcsot ¨osszeadjuk. K¨onnyen v´egiggondolhat´o, hogy kT -t ´eppen az akt´ıv felhaszn´al´ok tudj´ak kisz´amolni. Egy u felhaszn´al´onak annyi kulcsa lesz, ah´any legfeljebb k elem˝ u r´eszhalmaza van U \ {u}-nak, ami ´eppen  k  X n−1 i=0

i

.

Ezt az eredm´enyt foglaljuk ¨ossze a k¨ovetkez˝o t´etelben. 5.5. T´ etel. Tetsz˝oleges
ıv eg´eszhez l´etezik olyan k-biztos s´ema, amelyben minP k pozit´ den felhaszn´al´onak ki=0 n−1 kulcsa van, ´es nincs sz¨ uks´eg k¨ ul¨ on u ¨zenetre az akt´ıv i kulcs gener´al´as´ahoz.

55

5.4.2.

Egyir´ any´ u f¨ uggv´ enyekre ´ ep¨ ul˝ o konstrukci´ o

Ha feltessz¨ uk, hogy l´etezik egyir´any´ u f¨ uggv´eny, akkor az el˝oz˝on´el j´oval hat´ekonyabb s´em´at tudunk k´esz´ıteni: n helyett el´eg log n kulcsot t´arolnia egy-egy felhaszn´al´onak. 5.6. T´ etel. Ha l´etezik egyir´any´ u f¨ uggv´eny, akkor konstru´ alhat´ o olyan 1-biztos s´ema, amelyben minden felhaszn´al´onak log n darab kulcsot kell t´ arolnia, ´es nincs sz¨ uks´eg k¨ ul¨ on u ¨zenetre az akt´ıv kulcs gener´ al´ as´ ahoz. Bizony´ıt´ as. Tegy¨ uk fel, hogy l´etezik egyir´any´ u f¨ uggv´eny. A 2.1. T´etel alapj´an tudjuk, hogy ekkor l´etezik pszeudorandom gener´ator is. Legyen f : {0, 1}s → {0, 1}2s egy pszeudorandom gener´ator. ´ ıts¨ Ep´ unk fel egy log n m´elys´eg˝ u bin´aris f´at, ´es l´assuk el minden cs´ ucs´at rekurz´ıv m´odon egy-egy s hossz´ u bin´aris c´ımk´evel. V´alasszunk egy v´eletlen a ∈ {0, 1}s bitsorozatot, ´es legyen ez a fa gy¨oker´enek a c´ımk´eje. Alkalmazzuk f -et erre az ´ert´ekre: f (a) ´eppen 2s hossz´ u. A gy¨ok´er baloldali gyerek´et c´ımk´ezz¨ uk meg f (a) els˝o s bitj´evel, a jobboldalit pedig a m´asodik s-sel. Ezt a m˝ uveletet rekurz´ıvan folytatva az ¨osszes cs´ ucs megc´ımk´ezhet˝o eg´eszen a levelekig.

a f

@ @ R @

  f A AAU  



@ R @




HH f HH

j H

@ R @



@ R @



@ R @

. . .

u1

@ R @

u2



...

un−1

@ R @

un

5.12. ´ abra. A fel´ep´ıtett bin´aris fa

Azonos´ıtsuk az n levelet a felhaszn´al´okkal, ´es minden felhaszn´al´ohoz rendelj¨ uk hozz´a a neki megfelel˝o lev´el c´ımk´ej´et, mint kulcsot. Az el˝oz˝o s´ema ¨otlet´ere ´ep´ıtve 56

most is azt szeretn´enk, hogy egy ui j´at´ekos rendelkezzen az ¨osszes kulccsal, kiv´eve a saj´atj´at. Ahelyett azonban, hogy magukat a kulcsokat adn´ank oda ui -nek, bizonyos magasabb szinten lev˝o c´ımk´eket adunk, a k¨ovetkez˝o elv szerint. T¨or¨olj¨ uk ki az ui -t˝ol a gy¨ok´erbe vezet˝o utat! ´Igy a f´ank sz´etesik log n darab bin´aris f´ara. (Az ui cs´ ucsot is let¨or¨olj¨ uk.) Ezek a bin´aris f´ak mind olyanok, hogy a gy¨ok´ernek csak egyetlen gyereke van. Nevezz¨ uk ezeket az egyk´eket algy¨ok´ernek. Az ui kulcsai legyenek az algy¨okerek c´ımk´ei. Az 5.13. ´abr´an l´athat´o, amint az ui j´at´ekos kulcs´at gener´aljuk. Az algy¨okereket sat´ıroz´assal jel¨olt¨ uk. Mivel az f f¨ uggv´enyt be´ep´ıtj¨ uk a j´at´ekosok dek´oder´ebe, ez´ert igaz lesz az, hogy mindenki ismeri az ¨osszes t¨obbi j´at´ekos kulcs´at. B´armelyik felhaszn´al´o maga fel tudja ´ep´ıteni a log n darab bin´aris f´at az f ´es az algy¨okerek ismeret´eben. ´Igy az ui lev´el kiv´etel´evel az eredeti bin´aris fa gy¨okereihez rendelt c´ımk´eket is ki tudja sz´amolni. N´ezz¨ uk, mi t¨ort´enne, ha egy ui j´at´ekos valahogy m´egis ki tudn´a sz´am´ıtani a saj´at kulcs´at. Azt ´all´ıtjuk, hogy ebben az esetben az f f¨ uggv´eny nem lenne pszeudorandom. ´ ıt´ 5.7. All´ as. Ha a kulcskioszt´ast a fent le´ırtak szerint v´egezz¨ uk, akkor semelyik ui j´ at´ekos nem tudja kital´alni a saj´at ri kulcs´ at. Bizony´ıt´ as. Jel¨olj¨ uk t1 , t2 , . . . , tlog n -nel az ui kulcsait. Indirekt m´odon tegy¨ uk fel, hogy ui ezekb˝ol a t ´ert´ekekb˝ol (az f f¨ uggv´eny ismeret´eben) valamilyen p0 nem elhanyagolhat´o val´osz´ın˝ us´eggel k´epes el˝o´all´ıtani a saj´at ri kulcs´at. Jel¨olj¨ uk Z-vel az ui ´altal alkalmazott visszafejt˝o algoritmust. V´egezz¨ unk k´ıs´erleteket a k¨ovetkez˝o m´odon. Minden k´ıs´erletben hajtsuk v´egre u ´jfent az inicializ´al´ast, azaz osszuk ki u ´jra a kulcsokat. Az els˝o k´ıs´erletben az ui -nek sz´ant t1 , t2 , . . . , tlog n kulcsok k¨oz¨ ul az els˝o (t1 ) helyett egy val´odi v´eletlen {0, 1}s -beli sz´ot adjunk ui -nek. Vizsg´aljuk meg, hogy az ´ıgy kiosztott kulcsokkal a Z algoritmus milyen es´ellyel fejti meg ri -t. Ezt a val´osz´ın˝ us´eget jel¨olj¨ uk p1 -gyel. Folytassuk a k´ıs´erletez´est u ´gy, hogy a j. k´ıs´erletben a t1 , . . . , tj ´ert´ekek helyett v´eletlen bitsorozatokat adunk ui -nek (2 ≤ j ≤ log n). A j. k´ıs´erlet sor´an jel¨olj¨ uk pj -vel annak az es´ely´et, hogy Z el˝o tudja ´all´ıtani ri -t. A p log n ´ert´ek nyilv´anval´oan elhanyagolhat´o, hiszen a log n-dik k´ıs´erletben az ui -nek adott ¨ osszes ´ert´eket lecser´elt¨ uk egy-egy val´odi v´eletlen bitsorozatra. Mivel az indirekt feltev´es szerint a kezdeti p0 ´ert´ek nem elhanyagolhat´o, a v´egs˝o p log n ´ert´ek viszont az, ez´ert lennie kell egy olyan 2 ≤ d ≤ log n indexnek, amelyre a pd−1 − pd k¨ ul¨onbs´eg nem elhanyagolhat´o. Ez azt jelenti, hogy a Z visszafejt˝o algoritmus abban a pillanatban ,,elromlik”, ha a td pszeudorandom sz´am helyett egy val´odi v´eletlen inputot kap. Vagyis Z k¨ ul¨onbs´eget tud tenni td ´es egy val´odi v´eletlen k¨oz¨ott. Ez pedig ellentmond annak, hogy az f f¨ uggv´eny pszeudorandom.

57

a  H  HH   HH  H

 

HH j

 HH HH j

 HH HH j

 

 

 HH   j H

 HH   j H

 HH   j H

 HH   j H

ui

a 

 

  

 H  HH   H j  H  H   j H

H

HH j H

 H  H   j H

   

 H  H   j H

5.13. ´ abra. Az ui j´at´ekos kulcsai, az algy¨okerek

58

Mindebb˝ol l´athat´o, hogy alkalmazhat´o az 5.4. T´etel konstrukci´oja. Az akt´ıv kulcs ´eppen az inakt´ıv j´at´ekosok kulcsainak mod 2 ¨osszege. ´Igy ´eppen az inakt´ıv j´at´ekos nem ismerhetik az akt´ıv kulcsot.

5.4.3.

Egy sz´ amelm´ eleti konstrukci´ o

Ebben a szakaszban feltessz¨ uk azt, hogy az ¨osszetett modulus szerinti gy¨okvon´as neh´ez feladat, ´es nem v´egezhet˝o el polinom id˝oben. Ezt kihaszn´alva szerkeszthet˝o olyan s´ema, amely felhaszn´al´onk´ent ¨osszesen 1 kulcs t´arol´as´at ig´enyli. A konstrukci´o alapj´aul a Diffie-Hellman-f´ele kulcscsere protokoll szolg´al. 5.8. T´ etel. Ha feltessz¨ uk azt, hogy ¨ osszetett modulus szerint a gy¨ okvon´ as nehezen elv´egezhet˝o feladat, akkor szerkeszthet˝ o olyan 1-biztos s´ema, amelyben minden felhaszn´ al´onak egyetlen kulcsot kell t´ arolnia, ´es a rendszerben nincs sz¨ uks´eg k¨ ul¨ on u ¨zenetre az akt´ıv kulcs gener´al´as´ahoz. Bizony´ıt´ as. Legyenek p ´es q pr´ımek, n = pq ´es g egy magas rend˝ u elem Zn -ben. V´alasszunk n tetsz˝oleges ´ert´eket u ´gy, hogy azok p´aronk´ent relat´ıv pr´ımek legyenek: a1 , . . . , an eg´esz, ´es (ai , aj ) = 1 minden i 6= j-re. Ezek az ai ´ert´ekek publikusak. Az ui j´at´ekos kulcsa legyen a k¨ovetkez˝o: ri ≡ g ai

(mod n) .

Ha egy T halmazt szeretn´enk kijel¨olni, akkor a tagok a k¨ovetkez˝o szab´aly alapj´an k´epezhetik az akt´ıv kulcsot: k T ≡ g aT aT =

(mod n) , ahol

Y

aj .

j ∈T

A kT kulcsot minden T -beli j´at´ekos ki tudja sz´amolni: a saj´at ri kulcs´at fel kell emelnie arra a hatv´anyra, amelyet a t¨obbi T -beli felhaszn´al´ohoz tartoz´o aj -k ¨osszeszorz´as´aval kap: ai

i

kT ≡ r i T ≡ g ai aT aiT =

Y

aj .

j ∈T \{i}

59

(mod n) , ahol

Indirekt m´odon tegy¨ uk fel, hogy az ud ∈ / T j´at´ekosnak siker¨ ult megkaparintania kT -t kiz´ar´olag a saj´at kulcsa ´es az ai ´ert´ekek felhaszn´al´as´aval. Bel´atjuk, hogy ebben az esetben ud tud gy¨ok¨ot vonni modulo n. ud ismeri kT -t ´es rd -t is: k T ≡ g aT

(mod n) ,

r d ≡ g ad

(mod n) .

Mivel ud inakt´ıv, ez´ert aT ´es ad relat´ıv pr´ımek lesznek. ud futtathatja a kiterjesztett euklideszi algoritmust, amely tal´al egy olyan (x; y) p´art, amelyre x aT + y ad = 1 . Ezt az x ´es y-t felhaszn´alva ud (kT ´es a saj´at kulcsa ismeret´eben) k´epes lesz arra, hogy g ad -b˝ol ad -dik gy¨ok¨ot vonjon: (kT )x (rd )y ≡ g x aT g y ad ≡ g x aT +y ad ≡ g 1 ≡ g

(mod n) .

Ellentmond´asba u ¨tk¨ozt¨ unk a feltev´es¨ unkkel, miszerint az ¨osszetett modulusra vonatkoz´o gy¨okvon´as neh´ez. Ez a s´ema bizonyos ´ertelemben gyeng´ebb, mint az 5.6. T´etelben l´atott. A felt´etelez´es ugyanis, amire ´ep¨ ul, er˝osebb: ha a gy¨okvon´as val´ oban nehezen v´egezhet˝o el, akkor m´aris van egy val´odi egyir´any´ u f¨ uggv´eny¨ unk. Egy egyir´any´ u f¨ uggv´eny l´etez´ese azonban nem implik´alja azt, hogy a gy¨okvon´as neh´ez feladat.

Felt´etelez´es:

-

l´etezik egyir´any´ u f¨ uggv´eny

a gy¨okvon´as neh´ez

Kulcsok sz´ama:

n

log n

1

5.1. t´ abl´ azat. H´arom 1-biztos s´ema ¨osszehasonl´ıt´asa

´ Eszrevehetj¨ uk, hogy a h´arom s´ema k¨oz¨ ul egyik sem 2-biztos. Az els˝o k´et s´em´at az´ert tudja felt¨orni k´et sz¨ovetkez˝o felhaszn´al´o, mert egy¨ uttesen rendelkeznek az ¨osszes kulccsal, ´es ´ıgy k´epesek b´armely akt´ıv kulcsot kisz´amolni. Az utols´o s´em´aban is l´enyeg´eben hasonl´o a helyzet. K´et j´at´ekos minden kulcsot ki tud sz´amolni, mert a kett˝oj¨ uk kulcsa alapj´an (a bizony´ıt´asban l´atott m´odon) kisz´amolhat´o g. Mivel az ai -k publikusak, a k´et kal´oz k¨onnyed´en el˝o tudja ´all´ıtani kT -t. 60

5.5.

Magasabb v´ edetts´ eg˝ u s´ em´ ak

A bemutatott 1-biztos s´em´akat ´ep´ıt˝okockak´ent haszn´alhatjuk, hogy nagyobb koal´ıci´okkal szemben is v´edett rendszereket ´ep´ıthess¨ unk fel. Ennek az ´ep´ıtkez´esnek az ¨otlete nagyon hasonl´ıt arra a konstrukci´ora, amelyet a nyomoz´o s´em´akn´al l´athattunk az el˝oz˝o fejezetben. Mivel b´armelyik 1-biztos s´em´ab´ol kiindulhatunk, ez´ert a kapott rendszer hat´ekonys´ag´at az eredeti s´ema hat´ekonys´ag´anak f¨ uggv´eny´eben tudjuk majd le´ırni. C´elszer˝ u a fenti z´er´o-¨ uzenet s´em´ak k¨oz¨ ul valamelyiket haszn´alni, hiszen ´ıgy minim´alisra cs¨okkenthet˝o az akt´ıv kulcsot l´etrehoz´o u ¨zenetek sz´ama. Jel¨olj¨ uk r-rel azt, hogy az alapul vett 1-biztos s´em´aban egy felhaszn´al´onak h´any kulcsa van. 5.9. T´ etel. Ha k pozit´ıv eg´esz, akkor l´etezik olyan k-biztos ad´ asrejtjelez˝ o s´ema, amelyben egy felhaszn´al´onak O(kr log n) kulcsot kell t´ arolnia, ´es a szolg´ altat´ onak O(k 3 log n) u ¨zenetet kell leadnia az akt´ıv halmaz kijel¨ ol´es´ehez. Bizony´ıt´ as. Jel¨olj¨ uk R-rel a kiindul´o 1-biztos s´em´at. K´esz´ıts¨ uk el ennek az R-nek tl darab p´eld´any´at u ´gy, hogy minden p´eld´anyban teljesen f¨ uggetlen¨ ul gener´aljuk a kulcsokat. Ezeket jel¨olj¨ uk Ri,j -vel, ahol i = 1, . . . , l ´es j = 1, . . . , t. (A t ´es l param´eterek ´ert´ek´et k´es˝obb hat´arozzuk meg.) Az egyszer˝ ubb t´argyal´as kedv´e´ert azonos´ıtsuk egy l × t-es m´atrix elemeit ezekkel az 1-biztos s´em´akkal.

R1,1

R1,2

...

R1,t

R2,1

R2,2

...

R2,t

...

Rl,t

..

Rl,1

.

Rl,2

5.14. ´ abra. A s´ema-m´atrix Ez a m´atrix ´ırja majd le azt, hogy melyik felhaszn´al´o melyik Ri,j s´em´ahoz kap majd hozz´af´er´est. Minden felhaszn´al´o minden sorb´ol pontosan egy s´em´ahoz kap kulcsokat.

61

A konstrukci´o magj´at l darab hash f¨ uggv´eny alkotja, amelyek minden sorban (soronk´ent f¨ uggetlen¨ ul) lek´epezik a felhaszn´al´okat a s´ema-m´atrix oszlopaira: h1 , h2 , . . . , hl : U → {1, . . . , t} . Ezek a hi -k adj´ak meg, hogy az adott sorban melyik felhaszn´al´o melyik s´em´at haszn´alja. Az u j´at´ekos az Ri,hi (u) s´em´akhoz kap kulcsot (i = 1, . . . , l). C´elunk el´er´es´ehez a k¨ovetkez˝o felt´etelt kell kiel´eg´ıtenie a hash f¨ uggv´enyeknek: b´armely legfeljebb k m´eret˝ u C ⊆ U halmaz eset´en lennie kell egy olyan i sornak, ahol a hi |C injekt´ıv. (Itt hi |C -vel a hi f¨ uggv´eny C-re val´o megszor´ıt´as´at jel¨olt¨ uk.) Az injektivit´as ´epp azt jelenti, hogy b´armely u, v ∈ C-re hi (u) 6= hi (v) . Ha vet¨ unk egy pillant´ast a 2.1. r´eszre, akkor k¨onnyen ´atfogalmazhatjuk ezt a felt´etelt. A f¨ uggv´eny-csal´adunknak olyannak kell lennie, hogy b´armely legfeljebb k elem˝ u C ⊂ U -hoz legyen benne egy perfekt hash f¨ uggv´eny. L´assuk, hogyan zajlik az akt´ıv kulcs gener´al´asa ebben a rendszerben. Legyen m az akt´ıv kulcs, amelyet szeretn´enk eljuttatni a m´ar kijel¨olt akt´ıv halmaznak, T -nek. Bontsuk fel m-et l v´eletlen ¨osszetev˝ore: m = m1 ⊕ m2 ⊕ . . . ⊕ ml , ahol mi ∈ {0, 1}s , ´es ⊕ a bitenk´enti mod 2 ¨osszead´as jele. Az mi darabot (1 ≤ i ≤ l) az i. sorban tal´alhat´o s´em´akkal sug´arozzuk: mi -t k¨ uldj¨ uk el az Ri,j s´em´aval az { u ∈ T | hi (u) = j} ⊆ T halmaznak (1 ≤ j ≤ t). Ha ´ıgy j´arunk el, akkor b´armely legitim felhaszn´al´o el˝o tudja ´all´ıtani m-et, hiszen mindegyik mi eljut hozz´a, ´ıgy ezeket csak ¨ossze kell adni. M´asr´eszt igaz lesz az, hogy egy legfeljebb k m´eret˝ u koal´ıci´o nem tudja el˝o´all´ıtani m-et. Legyen C egy ilyen koal´ıci´o. Ekkor (a hash f¨ uggv´enyek v´alaszt´asa miatt) l´etezik egy d sor, ahol a hd |C injekt´ıv. Ez azt jelenti, hogy a d. sorban mindegyik C-beli felhaszn´al´onak m´as-m´as s´em´ahoz van hozz´af´er´ese. Mivel ezek a s´em´ak 1-biztosak, egyed¨ ul semelyik¨ uk sem tudja kital´alni md -t. E tag ismerete n´elk¨ ul mag´at m-et sem tudj´ak megfejteni. Vajon h´any 1-biztos s´em´ara van sz¨ uks´eg ahhoz, hogy k¨onny˝ u legyen ilyen speci´alis tulajdons´ag´ u hash f¨ uggv´enyeket tal´alni? Azt ´all´ıtjuk, hogy ha t = 2k 2 , illetve l = k log n, akkor a v´eletlenszer˝ uen v´alasztott hash f¨ uggv´enyek nagy val´osz´ın˝ us´eggel megfelel˝oek lesznek. Legyen C egy k tag´ u koal´ıci´o. Becs¨ ulj¨ uk meg annak a val´osz´ın˝ us´eg´et, hogy egy v´eletlen¨ ul v´alasztott h : U → {1, . . . , t} f¨ uggv´eny injekt´ıv lesz C-n. Annak az es´elye, hogy egy r¨ogz´ıtett C-beli p´arhoz h ugyanazt az elemet rendeli t/t2 = 1/t. Ezt felhaszn´alva kisz´amolhat´o, hogy milyen es´ellyel lesz h ,,rossz” (azaz nem injekt´ıv).

62

Prob[ h nem injekt´ıv C-n ] =   k 1 = Prob[ van olyan C-beli p´ar, akihez a h ugyanazt rendeli ] ≤ = 2 t k(k − 1) 1 = ≤ 2 4k 4 Ennek seg´ıts´eg´evel kisz´am´ıthat´o, hogy egy l tag´ u H v´eletlen hash-csal´ad mekkora es´ellyel lesz ,,rossz” a fix C koal´ıci´ohoz. 1 1 1 Prob[ C-hez nincs perfekt hash H-ban ] ≤ l = k log n = 2k 4 4 n Annak az es´elye, hogy egy v´eletlen¨ ul megv´alasztott H hash-csal´adhoz tal´alhat´o olyan legfeljebb k tag´ u koal´ıci´o, amelyhez nincs perfekt hash f¨ uggv´eny H-ban:   1 1 n 1 ≤ nk 2k = k Prob[ a H hash-csal´ad rossz ] ≤ 2k n n k n Mindez azt mutatja, hogy a konstrukci´o ´eletk´epes, mert k¨onny˝ u j´o hash f¨ uggv´enyeket tal´alni. Vizsg´aljuk meg, hogy mik´epp alakulnak a hat´ekonys´agi param´eterek. Az eredeti 1-biztos s´em´aban egy j´at´ekosnak r kulcsot kell t´arolnia. Mivel minden sorb´ol pontosan egy ilyen s´em´ahoz kap hozz´af´er´est mindenki, ez´ert ¨osszesen O(kr log n) kulcs ker¨ ul egy felhaszn´al´ohoz. A legrosszabb esetben a s´ema-m´atrix ¨osszes s´em´aj´aval le kell adnunk egy u ¨zenetet az akt´ıv kulcs eljuttat´as´ahoz, ez´ert ¨osszesen O(k 3 log n) u ¨zenetet kell sug´aroznunk. V´egezet¨ ul l´assuk, hogy mik´epp alak´ıthat´o egy ilyen k-biztos s´ema (, k)-biztoss´a, ´es hogy egy ilyen v´alt´as milyen m´ert´ekben n¨ovelheti a hat´ekonys´agot. 5.10. K¨ ovetkezm´ eny. Ha  pozit´ıv sz´ am, ´es k pozit´ıv eg´esz, akkor l´etezik olyan (, k)-biztos ad´asrejtjelez˝o s´ema, amelyben egy felhaszn´ al´ onak O(r log(1/)) kulcsot kell t´ arolnia, ´es az akt´ıv kulcs gener´ al´ as´ ahoz O(k 2 log(1/)) u ¨zenetre van sz¨ uks´eg. Bizony´ıt´ as. Ez az eredm´eny egyszer˝ uen ad´odik az el˝oz˝o konstrukci´ob´ol. Legyen H egy v´eletlen hash-csal´ad, ´es C egy v´eletlen koal´ıci´o. Az (, k)-biztoss´aghoz a k¨ovetkez˝o kell: 1 = . 4l Ebb˝ol k¨ozvetlen¨ ul ad´odik, hogy el´eg l = log4 (1/) sor a s´ema-m´atrixban, hogy teljes¨ ulj¨on az (, k)-biztoss´ag. Prob[ C-hez nincs perfekt hash H-ban ] ≤

63

6.

Digit´ alis v´ızjelek lehets´ eges alkalmaz´ asai

Ebben a szakaszban egy olyan technik´ar´ol ejt¨ unk sz´ot, amely ´altal´anosabb az ujj´ lenyomatoz´asn´al. Attekintj¨ uk a digit´alis v´ızjelek alkalmaz´asi k¨or´et. Digit´alis v´ızjel alatt egy digit´alis dokumentumba be´agyazott jelsorozatot ´ert¨ unk. Ennek a be´agyaz´asnak az a c´elja, hogy megjel¨olj¨ uk az eredeti adatot. A k¨ovetkez˝okben ´attekintj¨ uk, hogy milyen c´ellal szok´as v´ızjelet elhelyezni egy dokumentumban. Van olyan alkalmaz´asi ter¨ ulet, ahol a v´ızjelet egyszer˝ uen ,,hozz´acsaphatjuk” a dokumentumhoz, mint egy sorozatsz´amot. Sokszor azonban ez nem el´eg: ´altal´aban a k¨ovetkez˝o elv´ar´asoknak kell megfelelnie egy v´ızjelnek: • a v´ızjel helye ne legyen meg´allap´ıthat´o17 • a be´agyazott v´ızjel ne rontsa a term´ek funkcionalit´as´at • a v´ızjel legyen robusztus18

6.1.

Ad´ as-ellen˝ orz´ es

1997-ben nagy botr´any t¨ort ki Jap´anban, amikor t¨obb csatorn´ar´ol is kider¨ ult, hogy a val´os´agban sug´arzottn´al t¨obb rekl´amid˝ot adott el. A hirdet˝ok t¨obb ezer olyan rekl´am´ert fizettek, amelyek soha nem ker¨ ultek ad´asba. Ezt a gyakorlatot sok-sok ´even ´at folytatt´ak a t´ev´et´arsas´agok, val´osz´ın˝ uleg nem csak Jap´anban. Sok szervezetnek (´es mag´anszem´elynek) ´erdek´eben ´allt, hogy bevezess´ek az ad´asok ellen˝orz´es´et. A hirdet˝ok szerett´ek volna tudni, hogy val´oban lementek-e a kifizetett rekl´amok. Hasonl´oan motiv´altak voltak a lemezkiad´ok, zen´eszek, sz´ın´eszek is: biztos´ıtani akart´ak, hogy val´oban megkapj´ak a jogd´ıjaikat. Ha minden videoklipben, rekl´amban egyedi v´ızjelet helyez¨ unk el, akkor lehet˝ov´e v´alik annak ellen˝orz´ese, hogy az adott anyagot leadt´ak-e, ´es ha igen, h´anyszor. Ehhez minden ad´ok¨orzetben fel kell ´all´ıtani egy ´allom´ast, amely a sug´arzott ad´asban keresi, ´es regisztr´alja a v´ızjeleket.

6.2.

Tulajdonos azonos´ıt´ asa

c 2003, Aliz Bt. Ez az apr´o Sokszor tal´alkozunk a szerz˝oi jogot v´ed˝o felirattal: figyelmeztet´es ´epp az´ert szerepel k¨onyvek bor´ıt´oj´an, cd-k tokj´an, filmek f˝oc´ım´enek v´eg´en, hogy t´aj´ekoztasson minket, ki´e is az adott term´ek. El˝ofordul azonban, hogy 17

Term´eszetesen a konkr´et alkalmaz´ast´ol f¨ ugg, hogy ez pontosan mit jelent. Egyes esetekben el´eg, ha a mag´ anyos ´ arul´ ok ellen v´ed a rendszer. M´askor azonban arra is fel kell k´esz¨ ulni, hogy a felhaszn´al´ ok sz¨ ovetkezhetnek. 18 Ez pl. k´epek eset´en azt jelenti, hogy a v´ızjel ne v´altozzon meg, ha a k´epet ´atm´eretezik, vagy m´as geometriai transzform´ aci´ ot hajtanak v´egre rajta.

64

a felirat – akarva vagy akaratlanul – elv´alik mag´at´ol a term´ekt˝ol. Gondoljunk csak arra, hogy mostan´aban a kereskedelmi csatorn´akon nem divat leadni a filmek v´egef˝oc´ım´et. Hab´ar az szerves r´esze a filmnek, ´es t¨ort´enetesen a szerz˝oi jogi felirat is abban tal´alhat´o. A hagyom´anyos figyelmeztet´est kieg´esz´ıthetj¨ uk egy digit´alis v´ızjel be´agyaz´as´aval, amely j´oval nehezebben ,,kopik le” a term´ekr˝ol. Az Adobe c´eg n´epszer˝ u Photoshop programj´ahoz adj´ak a Digimarc plugint (r´egebben k¨ ul¨on program volt), amely lehet˝ov´e teszi digit´alis v´ızjelek be´agyaz´as´at illetve detekt´al´as´at. A rendszer l´enyege, hogy ha egy k´epb˝ol kiolvasunk egy v´ızjelet, akkor a program kapcsol´odik a Digimarc adatb´azis´ahoz, hogy onnan olvassa ki a szerz˝oi jogi adatokat. Az´ert, hogy mi is szerepelhess¨ unk ebben az adatb´azisban, term´eszetesen fizetni kell. A 2003 m´arciusi regisztr´aci´os k¨olts´egek l´athat´ok az al´abbi t´abl´azatban. (Ezek a d´ıjak a legolcs´obb szolg´altat´ashoz tartoznak.)

K´epek sz´ama Regisztr´aci´os k¨olts´eg (USD) 1-99

$ 50

100-999

$ 150

1000-4999

$ 530

6.2. t´ abl´ azat. A Digimarc ´arai

6.3.

Tulajdonjog bizony´ıt´ asa

Sokszor nem el´eg, ha a v´ızjel alapj´an azonos´ıtani lehet a jogos tulajdonost, hanem bizony´ıtani is kell, hogy val´oban a felt¨ untetett szem´ely a jogos tulajdonos. Tegy¨ uk c 2003 Aliz felirafel, hogy Bob let¨olti Aliz honlapj´ar´ol Aliz kedvenc f´enyk´ep´et. A c 2003 Bob feliratra, ´es felrakja a saj´at honlapj´ara. Hogyan d¨onthet˝o tot lecser´eli el az esetlegesen felmer¨ ul˝o jogvita? Klasszikus esetben Aliz lev´edetheti a fot´ot. ´Igy k¨onnyen r¨ovidre z´arhat´o egy tulajdonjogi vita. Ha azonban Aliz nem jegyezteti be a fot´ot, akkor csak a negat´ıvval tudja bizony´ıtani, hogy a k´ep az ¨ov´e. Egy digit´alis f´enyk´epnek viszont nincs negat´ıvja. S˝ot, Bob v´egrehajthat n´eh´any apr´o v´altoztat´ast a k´epen, hogy m´eg nehezebben lehessen bizony´ıtani a csal´ast. Aliz u ´gy tud v´edekezni a hasonl´o vissza´el´esek ellen, hogy be´agyaz egy v´ızjelet a k´epbe. ´Igy k´es˝obb bizony´ıthat´o, hogy ˝o a jogos tulajdonos. Egy ilyen v´ızjelnek felfedezhetetlennek ´es robusztusnak kell lennie, nehogy Bob kit¨or¨olhesse, vagy eltorz´ıthassa azt. 65

6.4.

Hiteles´ıt´ es

Egy digit´alis dokumentumot nem t´ ul neh´ez m´odos´ıtani. Ak´ar u ´gy is, hogy a v´altoz´as szinte ´eszlelhetetlen legyen. Sok esetben komoly gondot jelenthet, ha nem tudunk arr´ol, hogy a vizsg´alt dokumentum nem eredeti. Ha egy digit´alis dokumentum bizony´ıt´ekk´ent szolg´al egy b´ır´os´agi t´argyal´ason, akkor l´enyeges a dokumentum hiteless´ege. Orvosi alkalmaz´asok eset´eben m´eg fontosabb, hogy egy dokumentumr´ol bizony´ıthat´o legyen az eredetis´ege. Egy digit´alis dokumentum ,,´erintetlens´eg´enek” ellen˝orz´es´ere alkalmas eszk¨oz lehet egy hash f¨ uggv´eny. A 2.1. r´esz m´asodik fel´eben sz´oltunk a kriptogr´afiai c´elokra alkalmas hash f¨ uggv´enyekr˝ol. Az ott le´ırtak ´ertelm´eben egy hash f¨ uggv´enyhez neh´ez olyan dokumentumot tal´alni, amelynek ugyanaz a lenyomata, mint a hiteles´ıteni k´ıv´ant dokumentumnak. Ha ak´ar csak egyetlen bit is megv´altozik, akkor a hashlenyomat is m´odosul. Ha a dokumentum lenyomat´at v´ızjelk´ent be´agyazzuk az anyagba, akkor ut´olag meg lehet ´allap´ıtani, hogy t¨ort´ent-e v´altoz´as. Csak ¨ossze kell hasonl´ıtani a kiolvasott v´ızjelet a dokumentum lenyomat´aval. Term´eszetesen nem szabad megfeledkezni arr´ol, hogy a v´ızjel be´agyaz´as´aval a dokumentum lenyomata megv´altozik. Ezt a probl´em´at p´eld´aul u ´gy lehet lek¨ uzdeni, hogy a lenyomatot csak a dokumentum 19 ´erv´enyes bitjei alapj´an sz´amoljuk. L´eteznek p´eld´aul olyan rendszerek, amelyek elviselik a JPEG-t¨om¨or´ıt´est ([13]).

6.5.

Digit´ alis ujjlenyomatok

A kor´abban bemutatott digit´alis ujjlenyomatok felfoghat´ok egy speci´alis v´ızjelk´ent is, amely alapj´an nyomoz´ast lehet v´egezni. Ha a j´at´ekosok manipul´alj´ak a v´ızjelet, az m´eg akkor is elegend˝o inform´aci´ot tartalmaz a nyomoz´ashoz. Megeml´ıtj¨ uk az ujjlenyomatok egy ´erdekes alkalmaz´as´at. A nagyobb j´at´ekfilmek k´esz´ıt´es´en´el miden nap kiadj´ak az aznap k´esz¨ ult anyagot a rendez˝onek, az operat˝ornek, a v´ag´onak ´es m´eg n´eh´any munkat´arsnak. Az ilyen v´agatlan anyagot muszternek h´ıvj´ak. Sok botr´any (´es olykor jelent˝os k´ar is) sz´armazott abb´ol, hogy egy-egy muszter id˝o el˝ott kisziv´argott. Ez´ert a nagyobb filmgy´arak a muszter minden p´eld´any´at megjel¨olik egy-egy ujjlenyomattal. Ha az anyag nyilv´anoss´agra ker¨ ul, akkor viszonylag k¨onnyen kider´ıthet˝o, hogy melyik munkat´ars a b˝ un¨os.

6.6.

M´ asol´ asv´ edelem

V´ızjelek alkalmaz´as´aval lehet˝os´eg ny´ılik az illeg´alis m´asol´as elleni akt´ıvabb fell´ep´esre is. Napjainkban egyre t¨obb a m´asol´asv´edett zenei cd a boltokban. Ezekbe egy olyan v´ızjel van be´agyazva, amely azt jelzi, hogy a term´ek m´asol´asa tilos. Ha a 19

Egy bit akkor ´erv´enyes, ha nem tartozik a v´ızjelhez.

66

cd-´ır´o detekt´al egy ilyen v´ızjelet, akkor nem m´asolja le a lemezt. Ezek a rendszerek nem t¨ok´elestesek. Egy r´egebbi ´ır´oval p´eld´aul ´atm´asolhat´o az ,,´ır´asv´edett” lemez is.

6.7.

Rejtett kommunik´ aci´ o

Az egyik legklasszikusabb m´odja a biztons´agos kommunik´aci´onak az u ¨zenet elrejt´ese. Ilyenkor az adat titkos´ıt´asa helyett az u ¨zenet l´etez´es´et pr´ob´aljuk meg pal´astolni. Az ilyen rejtett kommunik´aci´ot szteganogr´ afi´ anak nevezz¨ uk. M´ar az ´okori g¨or¨og¨ok is szellemes ¨otleteket alkalmaztak. R´a´er˝osebb id˝okben p´eld´aul u ´gy juttattak el u ¨zenet egyik helyr˝ol a m´asikra, hogy egy szolga fej´et kopaszra borotv´alt´ak, majd r´a´ırt´ak az u ¨zenetet. Megv´art´ak, m´ıg u ´jra kin˝o a haja, ´es ´ıgy k¨ uldt´ek el a vesz´elyes u ´tra. Mivel sehol nem tal´alhattak n´ala semmilyen gyan´ us iratot, ez´ert a szolga biztons´aggal el tudott jutni a c´ımzetthez, ahol u ´jra leny´ırt´ak a haj´at, hogy olvashat´ov´a v´aljon az u ¨zenet. Tulajdonk´eppen maga a v´ızjel is egy szteganogr´afiai eszk¨oz, hiszen ´altal´aban felfedezhetetlennek kell lennie. ´Igy egy m˝ uk¨od˝o v´ızjelez˝o elj´ar´assal egy¨ utt m´aris a kez¨ unkben van egy a g¨or¨og¨ok´en´el gyorsabb (ha nem is szellemesebb) m´odszer.

67

7.

Kriptogr´ afia az iskol´ aban

A magyar matematika- ´es informatikaoktat´as egyel˝ore sajnos t´avol ´all att´ol, hogy a rejtjelez´es vil´aga ak´ar csak el˝obukkanhasson a gimn´aziumi ´or´akon. Pedig a kriptogr´afia t¨obb szempontb´ol is vonz´o ter¨ ulet, ´es eg´esz biztosan meg´eri fakult´aci´on (vagy szakk¨or¨on) r´asz´anni n´eh´any ´or´at. T¨obbek k¨oz¨ott kit˝ un˝o lehet˝os´eget ny´ ujt a k¨ ul¨onb¨oz˝o tant´argyi ismeretek ¨osszekapcsol´as´ara. Rengeteg ´erdekes t¨ort´enelmi p´eld´aval szines´ıthetj¨ uk el˝oad´asainkat, elbesz´elgethet¨ unk kriptogr´afiai t´argy´ u iro20 dalmi m˝ uvekr˝ol , ´erdekes ¨osszef¨ ugg´eseket mutathatunk be kriptogr´afia ´es nyelv´eszet k¨oz¨ott, ´es a k´odol´asokkal kapcsolatban ak´ar a biol´ogia ter¨ ulet´ere is elkalandozhatunk, ´es besz´elhet¨ unk a DNS fel´ep´ıt´es´er˝ol. De term´eszetesen matematikai szempontb´ol is gazdag a t´emak¨or. Mindenk´eppen u ¨d´ıt˝oleg hathat a mer˝oben u ´j tartalom, ´es a kreat´ıv feladatok ellenpontj´aul szolg´alhatnak az unalomig r´agott gyakorl´o p´eld´aknak ´es m´odszereknek. Ha u ´gy d¨ont¨ unk, hogy kriptogr´afi´at tan´ıtunk az iskol´aban, akkor az egyik alapvet˝o c´elunk az lehet, hogy p´eld´at mutassunk a matematika gyakorlati alkalmaz´as´ara, ´es ´ıgy ´erz´ekeltess¨ uk a matematika fontoss´ag´at. A hangs´ ulyt ennek ellen´ere nem felt´etlen¨ ul a ,,matematikai mondanival´ora” kell helyezni; legal´abbis nem a form´alis, elm´eleti jelleg˝ u ismeretek ´atad´as´ara. A t´ema ,,h´al´as” abb´ol a szempontb´ol, hogy rengeteg lehet˝os´eget ad a gyermekek aktiviz´al´as´ara, ´es alkot´ok´eszs´eg¨ uk felsz´ınre hozatal´ara. Term´eszetesen egy ilyen rendhagy´o tananyag eset´en sem szabad megfeledkezni a gyeng´ebb k´epess´eg˝ u tanul´okr´ol, akik nehezebben sejtik meg a helyes ir´anyt egy-egy probl´ema megold´asa k¨ozben. Sajnos ezen dolgozatban nem f´er el egy hosszabb (´ertsd: nem ´ertelmetlen¨ ul r¨ovid) m´odszertani le´ır´as a kriptogr´afia iskolai tan´ıt´as´ar´ol. A szerz˝o azonban k´esz´ıtett egy ilyen t´argy´ u dolgozatot kor´abban ([14]). A t´ema ir´ant ´erdekl˝od˝o olvas´o tal´an mer´ıthet n´eh´any ¨otletet bel˝ole.

20

P´eld´ aul E. A. Poe Az aranybog´ ar c´ım˝ u novell´aj´ar´ol.

68

8.

¨ Osszefoglal´ as

A dolgozatban a digit´alis szerz˝oi jogok v´edelm´evel kapcsolatos legalapvet˝obb matematikai m´odszereket ´es eredm´enyeket tekintett¨ uk ´at. Ahhoz, hogy elrettents¨ uk a felhaszn´al´okat a jogtalan m´asol´ast´ol, egy egyedi azonos´ıt´o jelet u ¨ltethet¨ unk a digit´alis dokumentumba. Ez lehet˝ov´e teszi azt, hogy azonos´ıtani lehessen az illeg´alis k´opi´ak forr´as´at. L´attuk, hogy j´oval bonyolultabb´a v´alik a helyzet a j´at´ekosok sz¨ovetkez´ese eset´en. Ilyenkor ¨osszehasonl´ıthatj´ak a k´opi´aikat, ´es ´ıgy kit¨or¨olhetik, vagy megv´altoztathatj´ak a be´agyazott jelet. Ezen probl´ema megold´as´ara mutattuk be az ujjlenyomat-k´odokat. Ha egy ilyen k´od szavait helyezz¨ uk el a felhaszn´al´oknak adott dokumentumokban, akkor a rendszer m˝ uk¨od˝ok´epes marad: legal´abb egy ´arul´ot nagy val´osz´ın˝ us´eggel el tudunk fogni. Bel´attuk azt is, hogy soha nem z´arhat´o ki teljesen, hogy a nyomoz´as sor´an ´artatlan felhaszn´al´ot gyan´ us´ıtunk meg. A k´odhossz n¨ovel´es´evel azonban tetsz˝oleges  ´ert´ek al´a cs¨okkenthet˝o a hiba val´osz´ın˝ us´ege. Ilyen 2 felt´etelek mellett az optim´alis ujjlenyomat-k´odok O(k log(n/)) hossz´ us´ag´ uak, ahol n az ¨osszes felhaszn´al´o sz´ama, k pedig a legnagyobb lehets´eges koal´ıci´o m´erete. Nem szabad megfeledkezni arr´ol, hogy a koncepci´o alapj´at a jel¨ol´esi felt´etel k´epezte. Eszerint a sz¨ovetkez˝o felhaszn´al´ok csakis olyan biteket tudnak megv´altoztatni, vagy kit¨or¨olni, amelyek a p´eld´anyaikban elt´ernek. Az term´eszetesen k¨ ul¨on vizsg´al´od´ast ig´enyel, hogy mik´epp lehet ilyen t¨ok´eletesen elrejteni az ujjlenyomat bitjeit. Sz´o esett m´eg dinamikus alkalmaz´asokr´ol, ahol az adatok on-line jelleg˝ uek. Ezen alkalmaz´asok eset´eben ´ertelmess´e v´alik az a modell, amelyben a j´at´ekosok nem t¨or¨olhetik ki az ujjlenyomat bitjeit. Ilyen felt´etelek mellett m´ar megval´os´ıthat´o a 100%-os biztons´ag´ u nyomoz´as. Az ujjlenyomat egy bet˝ uj´enek ebben a rendszerben egy kulcs felel meg. A bemutatott s´ema O(k log(n/)) kulccsal, O(k 2 log(n/)) redundanci´aval m˝ uk¨odik, ´es a felhaszn´al´oknak O(k log(n/)) plusz sz´am´ıt´ast kell elv´egezni¨ uk az on-line ad´as dek´odol´as´ahoz. Szorosan a dinamikus alkalmaz´asokhoz kapcsol´od´oan ejtett¨ unk sz´ot az ad´asrejtjelez˝o s´em´akr´ol. Ezek lehet˝ov´e teszik egy k¨ozponti adatszolg´altat´o sz´am´ara, hogy dinamikusan v´altoztassa azok k¨or´et, akik dek´odolni tudj´ak az ad´ast. Az ilyen rendszerek sz´eles k¨orben haszn´alhat´oak. T¨obbek k¨oz¨ott nagyon hasznos, ´es hat´ekony kieg´esz´ıt˝ou ¨l szolg´alhatnak nyomoz´o rendszerekhez. Ilyenkor ugyanis el´eg egyetlen kal´oz dek´oder elfog´asa ahhoz, hogy az ¨osszes illeg´alis dek´odert haszn´alhatatlann´a tegy¨ uk. H´arom k¨ ul¨onb¨oz˝o er˝oss´eg˝ u felt´etelez´esre ´ep´ıtve h´arom k¨ ul¨onb¨oz˝o hat´ekonys´ag´ u s´em´at mutattunk be. Ha a k¨oz´eps˝o felt´etelb˝ol indulunk ki (l´etezik egyir´any´ u f¨ uggv´eny), akkor egy O(log n log(1/)) kulcsot ´es O(log2 n log(1/)) u ¨zenetet ig´enyl˝o rendszert kapunk.

69

8.1. 8.1.1.

Tov´ abbi eredm´ enyek, nyitott k´ erd´ esek Aszimmetrikus ujjlenyomatok

Az ujjlenyomat-k´odokkal kapcsolatban felvet˝odik n´eh´any tov´abbi probl´ema. Ha az adatszolg´altat´o felfedez egy hamis k´opi´at, akkor nincs megb´ızhat´o igazol´as arra, hogy az elfogott p´eld´anyt val´oban az a j´at´ekos k´esz´ıtette, akit a szolg´altat´o gyan´ us´ıt. Egy rosszindulat´ u adatszolg´altat´o elvileg gyan´ uba keverhet egy teljesen ´artatlan felhaszn´al´ot u ´gy, hogy k´esz´ıt egy hamis dokumentumot (vagy fabrik´al egy kal´oz dek´odert), amelyet azt´an ,,megtal´al”, ´es meggyan´ us´ıtja a j´at´ekost. Ez a probl´ema abb´ol ad´odik, hogy mind az adatszolg´altat´o, mind a j´at´ekos hozz´af´er az ujjlenyomattal ell´atott dokumentumhoz. Ezt a fajta k¨olcs¨on¨oss´eget k¨ usz¨ob¨olik ki az aszimmetrikus ujjlenyomatok. Az ujjlenyomatok aszimmetrikus be´agyaz´asa a k¨ovetkez˝ot jelenti. Miut´an a term´ek a felhaszn´al´ohoz ker¨ ul, kiz´ ar´ olag a felhaszn´al´o ismeri az ujjlenyomatozott dokumentumot. Mindazon´altal, ha a szolg´altat´o tal´al egy p´eld´anyt, akkor egy harmadik f´el sz´am´ara is meggy˝oz˝oen tudja bizony´ıtani, hogy a k´opia val´oban a meggyan´ us´ıtott j´at´ekost´ol sz´armazik. Ennek ´erdek´eben az ujjlenyomat be´agyaz´asa egy k´etr´esztvev˝os protokoll keret´eben zajlik: az egyik f´el a szolg´altat´o, a m´asik a vev˝o. A protokoll a nyilv´anos kulcs´ u21 rejtjelez´es ¨otlet´ere ´ep¨ ul, ´es a l´enyege, hogy a vev˝o is be´ep´ıt egy titkot az ujjlenyomatba. A r´eszletes kidolgoz´as [15]-ben olvashat´o. 8.1.2.

Anonim ujjlenyomatok

Pfitzmann ´es Waidner [16]-ban veti fel az anonim (n´evtelen) ujjlenyomatoz´ as ¨otlet´et. Az elektronikus piacon is ´erv´enyes¨ ulnie kell annak az elvnek, hogy olcs´obb term´ekek v´as´arl´asa eset´en (pl. k¨onyv, zenei cd) a vev˝o n´evtelen maradhasson. Ez k¨ ul¨on¨osen fontos lehet, ha p´eld´aul k¨onyvekr˝ol, u ´js´agokr´ol van sz´o, hiszen ezek nagyon sokat el´arulnak a vev˝or˝ol. Ezt a fajta elektronikus n´evtelens´eget biztos´ıtj´ak az anonim h´al´ozatok, protokollok ´es fizet´esi rendszerek. Kellemetlen lenne, ha egy ilyen rendszerben a vev˝onek m´egis meg kellene adnia a szem´elyes adatait csup´an az´ert, hogy az ujjlenyomatoz´ast elv´egezhess¨ uk. A Pfitzmann ´es Waidner ´altal bemutatott rendszerben megoldhat´o az anonim ujjlenyomatoz´as u ´gy, hogy k´es˝obb az ´arul´okat (´es csakis az ´arul´okat) m´egis azonos´ıtani lehessen. A vev˝ot nem a val´odi, hanem az u ´n. digit´ alis szem´elyazonoss´ aga alapj´an kezelj¨ uk majd. Ez l´enyeg´eben egy digit´alis al´a´ır´as s´em´ab´ol sz´armaz´o kulcsot jelent. Az anonim rendszerben szerepet kap az a bank, amelyik a vev˝o sz´aml´aj´at vezeti. A bank ugyanis mindenk´eppen rendelkezik a vev˝o szem´elyes adataival. Ha bizony´ıthat´o, hogy a vev˝o illeg´alis m´asolatokat k´esz´ıtett, akkor a bank kiadhatja ´ a szem´elyes adatokat. Erdekess´ egk´ent jegyezz¨ uk meg, hogy ezek a rendszerek m´eg 21

M´as n´even: aszimmetrikus.

70

biztons´agosabb´a tehet˝ok, hogy akkor is m˝ uk¨odjenek, ha a bank nem kooper´al (nem adja ki a szem´elyes adatokat). 8.1.3.

M´ eg hat´ ekonyabb nyomoz´ as

´ Ujabb ´erdekes probl´ema mer¨ ul fel, ha nem csak egyetlen ´arul´ot szeretn´enk elfogni, hanem az ¨osszeset. Ilyenkor term´eszetesen valamilyen ´esszer˝ u kik¨ot´est kell tenni az ´arul´ok strat´egi´aj´ara. Fel kell tenni, hogy az ´arul´ok racion´alisan viselkednek, ´es egyik¨ uk sem akar nagyobb kock´azatot v´allalni, mint a t¨obbiek. Ez akkor teljes¨ ul, ha mindannyian nagyj´ab´ol ugyanannyi bitet adnak a hamis´ıtott dokumentumba. Erre vonatkoz´o eredm´enyek tal´alhat´ok [17]-ben. Az ott bemutatott k´odok csak kis m´eret˝ u koal´ıci´ok eset´en, legfeljebb k = 3 ´arul´oig m˝ uk¨od˝ok´epesek. K´erd´es, hogy mik´epp lehet nagyobb k-ra ilyen k´odokat k´esz´ıteni? Tov´abbi izgalmas k´erd´es, hogy milyen javul´ast lehet el´erni a nyomoz´o s´em´ak hat´ekonys´ag´aban, ha Tardos m´odszereit haszn´aljuk ([19]).

K¨ osz¨ onetnyilv´ an´ıt´ as Szeretn´em megk¨osz¨onni t´emavezet˝omnek, Grolmusz Vinc´enek a seg´ıts´eg´et. Megjegyz´esei, javaslatai ´es jav´ıt´asai mind formai, mind tartalmi szempontb´ol jelent˝osen megk¨onny´ıtett´ek a munk´amat. K¨osz¨on¨om tov´abb´a Tardos G´abornak, hogy k´eszs´egesen v´alaszolt a t´em´aval kapcsolatos k´erd´eseimre.

71

Hivatkoz´ asok [1] N. Alon, J. Bruck, J. Naor, M. Naor ´es R. Roth, Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs, IEEE Transactions on Information Theory, vol. 38 (1992) [2] N. Alon, J. Spencer, The probabilistic method, Wiley (1992) [3] D. Boneh ´es J. Shaw Collusion-secure fingerprinting for digital data, IEEE Transactions on Information Theory, vol. 44 (1998) [4] B. Chor, A. Fiat ´es M. Naor, Tracing traitors, Proceedings of Crypto ’94, LNCS, vol. 839, pp. 257-270 (1994) [5] T. Cormen, Ch. Leiserson ´es R. Rivest, Algoritmusok, M˝ uszaki K¨onyvkiad´o (1999) [6] I. Cox, J. Kilian, T. Leighton, T. Shamoon, A secure robust watermark for multimedia, Information Hiding, LNCS, vol. 1174, pp. 185-206 (1996) [7] I. Cox, M. Miller ´es J. Bloom, Watermarking applications and their properties, International Conference on Information Technology, Las Vegas (2000) [8] Z.J. Czech, G. Havas ´es B.S. Majewski, Perfect hashing, Theoretical Computer Science, vol. 182, pp. 1-143 (1997) [9] DigiMarc Co., http://www.digimarc.com [10] A. Fiat ´es M. Naor, Broadcast encryption, Proceedings of Crypto ’93, LNCS, vol. 773, pp. 480-491 (1994) [11] O. Goldreich, Foundations of cryptography, Cambridge University Press (2001) [12] J. Hastad, R. Impagliazzo, L.A. Levin ´es M. Luby, Construction of a pseudorandom generator from a one-way function, SIAM Journal on Computing, vol. 28, num. 4, pp. 1364–1396 (1999) [13] C. Y. Lin ´es S. F. Chang, A robust image authentication algorithm surviving JPEG compression, In SPIE Storage and Retireval of Image/Video Databases (1998) [14] P. M´atray, Rejtjelez´es, Tanmenet (2002) http://stuber.hu/pub/ [15] B. Pfitzmann ´es M. Schunter, Asymmetric fingerprinting, Proceedings of Eurocrypt ’96, LNCS (1997) 72

[16] B. Pfitzmann ´es M. Waidner, Anonymous fingerprinting, Proceedings of Eurocrypt ’97, LNCS, vol. 1070, pp. 84-95 (1996) [17] F. Seb´e ´es J. Domingo-Ferrer, Short 3-secure fingerprinting codes for copyright protection, LNCS, vol. 2384, pp. 316-327 (2002) [18] S. Singh, K´odk¨onyv, Park K¨onyvkiad´o (2001) [19] G. Tardos, Optimal probabilistic fingerprint codes, megjelenik a Proceedings of STOC 2003-ban (2003)

73