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

2. Konstrukciók tetszőleges hozzáférési rendszer esetére

2. Konstrukciók tetszőleges hozzáférési rendszer esetére

Ha a kérdések felvetésének időrendi sorrendjét követnénk, akkor ebben a fejezetben Shamir konstrukcióját írnánk le, melyet a ( t , n ) -küszöbrendszerhez adott meg (bármely t ? n esetére). Mivel azonban felsőbb matematikai ismeretek is szükségesek a megértéséhez, didaktikai szempontok alapján az általánosabb megoldásokat mutatjuk be előbb. Így ebben a fejezetben két olyan konstrukciót adunk meg, melyek tetszőleges hozzáférési rendszerhez perfekt titokmegosztást hoznak létre. Mindkettő teljesen elemi, csak az előző fejezetben bemutatott ( n , n ) -küszöbrendszert és a halmazelmélet alapfogalmait használják.

Benaloh és Leichter konstrukciója (1990)

A konstrukció azon a két igényen alapul, hogy a minimálisan felhatalmazott ( ? 0 -beli) csoportokon belül a résztvevők „egyenrangúak és pótolhatatlanok”; illetve, hogy egy általános csoport pontosan akkor van felhatalmazva, ha bővítménye bármelyik ilyen minimális csoportnak. Az első követelménynek eleget teszünk, ha a ? 0 -beli csoportokon belül ( a , a ) -küszöbrendszert hozunk létre (ahol a a csoport létszáma), a másodiknak pedig akkor, ha egy résztvevő több részletet is kap (kaphat), nevezetesen megkap minden olyan ? 0 -beli csoporton létrehozott szétosztásból egy részletet, amely csoportoknak tagja.

A megfelelő küszöbrendszerek létrehozásához szükségünk van a ? 0 -beli csoportok méretére (azaz lélekszámára). Legyen mondjuk r darab ? 0 -beli csoport: ? 0 = C 1 + C 2 + + C r , és C 1 = a 1 , C 2 = a 2 , …, C r = a r .

A protokoll:

1. D a C 1 halmazon létrehoz az adott kulcshoz egy ( a 1 , a 1 ) -küszöbrendszert, s ennek részleteit (tetszőleges sorrendben) kiosztja a C 1 csoport résztvevői között.

2– r . Ezek után D végrehajtja ugyanezt a többi C i ( 2 ? i ? r ) halmazon is: létrehoz (ugyanahhoz a kulcshoz, de egymástól függetlenül) egy-egy ( a i , a i ) -küszöbrendszert, s ezek részleteit is kiosztja a C i csoport tagjai között.

Fontos, hogy a többrészletes résztvevők tudják, hogy melyik részletet melyik csoportban való tagságuk miatt kapták. Képzelhetjük úgy is, hogy minden felhatalmazott csoportnak van egy színe, s ezzel a színnel kapják meg a tagok a részleteiket. Kevésbé színesen eljárhatunk úgy, mint az alábbi példában.

Példa (2.1)

Legyen például P = { p 1 , p 2 , p 3 , p 4 } , ? 0 = p 1 p 2 p 4 + p 1 p 3 p 4 + p 2 p 3 . Ekkor C 1 = p 1 p 2 p 4 , a 1 = 3 ; C 2 = p 1 p 3 p 4 , a 2 = 3 ; C 3 = p 2 p 3 , a 3 = 2 .

Rögzítünk egy tetszőleges Z m számkört ( m //>// 1 egész), s az alábbi számokat innen választjuk, a műveleteket ebben végezzük (modulo m ). Legyen a titok értéke k . A részleteket s betűvel jelöljük, és két indexszel különböztetjük meg őket. Az első index a csoport „színére” (azaz sorszámára) utal, a másodikkal pedig az egyforma színű részleteket különböztetjük meg. A protokoll lépéseit követve:

  1. A C 1 halmazon létrehozott ( 3 , 3 ) -küszöbrendszer részletei legyenek (az előző fejezetben leírtak szerint): s 1 , 1 , s 1 , 2 , k - s 1 , 1 - s 1 , 2 .

  2. A részletek szétosztása: p 1 s 1 , 1 , p 2 s 1 , 2 , p 4 k - s 1 , 1 - s 1 , 2 .

  3. A C 2 halmazon létrehozott ( 3 , 3 ) -küszöbrendszer részletei legyenek hasonlóan: s 2 , 1 , s 2 , 2 , k - s 2 , 1 - s 2 , 2 ;

  4. szétosztásuk: p 1 s 2 , 1 , p 3 s 2 , 2 , p 4 k - s 2 , 1 - s 2 , 2 .

  5. A C 3 halmazon létrehozott ( 2 , 2 ) -küszöbrendszer részletei legyenek: s 3 , 1 , k - s 3 , 1 .

  6. A részletek szétosztása: p 2 s 3 , 1 , p 3 k - s 3 , 1 .

Végül összesítve a résztvevők által kapott részleteket:

p 1 s 1 , 1 , s 2 , 1 ; p 2 s 1 , 2 , s 3 , 1 ; p 3 s 2 , 2 , k - s 3 , 1 ; p 4 k - s 1 , 1 - s 1 , 2 , k - s 2 , 1 - s 2 , 2 .

Mint látjuk, ebben a struktúrában mindegyik résztvevő két részletet kap.

Megadunk egy konkrét példát is:

Ha például a számkör a Z 4 , k = 3 , s 1 , 1 = 0 , s 1 , 2 = 2 , s 2 , 1 = 3 , s 2 , 2 = 0 , s 3 , 1 = 1 , akkor a részletek: p 1 0 , 3 ; p 2 2 , 1 ; p 3 0 , 2 ; p 4 1 , 0 . ?

Miért perfekt ez a titokmegosztás? Bármelyik felhatalmazott csoport összegyűjtvén részleteiket, (legalább) az egyik küszöbrendszer minden részletét megkapják (hiszen csoportjuk legalább egy C i csoportnak bővítménye), s így meg tudják határozni a titok értékét. (Mint már írtuk, a résztvevők tudják, hogy az adott csoportban melyik („színű”) részletüket kell használniuk.) A fel nem hatalmazott csoportoknak viszont mindegyik ( a i , a i ) -küszöbrendszerhez hiányozni fog részlet, hiszen egyik C i csoportnak sem bővítményei. A különböző küszöbrendszerek egymástól független létrehozása miatt a részleteik összessége is alkalmatlan lesz a titok értékének meghatározására.

Például a B = { p 1 , p 3 } együttes adatai: s 1 , 1 , s 2 , 1 , s 2 , 2 , k - s 3 , 1 nem elegendőek a k kiszámításához, de ha p 4 is beszáll, akkor s 2 , 1 , s 2 , 2 , k - s 2 , 1 - s 2 , 2 alkalmasak lesznek. ?

Ebben az esetben a lehetséges kiosztások száma minden kulcshoz m 5 , mert öt érték szabadon választható ( s 1 , 1 , s 1 , 2 , s 2 , 1 , s 2 , 2 , s 3 , 1 ? Z m ). Ha például m = 2 , akkor mindkét kulcshoz 32 sor tartozik a táblázatban. Amennyiben a titokmegosztás a táblázat alapján (matematikai háttér nélkül) történik, akkor a résztvevők egy-egy rendezett számpárt kapnak részletként.

k s 1 , 1 s 1 , 2 s 2 , 1 s 2 , 2 s 3 , 1 p 1 p 2 p 3 p 4 0 0 0 0 0 0 00 00 00 00 0 0 0 0 0 1 00 01 01 00 0 0 0 0 1 0 00 00 10 01 0 0 0 0 1 1 00 01 11 01 0 1 1 1 1 1 11 11 11 00 1 0 0 0 0 0 00 00 01 11 1 0 0 0 0 1 00 01 00 11 1 0 0 0 1 0 00 00 11 10 1 0 0 0 1 1 00 01 10 10 1 1 1 1 1 1 11 11 10 11 ? \[ {\setlength{\arraycolsep}{5pt}\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \multicolumn{1}{c}{k}//&//\multicolumn{1}{c}{ {s}_{1,1}}//&//\multicolumn{1}{c}{ {s}_{1,2}}//&//\multicolumn{1}{c}{ {s}_{2,1}}//&//\multicolumn{1}{c}{ {s}_{2,2}}//&//\multicolumn{1}{c}{ {s}_{3,1}}//&//\multicolumn{1}{c}{ {p}_{1}}//&//\multicolumn{1}{c}{ {p}_{2}}//&//\multicolumn{1}{c}{ {p}_{3}}//&//\multicolumn{1}{c}{ {p}_{4}}\\ \hline 0//&// 0//&// 0//&// 0//&// 0//&// 0//&// 00//&// 00//&// 00//&// 00\\ \hline 0//&// 0//&// 0//&// 0//&// 0//&// 1//&// 00//&// 01//&// 01//&// 00\\ \hline 0//&// 0//&// 0//&// 0//&// 1//&// 0//&// 00//&// 00//&// 10//&// 01\\ \hline 0//&// 0//&// 0//&// 0//&// 1//&// 1//&// 00//&// 01//&// 11//&// 01\\ \hline \dots //&// //&// //&// //&// //&// //&// //&// //&// //&// \dots \\ \hline 0//&// 1//&// 1//&// 1//&// 1//&// 1//&// 11//&// 11//&// 11//&// 00\\ \hline 1//&// 0//&// 0//&// 0//&// 0//&// 0//&// 00//&// 00//&// 01//&// 11\\ \hline 1//&// 0//&// 0//&// 0//&// 0//&// 1//&// 00//&// 01//&// 00//&// 11\\ \hline 1//&// 0//&// 0//&// 0//&// 1//&// 0//&// 00//&// 00//&// 11//&// 10\\ \hline 1//&// 0//&// 0//&// 0//&// 1//&// 1//&// 00//&// 01//&// 10//&// 10\\ \hline \dots //&// //&// //&// //&// //&// //&// //&// //&// //&// \dots \\ \hline 1//&// 1//&// 1//&// 1//&// 1//&// 1//&// 11//&// 11//&// 10//&// 11\\ \hline\end{array}} \hspace*{1em}\square \]

Jól látszik, hogy a megjegyzendő részletek (általában) hosszabbak, mint a titok. A fenti példában a résztvevők mindegyikének két bitnyi információt kell fejben tartani, ha egy bitet akarnak ilyen módon titkosítani. Ez nem túl hatékony, szemben az ( n , n ) -küszöbrendszerrel, ahol minden érték (a kulcs és a részletek is) ugyanabból a számkörből való. Az általánosságért cserébe hatékonysággal fizettünk.

A szerzők a cikkükben egy általánosabb konstrukciót írtak le logikai függvényeket használva. Ennek segítségével egy adott struktúrához a fent leírtnál esetleg „hatékonyabb” titokmegosztást is konstruálhatunk. A hatékonysággal bővebben az utolsó fejezetben foglalkozunk.

Ito, Saito és Nishizeki konstrukciója (1987)

Ennek a konstrukciónak a szépségét egy furfangos ötlet adja.

Szükségünk lesz újabb jelölésekre. A P nem felhatalmazott csoportjainak halmazát ? -val jelöljük. (A ? halmazrendszer tehát a ? halmazrendszer komplementere a P részhalmazainak halmazára nézve.) ? -nak fontos tulajdonsága, hogy bármely elemének részhalmazait is tartalmazza, hiszen ha egy csoport nem jogosult a titok megállapítására, akkor a részhalmazai sem bírhatnak evvel a joggal. (Ez következik abból, amit a ? -ról megállapítottunk.) Így ? jellemezhető a maximális elemeivel, amelyek akárhogyan bővítve ? -beliek lesznek. Ezen csoportok halmazát ? 0 -lal jelöljük. Tehát ? a ? 0 elemeiből és azoknak az összes részhalmazaiból álló halmaz. A ? ismeretében ? meghatározható, így ? 0 is. A ? 0 méretét (elemeinek számát) q -val fogjuk jelölni.

Példa (2.2)

Vizsgáljuk továbbra is a 2.1. példa struktúráját, a későbbi összehasonlítások végett.

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

Egyszerűen végiggondolható, hogy ekkor ? 0 = p 1 p 2 + p 1 p 3 + p 1 p 4 + p 2 p 4 + p 3 p 4 . Jelen esetben tehát q = 5 . (A { p 1 , p 2 } halmaz például azért tartozik ? 0 -hoz, mert nem eleme ? -nak, de mindkét egyelemű bővítménye, { p 1 , p 2 , p 3 } és { p 1 , p 2 , p 4 } már igen.) ?

Az alábbi protokoll is felhasználja az ( n , n ) -küszöbrendszert.

A protokoll:

1. D a q méretű ? 0 = D 1 + ? + D q halmazon létrehoz egy ( q , q ) -küszöbrendszert. A küszöbrendszer létrehozása után legyen D i részlete s i ( 1 ? i ? ).

2. Ezek után D minden résztvevőnek odaadja azon nem felhatalmazott csoportok részleteit, amelynek nem eleme, azaz p j megkapja az alábbi számhalmazt: { s i p j ? D i } .

Hangsúlyozni szeretnénk, hogy a protokoll első lépése csak egy előkészítés (valójában egy hozzárendelés), a részletek tényleges kiosztása csak a második lépésben történik meg.

Mivel a fenti konstrukcióban van egy kis „csavar”, érdemes szemléltetni, mi történik.

D 1 = p 1 p 2 , D 2 = p 1 p 3 , D 3 = p 1 p 4 , D 4 = p 2 p 4 , D 5 = p 3 p 4 .

A tartalmazásokat könnyen megadhatjuk táblázattal. Ha egy résztvevő benne van egy csoportban, azt fekete ponttal jelöljük, ha pedig nem, akkor a megfelelő cellába beírjuk az oszlopának címkéjét, azt a részletet, amit meg fog kapni.

s 1 s 2 s 3 s 4 s 5 D 1 D 2 D 3 D 4 D 5 p 1 s 4 s 5 p 2 s 2 s 3 s 5 p 3 s 1 s 3 s 4 p 4 s 1 s 2 \[ {\setlength{\arraycolsep}{5pt}\begin{array}{|c|c|c|c|c|c|} \multicolumn{1}{c}{} //&// \multicolumn{1}{c}{ {s}_{1} } //&// \multicolumn{1}{c}{ {s}_{2}} //&// \multicolumn{1}{c}{ {s}_{3}} //&// \multicolumn{1}{c}{ {s}_{4}} //&// \multicolumn{1}{c}{ {s}_{5} }\\ \hline //&// {D}_{1}//&// {D}_{2}//&// {D}_{3}//&// {D}_{4}//&// {D}_{5}\\ \hline {p}_{1}//&// \bullet //&// \bullet //&// \bullet //&// {s}_{4}//&// {s}_{5}\\ \hline {p}_{2}//&// \bullet //&// {s}_{2}//&// {s}_{3}//&// \bullet //&// {s}_{5}\\ \hline {p}_{3}//&// {s}_{1}//&// \bullet //&// {s}_{3}//&// {s}_{4}//&// \bullet \\ \hline {p}_{4}//&// {s}_{1}//&// {s}_{2}//&// \bullet //&// \bullet //&// \bullet\\ \hline\end{array}} \]

Leolvasva: p 1 s 4 , s 5 , p 2 s 2 , s 3 , s 5 , p 3 s 1 , s 3 , s 4 , p 4 s 1 , s 2 . ?

A rendszer perfektsége a következő (alább végiggondolandó) tulajdonságból következik. Bármelyik felhatalmazott csoport összegyűjtvén részleteiket mindegyik s i ( 1 ? i ? q ) értéket megkapják; a nem felhatalmazott csoportoknak viszont legalább egy hiányozni fog. (A struktúra nyilvánossága miatt a résztvevők tudják, hogy az adott csoportban melyik részletüket kell használni.) A k kulcs értékének meghatározására viszont az összes s i -re szükség van, ennél kevesebb semmi információt nem szolgáltat (hiszen ezek egy ( q , q ) -küszöbrendszer részletei).

A rendszer ezen tulajdonsága a következők miatt igaz:

1. Ha B ? ? , akkor nyilván B ? D i semelyik i -re ( 1 ? i ? q ). Ezek szerint bármelyik i -hez van a B csoportnak olyan tagja: p j , akire fennáll, hogy p j ? D i , ezért p j megkapja s i -t.

2. Ha B ? ? , akkor B ? ? , azaz B ? D i valamelyik i -re ( 1 ? i ? q ). Ekkor ehhez az i -hez tartozó s i részletet egyikőjük sem kapja meg.

Például a B = { p 1 , p 3 } együttes adatai: s 1 , s 3 , s 4 , s 5 nem elegendőek a k kiszámításához, de ha p 4 is beszáll, akkor a hiányzó s 2 -t is megkapják.

Megadjuk a konstrukció táblázatát. A lehetséges kiosztások száma minden kulcshoz m 4 , mert négy érték (például s 1 , s 2 , s 3 , s 4 ? Z m ) szabadon választható. ( s 5 = k - ( s 1 + s 2 + s 3 + s 4 ) .) Ha m = 2 , akkor mindkét kulcshoz 16 sor tartozik.

k s 1 s 2 s 3 s 4 s 5 p 1 p 2 p 3 p 4 0 0 0 0 0 0 00 000 000 00 0 0 0 0 1 1 11 001 001 00 0 0 0 1 0 1 01 011 010 00 0 0 0 1 1 0 10 010 011 00 0 1 1 1 1 0 10 110 111 11 1 0 0 0 0 1 01 001 000 00 1 0 0 0 1 0 10 000 001 00 1 0 0 1 0 0 00 010 010 00 1 0 0 1 1 1 11 011 011 00 1 1 1 1 1 1 11 111 111 11 ? \[ {\setlength{\arraycolsep}{5pt}\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \multicolumn{1}{c}{ k} //&// \multicolumn{1}{c}{ {s}_{1}} //&// \multicolumn{1}{c}{ {s}_{2}} //&// \multicolumn{1}{c}{ {s}_{3}} //&// \multicolumn{1}{c}{ {s}_{4}} //&// \multicolumn{1}{c}{ {s}_{5}} //&// \multicolumn{1}{c}{ {p}_{1}} //&// \multicolumn{1}{c}{ {p}_{2}} //&// \multicolumn{1}{c}{ {p}_{3}} //&// \multicolumn{1}{c}{ {p}_{4}}\\ \hline 0//&// 0//&// 0//&// 0//&// 0//&// 0//&// 00//&// 000//&// 000//&// 00\\ \hline 0//&// 0//&// 0//&// 0//&// 1//&// 1//&// 11//&// 001//&// 001//&// 00\\ \hline 0//&// 0//&// 0//&// 1//&// 0//&// 1//&// 01//&// 011//&// 010//&// 00\\ \hline 0//&// 0//&// 0//&// 1//&// 1//&// 0//&// 10//&// 010//&// 011//&// 00\\ \hline \dots \,//&// //&// //&// //&// //&// //&// //&// //&// //&// \dots \\ \hline 0//&// 1//&// 1//&// 1//&// 1//&// 0//&// 10//&// 110//&// 111//&// 11\\ \hline 1//&// 0//&// 0//&// 0//&// 0//&// 1//&// 01//&// 001//&// 000//&// 00\\ \hline 1//&// 0//&// 0//&// 0//&// 1//&// 0//&// 10//&// 000//&// 001//&// 00\\ \hline 1//&// 0//&// 0//&// 1//&// 0//&// 0//&// 00//&// 010//&// 010//&// 00\\ \hline 1//&// 0//&// 0//&// 1//&// 1//&// 1//&// 11//&// 011//&// 011//&// 00\\ \hline \dots \,//&// //&// //&// //&// //&// //&// //&// //&// //&// \dots \\ \hline 1//&// 1//&// 1//&// 1//&// 1//&// 1//&// 11//&// 111//&// 111//&// 11\\ \hline \end{array}} \hspace*{1em}\square \]

Természetesen a kapott számok sorrendje számít.

A hatékonyság ismét csorbát szenvedett.