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

5. Hatékonyság

5. Hatékonyság

Felmerül a kérdés, hogy ha egy hozzáférési rendszerhez több perfekt titokmegosztás is megadható, akkor melyik a legjobb. Az előbbi fejezetekben többször utaltunk erre a kérdésre, megpróbáltunk egy első megközelítést nyújtani. Mit is jelent és miért lényeges a hatékonyság? Tegyük fel, hogy a résztvevők képtelenek 10 számjegynél többet fejben tartani. Egy olyan titokmegosztási protokoll, ahol a kulcs számjegyeinek száma megegyezik a részletek számjegyeinek számával, ezen feltétel mellett egy 10 számjegyű titkot tud megosztani. Ezt próbálkozással kitalálni elég reménytelen. Azonban egy olyan, kevésbé hatékony rendszerrel, ahol a részletek ötször hosszabbak a kulcsnál, csak egy 2 számjegyű kulcs titkosítható. Mindkét titokmegosztás során kihasználjuk a részletek hosszának felső korlátját, az utóbbi mégis alkalmatlan a megvalósításra, mert egy 2 számjegyű titok könnyedén feltörhető. Úgy mondhatjuk, hogy a „titkosítási hatásfok”, a hatékonyság itt csak 1 5 , mert a 10 megjegyeznivaló számjegy csak 2-t titkosított. Alább belátjuk azt a kellemetlen tényt, hogy a részleteknél hosszabb titkot perfekt módon megosztani lehetetlen, azaz a hatékonyság, akár a hatásfok a fizikában legfeljebb 1 lehet.

A hatékonyságra a következő mértékszámot vezették be: Tegyük fel, hogy ? -n megadtunk egy perfekt titokmegosztást, melyben K a lehetséges kulcsok halmaza. Legyen P = { p 1 , p 2 , , p n } , és jelölje S ( p i ) ( 1 ? i ? n ) a p i résztvevő lehetséges részleteinek halmazát (az összes lehetséges szétosztást figyelembe véve). Ekkor a p i résztvevő információs rátája:

? i = log 2 K log 2 S ( p i ) .

A tört számlálója a kulcs kettes számrendszerbeli számjegyeinek száma, a nevező pedig a résztvevő részletének számjegyeinek száma. A hányados tehát azt méri, hogy a kulcs hossza hogyan aránylik a megjegyeznivaló hosszához. Ez az arány résztvevőnként más és más lehet, minél nagyobb, annál hatékonyabb a titokmegosztás az adott résztvevő szemszögéből. A legrosszabb, azaz a legkisebb eredményt tekintjük az egész protokoll hatékonyságának: a titokmegosztás információs rátája ? = min { ? i 1 ? i ? n } . (A logaritmus alapjának, azaz a kettes számrendszernek természetesen nincs kitüntetett szerepe.)

Végiggondoljuk, hogy bármely struktúrában S ( p i ) ? K , így ? i ? 1 minden résztvevőre, tehát ? ? 1 is fennáll. Legyen B ? ? 0 , p i ? B tetszőleges. Ekkor a B ' = B \ { p i } csoport már nem felhatalmazott csoport, a kulcsról semmilyen új információt nem tudhatnak meg, azaz az összes lehetséges szétosztásuknak az összes kulcs résztáblázatában szerepelnie kell. A p i résztvevővel együtt azonban már egyértelműen meghatározhatják a kulcsot, tehát különböző kulcs táblázatában B ' -nek ugyanahhoz a szétosztásához p i részletének különböznie kell. Így valóban teljesül, hogy S ( p i ) ? K . (Itt hallgatólagosan felhasználtuk azt a természetes feltevést, hogy minden résztvevő tagja legalább egy minimálisan felhatalmazott csoportnak.)

Természetesen egy titokmegosztás annál hatékonyabb, minél közelebb van az információs rátája a felső korláthoz, az 1-hez. Ha ? = 1 , akkor a titokmegosztást ideálisnak nevezzük.

Vizsgáljuk meg az eddig leírt konstrukciókat hatékonysági szempontból.

1. Shamir titokmegosztási protokolljában a titok és a részletek is F p -beli számok, így ez K = S ( p i ) = F p miatt mindig ideális, de csak a küszöbrendszerekre ad megoldást. A 3.1. példa megoldása így ideális.

2. Az Ito–Saito–Nishizeki és a Benaloh–Leichter konstrukciók általánosak, de általában nem túl hatékonyak.

A 2.1. példa megoldásában K = 2 és S ( p i ) = 4 , tehát ? i = 1 2 ( 1 ? i ? 4 ); ? = 1 2 .

A 2.2. példa megoldásában K = 2 és S ( p 1 ) = S ( p 4 ) = 4 , S ( p 2 ) = S ( p 3 ) = 8 , tehát ? 1 = ? 4 = 1 2 , ? 2 = ? 3 = 1 3 ; ? = 1 3 .

3. A Martin–Jachson–O’Keefe-modell esetén z ? k ? P -re z ^ egy d z -dimenziós altér az e 1 , e 2 , , e d z bázissal. Ahogy v végigfut V p d elemein, úgy az ( e 1 · v , , e d z · v ) szám d z -es is végigfut az összes lehetséges szám d z -esen (mindegyiket p d - d z -szer veszi fel). Tehát S ( z ) = p d z , így

? i = log 2 p dim k ^ log 2 p dim p ^ i = dim k ^ dim p ^ i .

Akkor lesz ideális a rendszer, ha dim k ^ = dim p ^ i minden 1 ? i ? n esetén. A 4.1. példa megoldása tehát ideális (ami az elkészített táblázatból is leolvasható).

(A három utóbbi példa mindegyike ugyanavval a hozzáférési struktúrával dolgozik. Íme, számosítottuk a három különböző konstrukció eddig is jelzett hatékonysági különbözőségét.)

További példaként egy hatékonysági felső becslést említünk. A hozzáférési rendszer izomorf egy gráffal, ha a felhatalmazott csoportok kételeműek. (A gráf csúcsainak a résztvevők, éleinek a felhatalmazott csoportok felelnek meg.) Ha ez a gráf G l 1 , , l r teljes többszínű gráf (azaz csúcsai besorolhatók r db l 1 , , l r méretű partícióba, melyekre igaz, hogy pontosan a különböző partíciójú csúcsokat köti össze él), akkor könnyen felállítható hozzá ideális titokmegosztás. Adjunk meg az r darab partíción egy ( 2 , r ) -küszöbrendszert, és a partíciók részletét osszuk ki a partícióban lévő csúcsokhoz (azaz résztvevőkhöz).

Példa (5.1)

P = { p 1 , p 2 , p 3 , p 4 } , ? 0 = p 1 p 2 + p 1 p 3 + p 1 p 4 + p 2 p 4 + p 3 p 4 ? G 1 , 1 , 2 .

2. ábra.

Legyen a ( 2 , 3 ) -küszöbrendszerben l i részlete s i ( 1 ? i ? 3 ). Ekkor a résztvevők az alábbi adatokat kapják: p 1 s 1 , p 2 s 2 , p 3 s 2 , p 4 s 3 . ?

Azonban minden egyéb összefüggő gráffal izomorf struktúra esetén a titokmegosztás információs rátájára fennáll, hogy ? ? 2 3 . Ezt az érdekes eredményt az információelméleti entrópia segítségével bizonyították.

Példa (5.2)

P = { p 1 , p 2 , p 3 , p 4 } , ? 0 = p 1 p 2 + p 2 p 3 + p 3 p 4 .

A 4.1. példában leírt Fano-síkon megadhatunk egy véges geometriai titokmegosztást:

Legyen p ^ 1 = C , p ^ 2 = A F B , p ^ 3 = A E C , p ^ 4 = B , k ^ = G . Ennek információs rátája ? = 1 2 , mivel az altér-konfigurációban két résztvevőhöz 2-dimenziós alteret, a kulcshoz viszont 1-dimenziós alteret rendeltünk.

Mivel a hozzáférési struktúra egy összefüggő, de nem teljes többszínű gráffal izomorf (lásd a következő példát), nem adható meg hozzá ideális titokmegosztás. Az itt leírtnál azonban létezik hatékonyabb. (Elérhető a ? = 2 3 -os felső korlát.)

3. ábra.

A következő táblázat összefoglalja a legfeljebb négy résztvevős nem triviális rendszereket, megadva a hozzájuk konstruálható leghatékonyabb titokmegosztás információs rátáját a negyedik oszlopban.

n

? 0

?

Megjegyzés

1.

2

p 1 p 2

1

(2,2)-küszöbrendszer

2.

3

p 1 p 2 + p 2 p 3

1

? 0 ? G 1 , 2

3.

3

p 1 p 2 + p 2 p 3 + p 1 p 3

1

(2,3)-küszöbrendszer

4.

3

p 1 p 2 p 3

1

(3,3)-küszöbrendszer

5.

4

p 1 p 2 + p 2 p 3 + p 3 p 4

2/3

6.

4

p 1 p 2 + p 2 p 3 + p 1 p 4

1

? 0 ? G 1 , 3

7.

4

p 1 p 2 + p 1 p 4 + p 2 p 3 + p 3 p 4

1

? 0 ? G 2 , 2

8.

4

p 1 p 2 + p 2 p 3 + p 2 p 4 + p 3 p 4

2/3

9.

4

p 1 p 2 + p 1 p 3 + p 1 p 4 + p 2 p 3 + p 2 p 4

1

? 0 ? G 1 , 1 , 2

10.

4

p 1 p 2 + p 1 p 3 + p 1 p 4 + p 2 p 3 + p 2 p 4 + p 3 p 4

1

(2,4)-küszöbrendszer

11.

4

p 1 p 2 p 3 + p 1 p 4

1

12.

4

p 1 p 2 + p 2 p 3 + p 1 p 3 p 4

2/3

13.

4

p 1 p 2 + p 1 p 3 + p 1 p 4 + p 2 p 3 p 4

2/3

14.

4

p 1 p 2 p 3 + p 1 p 2 p 4

1

15.

4

p 1 p 2 p 4 + p 1 p 3 p 4 + p 2 p 3

1

16.

4

p 1 p 2 p 3 + p 1 p 2 p 4 + p 1 p 3 p 4

1

17.

4

p 1 p 2 p 3 + p 1 p 2 p 4 + p 1 p 3 p 4 + p 2 p 3 p 4

1

(3,4)-küszöbrendszer

18.

4

p 1 p 2 p 3 p 4

1

(4,4)-küszöbrendszer

Ellenőrizze a kedves olvasó, hogy a 2.1., 2.2. és a 4.1. példák alaposan kidolgozott hozzáférési struktúrája a 15. sorban áll, a 4.2. példa a 13. sorban, az 5.2. példa pedig az 5. sorban található. A megjegyzéseknek a cikkben leírtakkal való összekapcsolása, és az alábbi ötödik feladat megoldása után csak az 5., 8., 12. és 13. sorban álló struktúrák kérdésesek. Bebizonyítható, hogy ezekhez a megadott 2 / 3 -nál nagyobb hatékonyságú titokmegosztás nem konstruálható. (Az idevonatkozó tételnek a következménye a gráffal izomorf struktúrákra említett azonos eredmény.) Azonban ennek a felső határnak az elérése sem triviális. Az [1] könyv 11.8. fejezetében megtalálható egy megfelelő konstrukció leírása.