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

3. Shamir konstrukciója a ( t , n ) -küszöbrendszerre (1979)

3. Shamir konstrukciója a ( t , n ) -küszöbrendszerre (1979)

Ez a megoldás igen szép alkalmazása a véges testeknek. Az egyszerűség kedvéért az F p véges testet használjuk, amelyben a számolás pusztán a p prím modulussal való számolás; de teljesen analóg a konstrukció egyéb véges testekre építve.

P = { p 1 , p 2 , , p n } , ? 0 = { B B ? P , B = t } ( t ? n ) .

A protokoll:

3. D választ n db különböző értéket F p -ben ( p //>// n ) : x 1 , , x n , x i ? 0 ; s ezeket nyilvánosan kiosztja a résztvevőknek: p i -nek adja x i -t ( 1 ? i ? n ). (Ezt a számot a résztvevőknek nem kell fejben tartaniuk, felírhatják maguknak.)

4. Legyen a kulcs k ? F p . D véletlenszerűen választ a 1 , , a t - 1 ? F p elemeket, és ezekkel felírja az a ( x ) = k + a 1 x + + a t - 1 x t - 1 F p -feletti polinomot, melyben tehát a 0 = k a konstans tag.

5. D minden résztvevőnek titkosan megadja a polinom helyettesítési értékét a nyilvános részletének helyén, azaz p i -nek adja az y i = a ( x i ) ? F p ( 1 ? i ? n ) értéket.

Összefoglalva a részleteket: p 1 a ( x 1 ) ; p 1 a ( x 2 ) ; …; p n a ( x n ) .

Tehát egy F p -feletti legfeljebb ( t - 1 ) -edfokú polinomnak a 0 helyen vett helyettesítési értéke (konstans tagja) a titok, és további különböző helyeken vett helyettesítési értékek a kiosztott részletek. Ha az alaptest a valós számok teste volna, akkor szemléletesen azt mondhatnánk, hogy a polinom y tengely-metszete a titok, és további különböző pontjai a kiosztott részletek.

Ha t db résztvevő: p i 1 , , p i t meg akarja határozni a kulcsot, akkor megoldják az alábbi egyenletrendszert:

y i 1 = a 0 + a 1 x i 1 + + a t - 1 x i 1 t - 1 y i 2 = a 0 + a 1 x i 2 + + a t - 1 x i 2 t - 1 ? y i t = a 0 + a 1 x i t + + a t - 1 x i t t - 1

az a 0 , a 1 , , a t - 1 ismeretlenekben. Mivel az egyenletrendszer determinánsa az x i 1 , x i 2 , , x i t különböző elemek által generált Vandermonde-determináns:

1 x i 1 x i 1 t - 1 ? 1 x i t x i t t - 1 = ? 1 ? j //<// k ? t ( x i k - x i j ) mod p ? 0 ,

ezért az egyenletrendszer egyértelműen megoldható például Cramer-szabállyal, s a megoldásból a 0 = k a kulcs. Az esetleges többi résztvevő adataira nincs is szükség. Valójában azt használjuk, hogy véges testek felett is igaz, hogy t különböző ponton keresztül egyértelműen állítható legfeljebb ( t - 1 ) -edfokú polinom.

Ha t - 1 db résztvevő: p i 1 , , p i t - 1 áll össze, akkor az alábbi egyenletrendszert kapják:

y i 1 = a 0 + a 1 x i 1 + + a t - 1 x i 1 t - 1 y i 2 = a 0 + a 1 x i 2 + + a t - 1 x i 2 t - 1 ? y i t - 1 = a 0 + a 1 x i t - 1 + + a t - 1 x i t - 1 t - 1

Bármely a 0 = k hipotézisre az

y i 1 - a 0 = a 1 x i 1 + + a t - 1 x i 1 t - 1 y i 2 - a 0 = a 1 x i 2 + + a t - 1 x i 2 t - 1 ? y i t - 1 - a 0 = a 1 x i t - 1 + + a t - 1 x i t - 1 t - 1

átrendezéssel kapott egyenletrendszernek az előzőhöz hasonlóan egyértelmű megoldása van. Ekkor ugyanis a fődetermináns

x i 1 x i 1 t - 1 ? x i t - 1 x i t - 1 t - 1 = x i 1 · · x i t - 1 · 1 x i 1 x i 1 t - 2 ? 1 x i t - 1 x i t - 1 t - 2 ? 0 .

Így semelyik lehetséges k értéket nem zárhatják ki vagy részesíthetik előnyben. (Egy megoldás találása egy olyan szétosztás létezését jelenti, amelyben a csoport tagjai az adott részletekkel bírnak, és a titok a hipotézisben feltett érték.) Lineáris algebrai ismeretek segítségével belátható, hogy ha r db ( r //<// t ) résztvevő áll össze, akkor a részleteik alapján felírt egyenletrendszerhez bármely kulcshipotézis esetén pontosan p t - r - 1 különböző megoldást kapnak. Ennek az eredménynek két fontos következménye van. Egyrészt r ? t - 1 miatt t - r - 1 ? 0 , s így p t - r - 1 ? 1 , azaz van megoldás akármelyik kulcshipotézisre, semelyik lehetséges titokérték nem zárható ki. Másrészt a megoldások száma csak a próbálkozó csoport létszámától függ, azaz egy konkrét csoport számára bármelyik lehetséges titokérték egyformán valószínű. Ez pedig éppen a perfektség feltétele.

A fent említett szemléletes képet használva azt mondhatjuk, hogy r db ( r //<// t ) résztvevő és tetszőleges a 0 = k kulcshipotézis esetén a ( 0 , y 0 = a 0 ) , ( x i 1 , y i 1 ) , , ( x i r , y i r ) pontokon át ugyanannyi ( p t - r - 1 ? 1 db) legfeljebb ( t - 1 ) -edfokú polinom állítható; legalább t résztvevő esetén viszont a pontjaikon át állított polinom egyértelmű, így ennek „ y tengely-metszete” is. (A valós számok teste felett hasonlóan szól a tétel, csak p t - r - 1 helyett végtelen sokat kellene mondanunk.)

Megjegyezzük, hogy a tetszőleges test felett igaz Lagrange-féle interpolációs formula segítségével a felhatalmazott csoportok az egyenletrendszer megoldásánál rövidebben is eljárhatnak bizonyos előre kiszámítható adatok felhasználásával (amennyiben nem áll rendelkezésükre táblázat).

Példa (3.1)

Egy Shamir-féle ( 2 , 3 ) -küszöbrendszert táblázatolunk. ( n = 3 , P = { p 1 , p 2 , p 3 } .) Mivel itt t = 2 , a polinom elsőfokú, a ( x ) = k + a 1 · x . Ekkor a lehetséges kiosztások száma minden kulcshoz p , mert a 1 ? F p szabadon választható.

Legyen például F p = Z 5 , és a nyilvánosan kiosztott értékek: x 1 = 1 , x 2 = 2 , x 3 = 4 .

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

Ennél a táblázatnál konkrét példán keresztül megnézzük, mit jelent a perfektség teljesülése. Tegyük fel, hogy a p 1 és a p 3 résztvevők együttesen szeretnék leleplezni a titkot. Mindketten felfedik a részletüket, legyen például p 1 részlete 2, p 3 részlete pedig 4. Mivel ketten vannak, felhatalmazott csoportot alkotnak, így annak kell teljesülnie, hogy csak egyetlen kulcs résztáblázatában találjanak olyan sort, ahol az ő részletük 2, illetve 4. Valóban egyetlen ilyen sor van az egész táblázatban, s ez a k = 3 értékhez tartozik (annak ötödik sora). Tehát a titok értéke 3. Ha viszont a p 3 résztvevő egyedül próbálkozott volna, akkor azt tapasztalta volna, hogy mindegyik kulcshoz pontosan egy olyan sor van, amelyben az ő részlete 4. ő egyedül nem felhatalmazott „csoportot alkot”, a titokról még csak valószínűségi feltevéseket sem tud tenni.

Itt említjük meg, hogy amennyiben egy felhatalmazott csoport leleplezte a titok értékét, az irányítónak természetesen újra el kell végeznie a szétosztást egy újonnan választott kulcs mellett. Ennél a konstrukciónál a protokoll első lépésében kiosztott nyilvános részletek maradhatnak, csak a polinomot (és ezáltal a helyettesítési értékeket) kell lecserélni. ?