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

4. Egy véges geometriai (lineáris algebrai) konstrukció

4. Egy véges geometriai (lineáris algebrai) konstrukció

Az első idevonatkozó cikk 1991-ben jelent meg, s a véges geometria igen alkalmasnak mutatkozott általános de az addigiaknál hatékonyabb konstrukciók gyártására. Az alábbiakban bemutatandó igen ötletes konstrukciót Jackson, Martin és O’Keefe írták le. A konstrukciót tisztán lineáris algebrai eszközök segítségével mutatjuk be (megértéséhez szükség van a vektorterekre vonatkozó alapismeretekre), s a fejezet végén utalunk a véges geometriai szemléletre.

Induljunk ki az F p véges test feletti d -dimenziós vektortérből, jelöljük ezt V p d -vel, vagy röviden V -vel. (Ekkor a vektorok a { 0 , 1 , , p - 1 } halmaz elemeiből képzett d -tagú sorozatok lesznek, az alapműveleteket, azaz az összeadást, a skalárral való szorzást és a skaláris szorzást pedig a szokásos módon modulo p végezzük.) A V vektortér k -dimenziós altereit (ahol 1 ? k ? d ) egy bázisukkal fogjuk megadni a W = [ v 1 , , v k ] jelöléssel. Altér konfigurációnak hívjuk az alábbi titokmegosztást, amely ugyan nem teljesíti a perfektség követelményeit, de alapul szolgál egy perfekt titokmegosztás konstruálásához.

Legyenek mind a titok, mind a résztvevők részletei V p d -nek alterei a következőképpen. Jelöljük a p j ( 1 ? j ? n ) résztvevő részlet-alterét p ^ j -pal, a kulcsnak megfelelő alteret k ^ -pal, egy A ? P csoport tagjainak részlet-alterei által kifeszített alteret pedig A^ -pal. Teljesüljön az alábbi két követelmény:

Ha A ? ? , akkor k ^ ? A^ (azaz k ^ altere A^ -nak);

Ha A ? ? , akkor k ^ ? A^ = ( 0 , 0 , 0 ) .

Példa (4.1)

A 2.1. példában megadott hozzáférési struktúra esetén

( 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 )

megfelel a következő altér konfiguráció:

V 3 3 -ban dolgozunk. Az alterek mindegyike jelen esetben egy egydimenziós altér lesz, tehát egy-egy origón átmenő egyenes, amelyet egy-egy vektorával adunk meg:

p ^ 1 = [ ( 0 , 1 , 2 ) ] , p ^ 2 = [ ( 0 , 1 , 0 ) ] , p ^ 3 = [ ( 1 , 0 , 1 ) ] , p ^ 4 = [ ( 1 , 0 , 0 ) ] , k ^ = [ ( 1 , 1 , 1 ) ] .

A feltételek ellenőrzése kissé aprólékos, de nem nehéz. Példaként nézzük először az A = { p 1 , p 2 } csoportot, amely nincs felhatalmazva. Mivel a ( 0 , 1 , 2 ) és a ( 0 , 1 , 0 ) vektorok lineárisan függetlenek, ezért a közösen kifeszített alterük A^ = [ ( 0 , 1 , 2 ) , ( 0 , 1 , 0 ) ] . Ezen altérben minden vektor első koordinátája 0, k ^ -ban pedig csak a nullvektorra teljesül ez, így az lesz az egyetlen közös elemük. A B = { p 1 , p 2 , p 4 } csoport viszont felhatalmazott, s valóban, közösen kifeszített alterüknek eleme az ( 1 , 1 , 1 ) = 2 · ( 0 , 1 , 2 ) + 2 · ( 0 , 1 , 0 ) + ( 1 , 0 , 0 ) , így k ^ ? B ^ teljesül. ?

Az altér konfiguráció létrehozására a próbálkozás a legjobb módszer. (Az Ito–Saito–Nishizeki konstrukciót felhasználva általánosan megadható alkalmas konfiguráció, csak ez túl magas dimenziós alterekkel dolgozik, általában ezen egzisztenciapéldánál találhatók egyszerűbbek.)

A leírt altér konfiguráció valóban nem perfekt titokmegosztást definiál, hiszen a felhatalmazott csoportok nem tudják pontosan meghatározni a kulcs-alteret (csak annak egy bővített terét), a nem felhatalmazottak pedig hasznos információkhoz juthatnak (kizárhatnak bizonyos altereket a lehetséges kulcs-alterek közül). Azonban ezen konfiguráció alapján előállíthatjuk egy perfekt titokmegosztási rendszer táblázatát a következőképpen:

A táblázat oszlopait a résztvevőkkel, illetve a titokkal címkézzük, a sorokat pedig a V p d vektortér összes vektoraival ( v 1 , v 2 , ) . Legyen z ? { k } ? P , az ehhez tartozó z ^ altér dimenziója d z , bázisa e 1 , , e d z ; e j ? V p d , 1 ? j ? d z . Ekkor z oszlopának i -edik sorában álljon d z darab F p -beli szám: e 1 · v i , , e d z · v i , ahol az e j · v i szorzatok skaláris szorzatok.

A fent megadott konfigurációval elkészítjük a táblázatot.

p ^ 1 = [ ( 0 , 1 , 2 ) ] , p ^ 2 = [ ( 0 , 1 , 0 ) ] , p ^ 3 = [ ( 1 , 0 , 1 ) ] , p ^ 4 = [ ( 1 , 0 , 0 ) ] , k ^ = [ ( 1 , 1 , 1 ) ] .

Mivel itt minden altér egydimenziós, a táblázat celláiban egy-egy szám áll, az illető cella sorának és oszlopának címkéinek skaláris szorzata

k p 1 p 2 p 3 p 4 ( 1 , 1 , 1 ) ( 0 , 1 , 2 ) ( 0 , 1 , 0 ) ( 1 , 0 , 1 ) ( 1 , 0 , 0 ) ( 0 , 0 , 0 ) 0 0 0 0 0 ( 0 , 0 , 1 ) 1 2 0 1 0 ( 0 , 0 , 2 ) 2 1 0 2 0 ( 0 , 1 , 0 ) 1 1 1 0 0 ( 0 , 1 , 1 ) 2 0 1 1 0 ( 2 , 2 , 0 ) 1 2 2 2 2 ( 2 , 2 , 1 ) 2 1 2 0 2 ( 2 , 2 , 2 ) 0 0 2 1 2 \[ {\setlength{\arraycolsep}{5pt}\begin{array}{|c|c|c|c|c|c|} \multicolumn{1}{c}{} //&// \multicolumn{1}{c}{ k} //&// \multicolumn{1}{c}{ {p}_{1}} //&// \multicolumn{1}{c}{ {p}_{2}} //&// \multicolumn{1}{c}{ {p}_{3}} //&// \multicolumn{1}{c}{ {p}_{4}}\\ \multicolumn{1}{c}{} //&// \multicolumn{1}{c}{ (1,1,1)} //&// \multicolumn{1}{c}{ (0,1,2)} //&// \multicolumn{1}{c}{ (0,1,0)} //&// \multicolumn{1}{c}{ (1,0,1)} //&// \multicolumn{1}{c}{ (1,0,0)}\\ \hline (0,0,0)//&// 0//&// 0//&// 0//&// 0//&// 0\\ \hline (0,0,1)//&// 1//&// 2//&// 0//&// 1//&// 0\\ \hline (0,0,2)//&// 2//&// 1//&// 0//&// 2//&// 0\\ \hline (0,1,0)//&// 1//&// 1//&// 1//&// 0//&// 0\\ \hline (0,1,1)//&// 2//&// 0//&// 1//&// 1//&// 0\\ \hline \dots //&// //&// //&// //&// //&// \dots \\ \hline (2,2,0)//&// 1//&// 2//&// 2//&// 2//&// 2\\ \hline (2,2,1)//&// 2//&// 1//&// 2//&// 0//&// 2\\ \hline (2,2,2)//&// 0//&// 0//&// 2//&// 1//&// 2\\ \hline \end{array}} \]

A táblázat készítésekor a kulcs oszlopát a résztvevőkével analóg módon töltjük ki, de praktikus ezt a táblázatot is a kulcsok szerint csoportosítani.

k = 0 k = 1 k = 2 p 1 p 2 p 3 p 4 p 1 p 2 p 3 p 4 p 1 p 2 p 3 p 4 0 0 0 0 2 1 2 0 1 2 1 0 1 0 0 1 0 1 2 1 2 2 1 1 2 0 0 2 1 1 2 2 0 2 1 2 2 0 1 0 1 1 0 0 0 2 2 0 0 0 1 1 2 1 0 2 1 2 2 1 1 0 1 2 0 1 0 2 2 2 2 2 1 0 2 0 0 1 1 0 2 2 0 0 2 0 2 1 1 1 1 1 0 2 0 1 0 0 2 2 2 1 1 2 1 2 0 2 ? \[ {\setlength{\arraycolsep}{5pt}\begin{array}{ccc} k=0//&// k=1//&// k=2\\ {\setlength{\arraycolsep}{5pt}\begin{array}{|c|c|c|c|} \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\\ \hline 2//&// 1//&// 2//&// 0\\ \hline 1//&// 2//&// 1//&// 0\\ \hline 1//&// 0//&// 0//&// 1\\ \hline 0//&// 1//&// 2//&// 1\\ \hline 2//&// 2//&// 1//&// 1\\ \hline 2//&// 0//&// 0//&// 2\\ \hline 1//&// 1//&// 2//&// 2\\ \hline 0//&// 2//&// 1//&// 2\\ \hline\end{array}}//&// {\setlength{\arraycolsep}{5pt}\begin{array}{|c|c|c|c|} \multicolumn{1}{c}{{p}_{1}} //&// \multicolumn{1}{c}{ {p}_{2}} //&// \multicolumn{1}{c}{ {p}_{3}} //&// \multicolumn{1}{c}{ {p}_{4}}\\ \hline 2//&// 0//&// 1//&// 0\\ \hline 1//&// 1//&// 0//&// 0\\ \hline 0//&// 2//&// 2//&// 0\\ \hline 0//&// 0//&// 1//&// 1\\ \hline 2//&// 1//&// 0//&// 2\\ \hline 1//&// 2//&// 2//&// 1\\ \hline 1//&// 0//&// 1//&// 2\\ \hline 0//&// 1//&// 0//&// 2\\ \hline 2//&// 2//&// 2//&// 2\\ \hline\end{array}}//&// {\setlength{\arraycolsep}{5pt}\begin{array}{|c|c|c|c|} \multicolumn{1}{c}{{p}_{1}} //&// \multicolumn{1}{c}{ {p}_{2}} //&// \multicolumn{1}{c}{ {p}_{3}} //&// \multicolumn{1}{c}{ {p}_{4}}\\ \hline 1//&// 0//&// 2//&// 0\\ \hline 0//&// 1//&// 1//&// 0\\ \hline 2//&// 2//&// 0//&// 0\\ \hline 2//&// 0//&// 2//&// 1\\ \hline 1//&// 1//&// 1//&// 1\\ \hline 0//&// 2//&// 0//&// 1\\ \hline 0//&// 0//&// 2//&// 2\\ \hline 2//&// 1//&// 1//&// 2\\ \hline 1//&// 2//&// 0//&// 2\\ \hline\end{array}} \end{array}}\hspace*{1em}\square \]

Vizsgáljuk meg pl. azt az esetet, amikor mindegyik résztvevő a 0 részletet kapta. Ha p 2 és p 3 összebeszél, akkor ki tudják találni a kulcs értékét, hiszen három helyen fordul elő, hogy mindketten a 0 részletet kapták és mindhárom lehetőség a k = 0 kulcshoz tartozik. Ezzel ellentétben p 2 és p 1 együtt nem tudnak meg semmit, hiszen a kulcs mindhárom lehetséges értékénél egyszer-egyszer fordul elő, hogy mindkettejük részlete 0.

Annak precíz bizonyítása, miszerint az így kapott táblázat valóban perfekt titokmegosztást ad meg, a lineáris algebrában tett némi gyakorlat után nem nehéz.

Összefoglalva a protokoll:

1. D konstruál a hozzáférési struktúrához egy altér konfigurációt (alkalmasan választott d és p értékek mellett).

2. D elkészíti a perfekt titokmegosztási táblázatot.

3. D (az előre adott, vagy véletlenszerűen választott) kulcs résztáblázatában véletlenszerűen kiválaszt egy sort, és ennek megfelelően kiosztja a részleteket.

Érdekessége a protokollnak, hogy nyilvánosságra csak a táblázat kerül, ennek alapja, az altér konfiguráció nem. (Az eddig bemutatott konstrukciókban a táblázatot csak a könnyebb áttekinthetőség, illetve a résztvevők számolgatásának megspórolása végett vezettük be.)

Egy másik érdekes és fontos megállapítást tehetünk, ha összehasonlítjuk ezt a táblázatot a 2.1. példa és a 2.2. példa táblázataival, melyeket ugyanehhez a hozzáférési struktúrához konstruáltunk. Ez az egyetlen közülük, amelyben a lehetséges részletek pontosan ugyanabból a halmazból kerülnek ki, mint a lehetséges kulcsok, azaz a résztvevők „megjegyeznivalója” nem több, mintha magát a titkot kellene megjegyezni. A három konstrukció közül tehát valóban ez a leghatékonyabb, mint azt a fejezet elején említettük.

Az altér konfiguráción alapuló perfekt titokmegosztási táblázat készítésére mutatunk egy másik példát is.

Példa (4.2)

Legyen P = { p 1 , p 2 , p 3 , p 4 } és ? 0 = p 1 p 2 + p 1 p 3 + p 1 p 4 + p 2 p 3 p 4 . Ez egy „diktatórikus” hozzáférési rendszer, a p 1 résztvevő kiemelt, a másik három egyenrangú.

V 2 3 -ban dolgozunk. A megfelelő altér konfiguráció:

p ^ 1 = [ ( 1 , 1 , 0 ) , ( 0 , 1 , 1 ) ] , p ^ 2 = [ ( 1 , 0 , 0 ) ] , p ^ 3 = [ ( 0 , 1 , 0 ) ] , p ^ 4 = [ ( 0 , 0 , 1 ) ] , k ^ = [ ( 1 , 1 , 1 ) ] .

Mivel most a p 1 résztvevő altere kétdimenziós, ezért ő két darab F 2 -beli számot kap részletként. A táblázat:

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

Konkrét példáinkon keresztül megmutatjuk a lineáris algebrai konstrukció véges geometriai szemléletét. Az általános esetben a ( d - 1 ) -dimenziós projektív térre van szükség, de példáinkban d = 3 , tehát a projektív sík jön csak szóba.

A 3-dimenziós tér origón átmenő egyenesei és síkjai (tehát a teljes tértől és az origótól különböző alterek) megfelelnek a projektív sík axiómáinak. Bármely két origón átmenő egyenesen pontosan egy origót tartalmazó sík fektethető át, és bármelyik két olyan sík, amely tartalmazza az origót, egy azon átmenő egyenesben metszi egymást. Tehát e projektív sík pontjai az origót tartalmazó egyenesek, míg a projektív sík egyenesei az origót tartalmazó síkok. Ez a projektív sík algebrailag is jól kezelhető. Ha a projektív sík egy pontját akarjuk akarjuk megnevezni, akkor megadjuk a pontnak megfelelő térbeli ( V p 3 -beli) egyenes egy tetszőleges nullvektortól különböző vektorát a három koordinátájával. Ha a projektív sík egy egyeneséről akarunk beszélni, akkor megadjuk az egyenesnek megfelelő, az origót tartalmazó sík egy nullvektortól különböző normálvektorát, azaz egy olyan vektort, amelynek a sík bármely vektorával vett skaláris szorzata 0. A projektív sík egy pontja és egy egyenese akkor és csak akkor illeszkedik egymásra, ha a nekik megfeleltetett vektorok skaláris szorzata 0.

Példa (4.3)

P G ( 2 , 2 ) az ún. Fano-sík pontjai: A ( 0 , 0 , 1 ) , B ( 0 , 1 , 0 ) , C ( 1 , 0 , 0 ) , D ( 1 , 1 , 0 ) , E ( 1 , 0 , 1 ) , F ( 0 , 1 , 1 ) , G ( 1 , 1 , 1 ) ; egyenesei pedig B D C ( 0 , 0 , 1 ) , A E C ( 0 , 1 , 0 ) , A F B ( 1 , 0 , 0 ) , A G D ( 1 , 1 , 0 ) , B G E ( 1 , 0 , 1 ) , C G F ( 0 , 1 , 1 ) , E D F ( 1 , 1 , 1 ) . Ennek közismert ábrája (1. ábra), ahol az E D F „kör” is egyenes. ?

1. ábra.

Teljesen hasonlóan leírható a d -dimenziós, q -adrendű véges projektív tér. Adott F q , az egyértelmű q = p n -elemű véges test; és felette V q d + 1 , a ( d + 1 ) -dimenziós vektortér. Nevezzük a V q d + 1 egydimenziós altereit pontoknak, a kétdimenziós altereit egyeneseknek, …, a d -dimenziós altereit hipersíkoknak. (Tehát a geometriai dimenzió eggyel kisebb az altér dimenziójánál.) A P G ( d , q ) d -dimenziós, q -adrendű véges projektív tér (Galois-tér) az így definiált pontok alkotta ponthalmaz. Látjuk tehát, hogy a véges projektív terek elmélete a vektorterek elméletével leírható. Az altér konfiguráció definiálásakor kellett volna általános vektortér helyett véges projektív teret írnunk ( V p d -nek P G ( d - 1 , q ) felel meg), az alterekre mint geometriai objektumokra (pontokra, egyenesekre), illetve a tartalmazásra mint illeszkedésre utalnunk, végül a második feltételben egy kis módosítást tennünk:

(1) Ha A ? ? , akkor k ^ ? A^ ;

(2) Ha A ? ? , akkor k ^ ? A^ = Ø .

Vegyük észre, hogy 4.2. példában az altér konfiguráció a Fano-síkon készült, a p 2 , p 3 , p 4 , résztvevők rendre a C , B , A pontokat kapták, p 1 a D és F pontok által kifeszített E D F egyenest, a kulcs-altér pedig a G pont. Érdemes geometriailag is ellenőrizni a feltételeket: egy egyenes ( D E F ) és egy rá nem illeszkedő pont ( A , B vagy C ), illetve 3 nem kollineáris pont ( A , B és C ) kifeszítik a síkot, amelynek része a G pont is, de három nem kollineáris pont ( A , B és C ) közül bármely kettő olyan egyenest feszít ki, amelyre nem illeszkedik a G pont, azaz metszetük üres. ?