Karnin-Green-Hellmanin suunnitelma

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 16. lokakuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 52 muokkausta .

Karnin-Green-Hellman- skeema on kynnyksen salainen jakamisjärjestelmä , joka perustuu yhtälöjärjestelmien ratkaisemiseen . Kirjoittajat ovat Ehud D. Karnin , Jonathan W. Greene ja Martin E. Hellman .

Johdanto

Kynnyssalaisuuden jakamisjärjestelmä äärellisillä kentillä on menetelmä salaisen avaimen vaihtamiseksi osallistujien välillä siten, että kuka tahansa heistä voi palauttaa salaisuuden, mutta mikä tahansa ryhmä tai vähemmän ei voi. Kaava koostuu kahdesta vaiheesta. Ensimmäisessä vaiheessa, allokointivaiheessa , joku osapuoli (kutsutaan toimittajaksi ) luo osakkeita käyttämällä allokointialgoritmia . Jokaisesta toimittaja luovuttaa henkilökohtaisesti osallistumisosuuden osallistujalle . Toinen vaihe, jota kutsutaan palautusvaiheeksi , tapahtuu, kun osallistujat haluavat palauttaa salaisen avaimen . $k$ $n$ $t$ $t-1$ $s_1, s_2, \pisteet, s_n$ $D$ $i$ $si}$ $P_{i}$ $t$ $P_{i_1}, P_{i_2}, \dots, P_{i_t}$ $k$

Kynnysmallien tyypit

Kynnyssalaisuuden jakamisjärjestelmän sanotaan olevan täydellinen , jos ainakin osapuolet voivat saada salaisuuden takaisin, mutta mikä tahansa ryhmä tai vähemmän osapuolia ei voi. $t$ $t-1$
Kynnysarvon salaisuuden jakamismenetelmää kutsutaan lineaariseksi , jos salaisuus palautetaan ottamalla panosten lineaarinen yhdistelmä. $k$ $t$
Kynnyssalaisuuden jakamisjärjestelmää kutsutaan ideaaliseksi , jos osakkeiden koko on sama kuin salaisuuden . $k$
Täydellinen, ihanteellinen ja lineaarinen kynnyssalaisuuden jakamisjärjestelmä on nimeltään PIL (perfect, ideal and linear) kynnyssalaisuuden jakamisjärjestelmä.

PIL-kynnyskaavio voidaan määritellä jakelumatriisin ominaisuuksien perusteella ${\näyttötyyli D:}$

1. Täydellisyys - mikä tahansa ryhmä, joka sisältää vähintään jäseniä, voi laskea salaisuuden . Siten kaikilla jakaumamatriisin riveillä on oltava väli, joka sisältää rivin $t$ $k$ $t$ $D$

\vasen[ 1, 0, 0, \pisteet, 0 \oikea]

2. Luottamuksellisuus - mikään ryhmä, jossa on alle jäsentä, ei voi saada tietoa salaisesta avaimesta . Toisin sanoen, tai vähemmän jakelumatriisin rivejä ei voi sisältää väliä, joka sisältää rivin $t$ $k$ $t-1$ $D$

\vasen[ 1, 0, 0, \pisteet, 0 \oikea]

Kuvaus

Tarkastellaan äärellistä kenttää . Anna yksinkertainen elementti ja anna $\mathrm{GF}(q^{m})$ $\alpha$ $\mathrm{GF}(q^{m})$

{\displaystyle \alpha _{i}\equiv \alpha ^{i},i={\overline {1,q^{m-1))))

Palveluntarjoaja valitsee satunnaisesti . $a_{1},a_{2},\dots ,a_{{t-1}}$ $\mathrm{GF}(q^{m})$

Sitten se kuvaa oman pääoman seuraavasti $n$ $si}$

\left[ \begin{array}{c} s_{1}\\s_{2}\\\vdots \\s_{r}\\s_{r+1} \\ \end{array}\right] = \quad\left[\begin{array}{ccccc} 1 & \alpha_{1} & \alpha_{1}^{2} & \cdots & \alpha_{1}^{t-1} \\ 1 & \ alfa_{2} & \alpha_{2}^{2} & \cdots & \alpha_{2}^{t-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \ alpha_{r} & \alpha_{r}^{2} & \cdots & \alpha_{r}^{t-1} \\ 0 & 0 & 0 & \cdots & 1 \end{array}\right] \ vasen[ \begin{array}{c} k\\a_1\\a_2\\\vdots\\a_{t-1}\\ \end{array}\right]

$n=r+1,r\leq q^{m}-1$ .

Palveluntarjoaja lähettää sen sitten osallistujalle varmistaen, että matriisin kaikki rivit, jotka on merkitty muodossa , muodostavat käännettävän matriisin . $si}$ $P_{i}$ $t$ $D$ $D_{i_1, i_2, \pisteet, i_t}$ $t\ kertaa t$

Näin ollen , Jossa vektori on sarake, joka koostuu . $\bar{y} = D_{i_1, i_2, \pisteet, i_t}^{-1} \cdot \bar{S}_{i_1, i_2, \dots, i_t}$ ${\bar {S}}_{i_{1},i_{2},\dots ,i_{t}}-$ $s_{{i_{1}}},s_{{i_{2}}},\dots ,s_{{i_{t}}}$

Näin salaisuus voidaan laskea. $k$

Myöskään matriisin riville ei sisällytetä riviä $t-1$ $D$ $[{\begin{array}{ccccc}\gamma ,0,0,\cdots ,0\\\end{array}}]$ ${\displaystyle \forall \gamma \in \mathrm {GF} (q^{m})\setminus \{0\))$ $D_{i_{1},i_{2},\dots ,i_{t-1)).$

Tämä tarkoittaa, että vähemmän tai vähemmän osallistujia ei voi saada tietoa salaisuudesta . Siksi on mahdollista rakentaa kynnyksen salainen jakamismalli , jossa , eli osallistujien määrä voi olla yhtä suuri kuin kentän koko. $t-1$ $k$ $r+1$ $r+1=\mid {\mathbb {F}}\mid$ $n$

Maksimin määrittämisen kannalta voidaan siis sanoa, että Karnin-Green-Hellman-kaavio on tehokkaampi kuin Shamir-kaavio . $n$

Esimerkki optimaalisesta mallista

$n_{{max,t}}$ on suurin , jolle on mahdollista rakentaa PIL - kynnyksen salainen jakamismalli äärellisen kentän yli . $n$ ${\näyttötyyli (t,n)-}$ ${\mathbb {F}}$
$D$ - jakelumatriisi PIL - kynnyksen salainen jakamismalli viimeisen kentän yli kirjoitetaan KGH-normaalimuodossa, jos se täyttää seuraavan yhtäläisyyden: ${\näyttötyyli (t,n)}$ ${\mathbb {F}}$

D=\quad \left[{\begin{array}{ccccc}1&x_{12}&x_{13}&\cdots &x_{1t}\\1&x_{22}&x_{23}&\cdots &x_{2t }\\\vpisteet &\vdots &\vdots &\ddots &\vdots \\1&x_{r2}&x_{r3}&\cdots &x_{rt}\\1&1&1&\cdots &1\\0&1&0&\cdots &0\\0&0&1&\ cdots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\cdots &1\\\end{array}}\right]

Minkä tahansa PIL :n, rajallisen kentän salaisen kynnyksen jakamismallin , jakelumatriisi voidaan kirjoittaa KGH-normaalimuotoon. ${\näyttötyyli (t,n)}$ ${\mathbb {F}}$ $D$

Lause 1. Oletetaan, että meillä on salainen avaruus = = ${\mathcal {S))$ ${\mathbb {F}}$ $\mathrm{GF}(q^{m})$

Sitten tyydyttää: $n_{{max,t}}$

\mid {\mathbb {F}}\mid \leq n_{{max,t}}\leq \mid {\mathbb {F}}\mid +t-2

. _

q^{{m}}>t

n_{{max,t}}=t

. _

q^{{m}}\leq t

Lause 2. Antaa olla äärellinen kenttä ja . Sitten on luotettava PIL - kynnys - salainen jakamisjärjestelmä kentällä . $\mathbb {F} =\mathrm {GF} (2^{m})$ $n=\mid \mathbb {F} \mid +1$ ${\näyttötyyli (3,n)}$ ${\mathbb {F}}$

Todiste. Kentän ominaisuus on . Kaikkien ei-triviaalien elementtien (elementit, jotka eivät ole yhtä suuria kuin tai ) kenttien kertova järjestys on suurempi kuin . Antaa olla kentän elementtejä ei ole yhtä suuri tai . $\mathbb {F} =\mathrm {GF} (2^{m})$ $2$ $0$ $yksi$ ${\mathbb {F}}$ $2$ ${\displaystyle x_{1},x_{2},\cdots ,x_{\mid \mathbb {F} \mid -2))$ ${\mathbb {F}}$ $0$ $yksi$

Sitten jakelumatriisi on seuraavanlainen:

D=\quad \left[{\begin{array}{ccccc}1&x_{1}&x_{1}^{2}\\\vdots &\vdots &\vdots \\1&x_{\mid \mathbb { F} \mid -2}&x_{\mid \mathbb {F} \mid -2}^{2}\\1&1&1\\0&1&0\\0&0&1\\\end{array}}\right]

Siten on kynnyksen salaisen koon jakamisjärjestelmän PIL - matriisi $D$ ${\näyttötyyli (3,n)-}$ $(\mid \mathbb {F} \mid +1)\times 3.$

Harkitse täydellisyyttä .

Numeroimme matriisin rivit ylhäältä alas . $D$ $yksi$ $n$

Tapaus I. Mikä tahansa 3 riviä sarjasta voi palauttaa salaisuuden Vandermonde-matriisin käänteisyyden vuoksi . $\{1,\cdots ,n-2\}$
Tapaus II. Sanotaan annetut merkkijonot ja ja vielä yksi merkkijono joukosta . Silloin on selvää, että salaisuus voidaan palauttaa. $\left[0,1,0\right]$ $\left[0,0,1\right]$ $\{1,\cdots ,n-2\}$
Tapaus III. Oletetaan, että yksi merkkijonoista kuuluu joukkoon ja kaksi muuta on valittu joukosta . Tämän jälkeen voit poistaa merkkijonon joukosta alkeismerkkijonomuunnoksilla . Tuloksena on Vandermont-kokojärjestelmä , joka on käännettävä. ${\displaystyle \{\left[0,1,0\right],\left[0,0,1\oikea]\))$ $\{1,\cdots ,n-2\}.$ ${\displaystyle \{\left[0,1,0\right],\left[0,0,1\oikea]\))$ $2 kertaa 2$

Täydellisyysominaisuus on todistettu. Luottamuksellisuuden todistaminen toimii samalla tavalla.

Kaikille kentille , joilla on ominaisuus , käy ilmi, että: ${\mathbb {F}}$ $2$

n_{max,3}=\mid \mathbb {F} \mid +1=\mid \mathbb {F} \mid +3-2=\mid \mathbb {F} \mid +t-2

Näin ollen kentillä, joilla on Karnin–Green–Hellman-kaavion ominaispiirteet , se saavuttaa Lauseen 1 mukaan ylärajan. $2$ $n_{max,3}$

Kirjallisuus

Schneier B. 23.2 Algoritmit salaisuuden jakamiseen. Karnin - Greene - Hellman // Sovellettu kryptografia. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodi julkaisussa C. - M . : Triumf, 2002. - S. 590. - 816 s. - 3000 kappaletta. - ISBN 5-89392-055-4 .
Yvo Desmedt, Brian King, Berry Schoenmakers. Revisiting the Karnin, Greene ja Hellman Bounds // ICITS '08 Proceedings of the 3rd International Conference on Information Theoretic Security. - 2008. - S. 183-198 . — ISBN 978-3-540-85092-2 . - doi : 10.1007/978-3-540-85093-9_18 .
Karnin ED, Greene J., Hellman ME Salaisista jakamisjärjestelmistä // Information Theory, IEEE Transactions on. - 2003. - S. 35-41 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1983.1056621 .
Stinson, D. R. Kryptografia: teoria ja käytäntö. - Chapman ja Hall/CRC, 2005. - ISBN 978-1584885085 .