Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as
1 / 22
Adatbiztons´ag ´es val´osz´ın˝us´egsz´am´ıt´as Nemetz O.H. Tibor eml´ek´ere Csirmaz L´aszl´ o K¨ oz´ ep Eur´ opai Egyetem R´ enyi Int´ ezet
2011 m´ajus 9.
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as
Nemetz O.H. Tibor, 1941–2006
2 / 22
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as ´ Eletrajzi adatok
V´azlat
1
´ Eletrajzi adatok
2
Alkalmazott statisztika, avagy hogyan nyerj¨ unk a Szerencseker´ekben?
3
Egy kutat´asi probl´ema
4
Tanul´as hib´aval
3 / 22
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as ´ Eletrajzi adatok
Munk´ass´aga
R´enyi Int´ezet (l´anykori nev´en Matematikai Kutat´o) 1969-t˝ol K¨oz´episkolai Matematikatan´ıt´asi Kis´erlet (1973 - 76) Tank¨onyvek (val´osz´ın˝ us´egsz´am´ıt´as, statisztika) Oktat´as, pedag´ogia ICME–6 szervez´esi munk´ai (1988) Eurocrypt’92 Balatonf¨ ureden Adatbiztons´agi szak´ert˝ o V´ızjel projekt (2004) Vend´egkutat´o/tan´ar (Ottawa, Frankfurt, B´ecs, Ankara)
4 / 22
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as Alkalmazott statisztika, avagy hogyan nyerj¨ unk a Szerencseker´ ekben?
V´azlat
1
´ Eletrajzi adatok
2
Alkalmazott statisztika, avagy hogyan nyerj¨ unk a Szerencseker´ekben?
3
Egy kutat´asi probl´ema
4
Tanul´as hib´aval
5 / 22
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as
6 / 22
Alkalmazott statisztika, avagy hogyan nyerj¨ unk a Szerencseker´ ekben?
Nyelvstatisztik´ak
Nemetz Tibor komment´arja: Eredm´enyes rejtjelfejt´es csak megbizhat´ o “nyelvstatisztikai t´abl´azatok birtok´aban k´epzelhet˝o el. Napjaink sz´am´ıt´astechnikai szintje mellett szinte m´ar elk´epzelhetetlen, hogy egy ilyen t´abl´azat elk´esz´ıt´ese m´eg a 70-es ´evek v´eg´en sem volt probl´emamentes. . . . Ezekb˝ol arra is lehet k¨ ovetkeztetni, hogy az egym´ast´ol 5-8 t´avols´agra elhelyezked˝ o bet˝ uk egym´ast´ ol statisztikailag f¨ uggetlenek.
”
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as Alkalmazott statisztika, avagy hogyan nyerj¨ unk a Szerencseker´ ekben?
´Irott nyelv entr´opi´aja K´ erd´ es Az ´ırott sz¨oveg egyetlen bet˝ uje h´any bit inform´aci´ ot hordoz?
7 / 22
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as Alkalmazott statisztika, avagy hogyan nyerj¨ unk a Szerencseker´ ekben?
´Irott nyelv entr´opi´aja K´ erd´ es Az ´ırott sz¨oveg egyetlen bet˝ uje h´any bit inform´aci´ ot hordoz? K¨ ul¨onb¨oz˝o nyelvekre, k¨ ul¨ onb¨ oz˝ o t´emak¨ or¨ okre a v´alasz m´as ´es m´as. Hat´art szab a lehets´eges t¨ om¨ or´ıt´es m´ert´ek´ere. Angolra C. Shannon adott becsl´eseket. Nemetz: csonk´ıtott sz¨ ovegek rekonstru´alhat´ os´ag´aval becs¨ ul!
7 / 22
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as Alkalmazott statisztika, avagy hogyan nyerj¨ unk a Szerencseker´ ekben?
´Irott nyelv entr´opi´aja K´ erd´ es Az ´ırott sz¨oveg egyetlen bet˝ uje h´any bit inform´aci´ ot hordoz? K¨ ul¨onb¨oz˝o nyelvekre, k¨ ul¨ onb¨ oz˝ o t´emak¨ or¨ okre a v´alasz m´as ´es m´as. Hat´art szab a lehets´eges t¨ om¨ or´ıt´es m´ert´ek´ere. Angolra C. Shannon adott becsl´eseket. Nemetz: csonk´ıtott sz¨ ovegek rekonstru´alhat´ os´ag´aval becs¨ ul! T´etel (Nemetz, Simon Judit) Az ´ırott magyar nyelv entr´ opi´aja 1.13 ´es 1.49 k¨ oz¨ ott van.
7 / 22
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as Alkalmazott statisztika, avagy hogyan nyerj¨ unk a Szerencseker´ ekben?
Szerencseker´ek – hogyan j´atsszuk?
8 / 22
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as Alkalmazott statisztika, avagy hogyan nyerj¨ unk a Szerencseker´ ekben?
Szerencseker´ek – hogyan j´atsszuk?
Tippelhet¨ unk m´assalhangz´ ot, ha van, megkapjuk a forgatott ¨osszeget. V´as´arolhatunk mag´anhangz´ ot. Milyen strat´egi´at v´alasszunk?
9 / 22
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as Alkalmazott statisztika, avagy hogyan nyerj¨ unk a Szerencseker´ ekben?
Szerencseker´ek – hogyan j´atsszuk?
Tippelhet¨ unk m´assalhangz´ ot, ha van, megkapjuk a forgatott ¨osszeget. V´as´arolhatunk mag´anhangz´ ot. Milyen strat´egi´at v´alasszunk? M´assalhangz´okat gyakoris´aguk alapj´an. J´ol j¨on a nyelvstatisztika. De nem mindig seg´ıt!
9 / 22
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as Alkalmazott statisztika, avagy hogyan nyerj¨ unk a Szerencseker´ ekben?
Tudja?
10 / 22
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as Alkalmazott statisztika, avagy hogyan nyerj¨ unk a Szerencseker´ ekben?
Tudja?
´ A j´ at´ ekos “megfejt´ ese”: TUDJA, HOL SZERET A CAPA
10 / 22
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as
11 / 22
Egy kutat´ asi probl´ ema
V´azlat
1
´ Eletrajzi adatok
2
Alkalmazott statisztika, avagy hogyan nyerj¨ unk a Szerencseker´ekben?
3
Egy kutat´asi probl´ema
4
Tanul´as hib´aval
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as
12 / 22
Egy kutat´ asi probl´ ema
Egy kutat´asi probl´ema (Nemetz) K´odol´as Az u ¨zenetet (nyelvi sz¨ oveg) felbontjuk B hossz´ us´ag´ u blokkokra, az n-edik blokk Mn . A k´odol´as blokkonk´ent: Cn = π(Mn ), ahol π egy titkos permut´aci´o. Feladat N k´odolt blokkb´ol: C1 , . . . , CN , keress¨ uk meg a π permut´aci´ot. Megold´asi ¨otlet M-ben a szomsz´edos bet˝ uk er˝ osen korrell´altak, a t´avoliak f¨ uggetlenek. Minden 1 ≤ i ≤ B-re keress¨ uk meg azt a k-t, amire Prob C -ben az i-edikre k¨ ovetkez˝ o jel a k-adik maxim´alis. Ekkor ha π(j) = i, akkor π(j + 1) = k, amib˝ol π rekonstru´alhat´o.
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as
13 / 22
Egy kutat´ asi probl´ ema
Egy kutat´asi probl´ema (Nemetz) F (a|b) annak val´osz´ın˝ us´ege, hogy az a bet˝ u k¨ovetkezik b ut´an. Annak val´osz´ın˝ us´ege, hogy C n blokkban az i-edikre k¨ovetkez˝o jel a k-adik: F Cn (k)|Cn (i) . Az, blokkban ´ıgy van, ezek szorzata: Q hogy ez mindegyik F C (k)|C (i) . n n n Megval´os´ıt´as Minden i-re v´alasszuk azt a k-t (azokat a k-kat), amire az al´abbi log-likelihood maxim´alis (a legnagyobb ´ert´ekeket veszi fel): N X
log F (Cn (k)|Cn (i) .
n=1
Ebb˝ol rekonstru´aljuk a π permut´aci´ ot.
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as
14 / 22
Egy kutat´ asi probl´ ema
Egy kutat´asi probl´ema (Nemetz)
A probl´em´ak 1
Ha mindegyik permut´aci´ o egyform´an val´ osz´ın˝ u, h´any blokkra van sz¨ uks´eg (N =?) ahhoz, hogy a fenti elj´ar´as egy´ertelm˝ uen megadja π-t a B blokkhossz f¨ uggv´eny´eben tipikus nyelvi sz¨ovegekre, mondjuk 1/2 val´ osz´ın˝ us´eggel?
2
Hogyan befoly´asolja az eredm´enyt, hogy az F (a|b) val´osz´ın˝ us´egekre csak emp´ırikus becsl´eseink vannak?
3
Hogyan lehet a π permut´aci´ ot gyorsan megtal´alni, ha minden i-re t¨obb k-t is figyelembe vesz¨ unk? (Ilyenkor az ¨osszes k val´osz´ın˝ uleg “k¨ozel” lesz i r´ak¨ ovetkez˝ oihez illetve megel˝oz˝oihez.)
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as
15 / 22
Tanul´ as hib´ aval
V´azlat
1
´ Eletrajzi adatok
2
Alkalmazott statisztika, avagy hogyan nyerj¨ unk a Szerencseker´ekben?
3
Egy kutat´asi probl´ema
4
Tanul´as hib´aval
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as
16 / 22
Tanul´ as hib´ aval
A probl´ema
Tanul´as Rn -ben van egy f´elt´er. B´armely x ∈ Rn -re megk´erdezhetj¨ uk, benne van-e, ´es igen/nem v´alaszt kapunk. Tanuljuk meg hol van a f´elt´er. Tanul´as hib´aval A fenti k´erd´esre ε hib´aval kapjuk meg a helyes v´alaszt. Tanuljuk meg hol van a f´elt´er.
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as Tanul´ as hib´ aval
A probl´ema – kriptogr´afiai v´altozat
Tanul´as Van egy ismeretlen s ∈ Fn2 vektor. B´armely x ∈ Fn2 -re megk´erdezhetj¨ uk az hs, xi ∈ {0, 1} skal´aris szorzat ´ert´ek´et. Tal´aljuk meg az s vektort. K¨onny˝ u: n k´erd´es ut´an van egy lin´aris egyenletrendszer¨ unk s-re. Tanul´as hib´aval A fenti k´erd´esre ε hib´aval kapjuk meg a helyes v´alaszt. Tal´aljuk meg az s vektort. c · n k´erd´es ut´an a megold´as egy´ertelm˝ u, de azt hogyan tal´aljuk meg polinom id˝o alatt?
17 / 22
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as
18 / 22
Tanul´ as hib´ aval
Tanul´as hib´aval
Ha a tanul´o x ∈ Fn2 vektorokat egym´ast´ ol f¨ uggetlen¨ ul egyenletes val´osz´ın˝ us´eggel kell v´alasztani: – a feladat exponenci´ alisan neh´ ez. – sz´amos u ´j kriptogr´afiai protokoll haszn´alja (pl. Ajtai Mikl´os legr¨ovidebb r´acsvektort haszn´al´ o protokollja).
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as
18 / 22
Tanul´ as hib´ aval
Tanul´as hib´aval
Ha a tanul´o x ∈ Fn2 vektorokat egym´ast´ ol f¨ uggetlen¨ ul egyenletes val´osz´ın˝ us´eggel kell v´alasztani: – a feladat exponenci´ alisan neh´ ez. – sz´amos u ´j kriptogr´afiai protokoll haszn´alja (pl. Ajtai Mikl´os legr¨ovidebb r´acsvektort haszn´al´ o protokollja). Ha a tanul´o x ∈ Fn2 vektorokat mi v´alaszthatjuk: – az s vektor gyorsan megtal´ alhat´ o (polinom id˝o alatt). – ez a nevezetes Goldreich–Levin t´etel (1989). – Nemetz Tibor a t´etelt m´ar kor´abban ismerte ´es haszn´alta.
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as
19 / 22
Tanul´ as hib´ aval
Visszavezet´es Az x k´erd´esre a (nem felt´etlen¨ ul helyes) v´alaszt A(x) jel¨oli. M´odos´ıtott feladat: Legyen v egy v´eletlen vektor; hat´arozzuk meg az A(x) v´alaszokb´ol (nagy val´osz´ın˝ us´eggel) az hs, vi szorzat ´ert´ek´et! V´eletlen¨ ul v´alasztott line´arisan f¨ uggetlen vi vektorokra elegend˝oen 3 nagy (p´eld´aul > 1 − 1/n ) val´ osz´ın˝ us´eggel megkeress¨ uk az hs, vi i szorzatok ´ert´ek´et. Innen a hs, v1 i = b1 hs, v2 i = b2 ... hs, vn i = bn line´aris egyenletrendszer megold´asa megadja az ismeretlen s vektort.
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as
20 / 22
Tanul´ as hib´ aval
Hat´arozzuk meg hs, vi ´ert´ek´et! Legyenek a1 , a2 , . . . , ak v´eletlen vektorok (k kicsi) ´es tegy¨ uk fel hogy az hs, ai i = ai ´ert´ekeket tudjuk. P P Mivel hs, v + i λi ai i = hs, vi + i λi hs, ai i, az´ert az hs, vi ´ert´ek´et becs¨ ulhetj¨ uk ´ıgy: P P A v + i λi ai − i λi ai : λi ∈ {0, 1} , ahol mindegyik becsl´es hib´aja ε. Legyen hs, vi-t az (1) alatti 2k darab 0/1-b˝ol a t¨obbs´eg.
(1)
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as
20 / 22
Tanul´ as hib´ aval
Hat´arozzuk meg hs, vi ´ert´ek´et! Legyenek a1 , a2 , . . . , ak v´eletlen vektorok (k kicsi) ´es tegy¨ uk fel hogy az hs, ai i = ai ´ert´ekeket tudjuk. P P Mivel hs, v + i λi ai i = hs, vi + i λi hs, ai i, az´ert az hs, vi ´ert´ek´et becs¨ ulhetj¨ uk ´ıgy: P P A v + i λi ai − i λi ai : λi ∈ {0, 1} ,
(1)
ahol mindegyik becsl´es hib´aja ε. Legyen hs, vi-t az (1) alatti 2k darab 0/1-b˝ol a t¨obbs´eg. Az (1) alatti becsl´esek p´ aronk´ ent f¨ uggetlenek, Csebisev szerint a hiba val´osz´ın˝ us´ege legfeljebb
2ε(1 − ε) . (1 − 2ε)2k
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as Tanul´ as hib´ aval
¨ Osszefoglal´ as
Az elj´ar´as Legyen k = 3 log n. V´alasszunk k v´eletlen vektort: a1 , . . . , ak Megtippelj¨ uk az hs, ai i ´ert´ekeket (2k = n3 lehet˝os´eg) Adott tipp mellett kisz´am´ıtjuk hs, vi i ´ert´ek´et (minden i-re 2k k´erd´es ´es ≤ 1/2k hiba) A kapott vi -kb˝ol kisz´am´ıtjuk s-et. Ellen˝orizz¨ uk, hogy a kapott s ´ert´ek j´ o-e (tov´abbi n k´erd´es). Mivel valamelyik tipp j´ o, O(n6 ) k´erd´essel 1/n2 -n´el kisebb hib´aval megkapjuk a keresett s-et.
21 / 22
Adatbiztons´ ag ´ es val´ osz´ın˝ us´ egsz´ am´ıt´ as Tanul´ as hib´ aval
K¨ osz¨ on¨ om a figyelmet!
22 / 22
