Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

Titokmegosztás

Titokmegosztás

Schmidt, Edit


1. Bevezetés

X úr egy szigorú családfő népes famíliájában. A csokoládékészletet egy fiókban tartja elzárva, melynek zárját egy 0-s vagy egy 1-s kódszámjegy nyitja. A kulcsot (a kódszámjegyet) csak ő ismeri és senkinek eszébe sem jutna próbálkozni a feltörésével. Egy idő után azonban az anyuka és a nagypapa is jogot szeretne kapni a ritka édességosztás lehetőségére. A családfő úgy látja biztonságosnak, ha ők csak ketten együtt férhetnek hozzá a fiók tartalmához. Hogyan tudná elérni ezt?

X úr egy titokmegosztási problémával szembesült, de szerencsére ennek megoldása még nem túl bonyolult. Próbálkozzon a kedves olvasó egy olyan megoldással, melynek során a férj súg egy-egy szót a feleségének és az édesapjának is, amiből ők külön-külön nem, de együttesen megállapíthatják, hogy a kulcs értéke (azaz a „titok”) 0 vagy 1! (Ehhez persze szükségük van a szabályra, ami szerint a titokmegosztás történt.) Bonyolódik a helyzet, ha X úr a család egyéb megbízható csoportjainak is ilyesféle együttes jogosultságot szeretne adni. A tanulság: tökéletesen bizalmatlannak lenni, vagy mindenkiben maximálisan megbízni egyszerűbb volna. Van azonban egy másik út is: megismerkedni a titokmegosztás matematikájával.

A titokmegosztás alapszituációja a következő: adottak résztvevők és egy titok (vagy másképpen kulcs), melyet a résztvevők között úgy kívánunk megosztani (vagyis szétteríteni), hogy csak az erre előre kijelölt (felhatalmazott) csoportjaik tudják a saját részleteikből közösen meghatározni az értékét. Ezen matematikai megoldásokban mind a titok, mind a kiosztott részletek számok lesznek.

Gyakorlati alkalmazásként megemlíthetők a következők:

1. Egy cég széfjének kinyitására vezető beosztású dolgozók különféle csoportjai legyenek alkalmasak, feltéve, hogy a csoport minden tagja jelen van. A felhatalmazott csoportok összetétele tetszőleges, a cég igazgatótanácsa határozza meg. (Egy vezető több ilyen csoporthoz is tartozhat.) A titok a széf zárjának kódja.

2. Egy valós alkalmazás Oroszországban a nukleáris fegyverek feletti kontroll: elindításukra három jogi személy (az elnök, a védelmi miniszter és a védelmi minisztérium) közül legalább kettő ebbéli akarata szükséges (azaz bármely kettő közös szándékkal meg tudja határozni a rakéta indítókódját). Hasonló rendszer működött az Egyesült Államokban is.

Megadjuk, és a továbbiakban alkalmazni is fogjuk az (angol nyelvű) irodalomban használt elnevezéseket és jelöléseket.

Az n darab résztvevőt p 1 , p 2 , , p n fogja jelölni, halmazukat pedig P .

Hozzáférési struktúrának hívjuk és ? -val jelöljük a P felhatalmazott részhalmazainak halmazát. Egy résztvevőcsoport akkor tartozik a ? elemei közé, ha jogosult a titok meghatározására. (Tehát a ? struktúra előre adott.) Értelemszerűen feltesszük, hogy ha egy csoport felhatalmazott csoport, akkor az összes bővítményei is ilyenek, hiszen új tagok csatlakozása nem változtat azon a tényen, hogy a kiinduló csoport jogosult a titok felfedésére. Ezen tulajdonsága miatt ? egyértelműen leírható azokkal a felhatalmazott csoportokkal, melyek már sehogy sem csökkenthetők úgy, hogy a maradék tagok is felhatalmazott csoportot alkossanak. Az ilyen minimális csoportokat a ? 0 halmazrendszerben adjuk meg. Tehát a ? a ? 0 elemeiből és azoknak az összes lehetséges bővítményeiből álló halmaz.

D -vel fogjuk jelölni az irányítót, aki kiosztja a részleteket. Természetesen D ismeri magát a titkot, így tökéletesen megbízhatónak kell lennie. Lehet például a fent említett cégnek a tulajdonosa, aki egymaga is hozzáférhet a széfben őrzött értékekhez. Vagy elképzelhetjük egy számítógépes programként, mely megsemmisíti önmagát, miután kiosztotta a részleteket. Az alább ismertetendő titokmegosztási eljárások mindegyikét egy ilyen megbízható irányító vezeti le. Született megoldás az irányító nélküli titokmegosztásra is, azonban az kissé bonyolultabb ezeknél.

Példa (1.1)

1. Adjuk meg a hozzáférési struktúráját az alábbi szituációnak: egy cég bankban lévő széfjének kinyitásához a cég két igazgatója közül legalább az egyiknek, illetve a bankigazgatónak jelenléte szükséges. Legyenek P = { p 1 , p 2 , p 3 } , ahol p 1 , p 3 a két cégigazgató és p 2 a bankigazgató. Ekkor a feltételeknek megfelelően a minimális felhatalmazott csoportok: ? 0 = { { p 1 , p 2 } { p 2 , p 3 } } . (Ez utóbbira használatos a ? 0 = p 1 p 2 + p 2 p 3 jelölés is. A további példákban ezt a jelölésmódot használjuk.) Végül ? = ? 0 ? { p 1 , p 2 , p 3 } , azaz ? = p 1 p 2 + p 2 p 3 + p 1 p 2 p 3 .

A P -nek ? -ban fel nem sorolt részhalmazai

( Ø , { p 1 } , { p 2 } , { p 3 } , { p 1 , p 3 } )

a nem felhatalmazott csoportok.

2. Legyen most P = { p 1 , p 2 , , p n } , tehát P = n . A későbbiekben használni fogjuk a ( t , n ) -küszöbrendszer elnevezést. Ez egy olyan hozzáférési struktúra, ahol az n résztvevőnek minden legalább t tagú csoportja (ahol 1 ? t ? n ) felhatalmazott, azaz ? = { B B ? P , B ? t } . Ekkor azok lesznek a minimálisan felhatalmazott csoportok, amelyek éppen t eleműek: ? 0 = { B B ? P , B = t } .

Ez a struktúra demokratikus, a résztvevők egyenrangúak. Az esetleges visszaélések elkerülése céljából érdemes a példa szerint megkívánni a titok értékének meghatározásához több (legalább t számú) résztvevő együttes szándékát. ?

Ezek után újra (precízebben) megfogalmazzuk a feladatot: A ? hozzáférési struktúra egy perfekt titokmegosztásán egy protokollt értünk, amelyben minden résztvevő kap egy vagy több részletet úgy, hogy

(1) a felhatalmazott csoportok ( A ? P , A ? ? ) meghatározhassák a kulcsot együttesen a részleteikből;

(2) a nem felhatalmazott csoportok ( A ? P , A ? ? ) pedig – akár leleplezvén egymás előtt saját részleteiket – semmi újat ne állapíthassanak meg a kulcsról azon kívül, ami nyilvános. (A protokoll rendszere, a lehetséges kulcsok és részletek értékei nyilvánosak, a konkrét titok és a kiosztott részletek titkosak.)

A (2) feltétel szerint tehát hiába szervezkednek a titok megszerzéséért erre nem felhatalmazott csoportok, nemcsak hogy nem tudják meghatározni azt, de még csak közelebb sem kerülhetnek céljukhoz. Ennek pontosabb megfogalmazása a feltételes valószínűség felhasználásával történhet. (Semelyik lehetséges kulcs nem válik valószínűbbé vagy kevésbé valószínűvé egy nem felhatalmazott csoport összebeszélése után, mint előtte volt a struktúra ismeretéből adódóan.)

Példa (1.2)

X úr titokmegosztási problémájában maga X úr az irányító. A résztvevők száma 2, és ketten együtt alkotnak felhatalmazott csoportot. A fenti jelölésekkel: P = { p 1 , p 2 } és ? 0 = ? = p 1 p 2 . Ez a hozzáférési struktúra éppen a ( 2 , 2 ) -küszöbrendszer. Ehhez a struktúrához perfekt titokmegosztást például az alábbi módon adhatunk. Amennyiben a kulcs értéke 0, akkor X úr azonos szót súg részletként a két résztvevőnek, ellenkező esetben különbözőt. (A kulcs lehetséges értékeit és a súgás szabályát előtte „nyilvánossá teszi”.) Hogy a kiosztott részletek is számok legyenek, X úr a 0 vagy az 1 „szavakat” súgja. Foglaljuk táblázatba a lehetőségeket:

k p 1 p 2 0 0 0 0 1 1 1 0 1 1 1 0

Ez a titokmegosztás megfelel a leírt követelményeknek. Az anyuka és a nagypapa együtt meg tudják határozni a kulcsot, de a saját részletükkel egyedül semmire sem jutnak, hiszen éppen a két részlet azonossága vagy különbözősége hordozza az információt. Mivel társuk részletét ugyanakkora (50%) eséllyel tudnák megtippelni, mint magát a kulcsot (márpedig erre nem vetemednek), ezért a saját részletük birtokában semmi újat nem tudnak meg róla. ?

Ebben a példában megalkottunk ugyan egy perfekt titokmegosztást, de ennek jelentősége természetesen csak elméleti. A titok értékének tippeléssel való meghatározása túl nagy valószínűségű, ezért a gyakorlatban (X úr családját kivéve) megvalósíthatatlan. Fontos lenne, hogy a kulcs lehetséges értékeinek számát növeljük, hogy ezáltal a tippelési kedv csökkenjen. Fogalmazzuk át a táblázatban megadott titokmegosztás képzési szabályát ekképpen: ha a két részletet modulo 2 összeadjuk, akkor éppen a kulcsot kapjuk. Vegyük észre, hogy ha a szisztéma megtartása mellett a lehetséges részletek, illetve kulcsok halmazát { 0 , 1 } -ről { 0 , 1 , , m - 1 } -re bővítjük, és modulo m számolunk, akkor evvel szintén egy perfekt titokmegosztást adunk meg. Mindkét résztvevő tudja, hogy a titok a { 0 , 1 , , m - 1 } számok valamelyike, akárcsak a saját és a társa részlete. Ha összefognak, akkor a részleteik összeadásával megkapják a kulcsot, de az összeg egyik tagjából semmire sem tudnak következtetni a másik hiányában. (Bármely kulcs lehetséges, amennyiben a társ részlete éppen a feltételezett szám és a saját részlet különbsége modulo m .) Ha m -et elég nagyra választjuk, akkor a tippelési valószínűség kicsi lesz (pl. m = 1000 esetén 0,1 %).

Teljesen hasonlóan felépíthető az általános ( n , n ) -küszöbrendszer, ahol tehát csak az n résztvevő együtt alkot felhatalmazott csoportot: P = { p 1 , p 2 , , p n } ; p 1 részlete x 1 , p 2 részlete x 2 , …, p n részlete x n , x i ? { 0 , 1 , , m - 1 } minden 1 ? i ? n esetén, és m //>// 1 tetszőleges egész; végül k = ( x 1 + x 2 + + x n mod m ) .

Ez m n lehetséges kiosztás, és valóban perfekt, mert bármely n - 1 résztvevő összeállva semmit nem tud az n -edik résztvevő részletéről, így a kulcsról sem, azonkívül, hogy ezek értéke is a 0, 1, …vagy m - 1 számok valamelyike. (Mondhatjuk úgy is, hogy a részletek és a kulcs is Z m -beli számok és a művelet a Z m -beli összeadás.)

Természetesen a tényleges megvalósításkor a kulcs értéke (általában) előre adott, s eszerint kell kiosztani a részleteket. A megfelelő protokoll:

1. D választ n - 1 db tetszőleges értéket Z m -ben, legyenek ezek x 1 , x 2 , , x n - 1 .

2. Legyen a kulcs k ? Z m . Ekkor a szétosztás:

p 1 x 1 , p 2 x 2 , , p n - 1 x n - 1 , p n k - ( x 1 + x 2 + ? + x n - 1 ) .

(A p x jelöli, hogy a p résztvevő az x részletet kapja. A számolás Z m -ben, azaz modulo m történik.)

Nyilvánvalóan a résztvevők sorrendiségének semmi szerepe nincs. Könnyen végiggondolható a precíz bizonyítás, miszerint ez a titokmegosztás perfekt.

A megvalósításkor érdemes az összes lehetséges szétosztást a kulcs szerint előre táblázatba rendezni, amint azt az 1.2. példában tettük. A táblázat oszlopai a kulccsal, illetve a résztvevőkkel vannak címkézve, a sorok pedig egy-egy konkrét szétosztásnak felelnek meg. Az irányító kiválasztja a titok értékét, majd az ennek megfelelő résztáblázatból véletlenszerűen az aktuális szétosztást, azaz annak egy sorát. Ez azért előnyös, mert a csoportoknak akcióik során nem kell ismerniük a matematikai hátteret, és esetleg bonyolult számításokat végezniük a titok meghatározásához.

Példa (1.2)

A ( 3 , 3 ) -küszöbrendszer táblázatolása Z m = Z 3 mellett (a kulcsok szerint csoportosítva):

k = 0 k = 1 k = 2 p 1 p 2 p 3 p 1 p 2 p 3 p 1 p 2 p 3  0   0   0  0 1 2 0 2 1 1 0 2 1 1 1 1 2 0 2 0 1 2 1 0 2 2 2  0   0   1  0 1 0 0 2 2 1 0 0 1 1 2 1 2 1 2 0 2 2 1 1 2 2 0  0   0   2  0 1 1 0 2 0 1 0 1 1 1 0 1 2 2 2 0 0 2 1 2 2 2 1 ?

Ilyen értelemben a szétosztás akkor perfekt, ha

(1) a felhatalmazott csoportok ( A ? P , A ? ? ) akciója esetén a táblázatnak csak egyetlen kulcsnak megfelelő résztáblázatában van olyan sor, melyben a csoport tagjai az aktuális részletekkel bírnak;

(2) a nem felhatalmazott csoportok ( A ? P , A ? ? ) próbálkozása esetén a táblázatnak minden kulcsnak megfelelő résztáblázatában van olyan sor, melyben a csoport tagjai az aktuális részletekkel bírnak (az erősebb értelemben vett definíció szerint minden kulcshoz pontosan ugyanannyi).