Karnin-Green-Hellman-ordningen

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 16. oktober 2018; checks kræver 52 redigeringer .

Karnin-Green-Hellman- skemaet er et tærskelhemmeligt delingsskema baseret på løsning af ligningssystemer . Forfatterne er Ehud D. Karnin , Jonathan W. Greene og Martin E. Hellman .

Introduktion

Et tærskelhemmelighedsdelingsskema på begrænsede felter er et skema til udveksling af en hemmelig nøgle mellem deltagere på en sådan måde, at enhver af dem kan genvinde hemmeligheden, men enhver gruppe af eller mindre kan ikke. Ordningen består af to faser. I den første fase, allokeringsfasen , opretter en part (kaldet leverandøren ) aktier ved hjælp af en allokeringsalgoritme . For hver giver leverandøren personligt deltagelsesandelen til deltageren . Den anden fase, kaldet gendannelsesfasen , opstår, når deltagerne ønsker at gendanne den hemmelige nøgle . $k$ $n$ $t$ $t-1$ $s_1, s_2, \dots, s_n$ $D$ $jeg$ $s_{i}$ $P_{i}$ $t$ $P_{i_1}, P_{i_2}, \dots, P_{i_t}$ $k$

Typer af tærskelordninger

Et tærskelhemmelighedsdelingssystem siges at være perfekt , hvis i det mindste parterne kan genvinde hemmeligheden, men enhver gruppe af eller færre parter kan ikke. $t$ $t-1$
Et tærskelhemmelighedsdelingssystem kaldes lineært , hvis hemmeligheden genfindes ved at tage en lineær kombination af indsatser. $k$ $t$
En tærskel hemmelig delingsordning kaldes ideel , hvis størrelsen af aktierne er den samme som hemmelighedens . $k$
En perfekt, ideel og lineær tærskelhemmelig delingsordning kaldes PIL (perfekt, ideel og lineær) tærskelhemmelighedsdelingsordning.

PIL-tærskelordningen kan specificeres med hensyn til fordelingsmatricens egenskaber $D:$

1. Fuldstændighed - enhver gruppe, der omfatter mindst medlemmer, kan beregne hemmeligheden . Derfor skal alle rækker i fordelingsmatricen have et interval, der inkluderer rækken $t$ $k$ $t$ $D$

\venstre[ 1, 0, 0, \prikker, 0 \højre]

2. Fortrolighed - ingen gruppe med færre end medlemmer kan få oplysninger om den hemmelige nøgle . Med andre ord, eller færre rækker i distributionsmatrixen kan ikke inkludere et interval, der inkluderer rækken $t$ $k$ $t-1$ $D$

\venstre[ 1, 0, 0, \prikker, 0 \højre]

Beskrivelse

Overvej et begrænset felt . Lad et simpelt element og lad $\mathrm{GF}(q^{m})$ $\alfa$ $\mathrm{GF}(q^{m})$

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

Udbyderen vælger tilfældigt fra . $a_{1},a_{2},\dots,a_{{t-1}}$ $\mathrm{GF}(q^{m})$

Det plotter derefter egenkapitalen som følger $n$ $s_{i}$

\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 & \ alpha_{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] \ venstre[ \begin{array}{c} k\\a_1\\a_2\\\vdots\\a_{t-1}\\ \end{array}\right]

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

Udbyderen sender derefter til deltageren og sikrer sig, at alle rækker i matrixen , betegnet som , danner en inverterbar matrix . $s_{i}$ $P_{i}$ $t$ $D$ $D_{i_1, i_2, \dots, i_t}$ $t\ gange t$

Derfor, , hvor vektoren er en kolonne bestående af . $\bar{y} = D_{i_1, i_2, \dots, 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}}}$

Således kan hemmeligheden beregnes. $k$

For nogen rækker af matrix , vil række , heller ikke blive inkluderet i $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)).$

Det betyder, at færre eller færre deltagere ikke kan få information om hemmeligheden . Derfor er det muligt at bygge et tærskelhemmeligt delingsskema for , hvor det vil sige antallet af deltagere kan være lig med feltstørrelsen. $t-1$ $k$ $r+1$ $r+1=\mid {\mathbb {F}}\midt$ $n$

Fra synspunktet om at bestemme maksimum , kan vi sige, at Karnin-Green-Hellman-ordningen er mere effektiv end Shamir-ordningen . $n$

Et eksempel på et optimalt skema

$n_{{max,t}}$ er den største , for hvilken det er muligt at konstruere et PIL -tærskel hemmeligt delingsskema over et begrænset felt . $n$ $(t,n)-$ ${\mathbb {F}}$
$D$ - distributionsmatrix PIL - tærskel hemmelig delingsskema over det endelige felt er skrevet i KGH normal form, hvis det opfylder følgende lighed: $(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 }\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{r2}&x_{r3}&\cdots &x_{rt}\\1&1&1&\cdots &1\\0&1&0&\cdots &&0\\\0&0 cdots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\cdots &1\\\end{array}}\right]

For enhver PIL , et tærskelhemmeligt delingsskema over et begrænset felt , kan distributionsmatrixen skrives i KGH normal form. $(t,n)$ ${\mathbb {F}}$ $D$

Sætning 1. Lad os sige, at vi har et hemmeligt rum = = ${\mathcal {S))$ ${\mathbb {F}}$ $\mathrm{GF}(q^{m})$

Så tilfredsstiller: $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

Sætning 2. Lade være et begrænset felt og . Så er der en pålidelig PIL - en tærskel hemmelig delingsordning over marken . $\mathbb {F} =\mathrm {GF} (2^{m})$ $n=\mid \mathbb {F} \mid +1$ $(3,n)$ ${\mathbb {F}}$

Bevis. Det karakteristiske ved feltet er . Alle ikke-trivielle elementer (elementer, der ikke er lig med eller ) felter har en multiplikationsrækkefølge større end . Lad være feltelementer ikke lig med eller . $\mathbb {F} =\mathrm {GF} (2^{m})$ $2$ $0$ $en$ ${\mathbb {F}}$ $2$ ${\displaystyle x_{1},x_{2},\cdots ,x_{\mid \mathbb {F} \mid -2))$ ${\mathbb {F}}$ $0$ $en$

Så vil fordelingsmatricen have følgende form:

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]

Således er PIL -matrixen af tærskelhemmelighedsdelingsskemaet af størrelse $D$ $(3,n)-$ $(\mid \mathbb {F} \mid +1)\ gange 3.$

Overvej fuldstændighed .

Vi nummererer rækkerne i matrixen fra top til bund. $D$ $en$ $n$

Case I. Enhver 3 rækker fra sættet kan genfinde hemmeligheden på grund af Vandermonde-matricens inverterbarhed . $\{1,\cdots ,n-2\}$
Sag II. Lad os sige givne strenge og og en streng mere fra sættet . Så er det åbenlyst, at hemmeligheden kan genfindes. $\left[0,1,0\right]$ $\left[0,0,1\right]$ $\{1,\cdots ,n-2\}$
Sag III. Antag, at en af strengene tilhører sættet , og de to andre er valgt fra . Derefter kan du ved hjælp af elementære strengtransformationer fjerne strengen fra sættet . Som et resultat vil der være et Vandermont-system af størrelse , som er reversibelt. ${\displaystyle \{\left[0,1,0\right],\left[0,0,1\right]\))$ $\{1,\cdots ,n-2\}.$ ${\displaystyle \{\left[0,1,0\right],\left[0,0,1\right]\))$ $2 gange 2$

Helhedsegenskaben er bevist. Bevis for fortrolighed fungerer på samme måde.

For ethvert felt med en karakteristik viser det sig, at: ${\mathbb {F}}$ $2$

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

For felter med karakteristika i Karnin-Green-Hellman-skemaet, ved sætning 1, når det følgelig den øvre grænse. $2$ $n_{max,3}$

Litteratur

Schneier B. 23.2 Algoritmer til at dele en hemmelighed. Karnin - Greene - Hellman // Anvendt kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protokoller, algoritmer og kildekode i C. - M. : Triumf, 2002. - S. 590. - 816 s. - 3000 eksemplarer. - ISBN 5-89392-055-4 .
Yvo Desmedt, Brian King, Berry Schoenmakers. Revisiting the Karnin, Greene and 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 Om hemmelige delingssystemer // Information Theory, IEEE Transactions on. - 2003. - S. 35-41 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1983.1056621 .
Stinson, D. R. Kryptografi: teori og praksis. - Chapman og Hall/CRC, 2005. - ISBN 978-1584885085 .