Karnin-Green-Hellman-schema

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 16 oktober 2018; kontroller kräver 52 redigeringar .

Karnin-Green-Hellman- schemat är ett hemligt delningssystem för tröskelvärden baserat på att lösa ekvationssystem . Författarna är Ehud D. Karnin , Jonathan W. Greene och Martin E. Hellman .

Introduktion

Ett schema för tröskelhemlighetsdelning på ändliga fält är ett schema för att utbyta en hemlig nyckel mellan deltagare på ett sådant sätt att vilken som helst av dem kan återställa hemligheten, men vilken grupp av eller mindre kan inte. Systemet består av två faser. I den första fasen, allokeringsfasen , skapar någon part (kallad leverantören ) aktier med hjälp av en allokeringsalgoritm . För varje ger leverantören personligen deltagarandelen till deltagaren . Den andra fasen, kallad återställningsfasen , inträffar när deltagarna vill återställa den hemliga nyckeln . $k$ $n$ $t$ $t-1$ $s_1, s_2, \dots, s_n$ $D$ $i$ $si}$ $Pi}$ $t$ $P_{i_1}, P_{i_2}, \dots, P_{i_t}$ $k$

Typer av tröskelscheman

Ett system för delning av tröskelhemligheter sägs vara perfekt om åtminstone parterna kan återställa hemligheten, men vilken grupp av eller färre parter som helst kan det inte. $t$ $t-1$
Ett schema för tröskelhemlighetsdelning kallas linjärt om hemligheten återvinns genom att ta en linjär kombination av insatser. $k$ $t$
Ett system för tröskelhemlighetsdelning kallas ideal om storleken på aktierna är densamma som hemlighetens . $k$
Ett perfekt, ideal och linjärt tröskelhemlighetsdelningsschema kallas PIL (perfect, ideal and linear) tröskelhemlighetsdelningsschema.

PIL-tröskelschemat kan specificeras i termer av egenskaper hos distributionsmatrisen $D:$

1.Fullständighet - vilken grupp som helst som innehåller minst medlemmar kan beräkna hemligheten . Således måste alla rader i distributionsmatrisen ha ett intervall som inkluderar raden $t$ $k$ $t$ $D$

\left[ 1, 0, 0, \dots, 0 \right]

2. Sekretess - ingen grupp med mindre än medlemmar kan få information om den hemliga nyckeln . Med andra ord, eller färre rader i distributionsmatrisen kan inte inkludera ett intervall som inkluderar raden $t$ $k$ $t-1$ $D$

\left[ 1, 0, 0, \dots, 0 \right]

Beskrivning

Betrakta ett ändligt fält . Låt ett enkelt element och låt $\mathrm{GF}(q^{m})$ $\alfa$ $\mathrm{GF}(q^{m})$

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

Leverantören väljer slumpmässigt från . $a_{1},a_{2},\dots,a_{{t-1}}$ $\mathrm{GF}(q^{m})$

Den plottar sedan eget kapital enligt följande $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 & \ 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] \ vänster[ \begin{array}{c} k\\a_1\\a_2\\\vdots\\a_{t-1}\\ \end{array}\right]

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

Leverantören skickar sedan till deltagaren och ser till att alla rader i matrisen , betecknade som , bildar en inverterbar matris . $si}$ $Pi}$ $t$ $D$ $D_{i_1, i_2, \dots, i_t}$ $t\ gånger t$

Därav, , där vektorn är en kolumn som består av . $\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 hemligheten beräknas. $k$

Dessutom, för alla rader av matris , rad , kommer inte att inkluderas 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 innebär att färre eller färre deltagare inte kan få någon information om hemligheten . Därför är det möjligt att bygga ett tröskelhemligt delningsschema för , där det vill säga antalet deltagare kan vara lika med fältstorleken. $t-1$ $k$ $r+1$ $r+1=\mid {\mathbb {F}}\mid$ $n$

Sålunda, ur synvinkeln att bestämma maximum , kan vi säga att Karnin-Green-Hellman-schemat är mer effektivt än Shamir-schemat . $n$

Ett exempel på ett optimalt schema

$n_{{max,t}}$ är den största för vilken det är möjligt att konstruera ett hemligt delningsschema för PIL- tröskel över ett ändligt fält . $n$ $(t,n)-$ ${\mathbb {F}}$
$D$ - distributionsmatris PIL - tröskelhemlighetsdelningsschema över det sista fältet skrivs i KGH normal form om det uppfyller följande likhet: $(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 &&1\\\0&0 cdots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\cdots &1\\\end{array}}\right]

För vilken PIL som helst , ett hemligt delningsschema för tröskelvärden över ett ändligt fält , kan distributionsmatrisen skrivas i KGH-normalform. $(t,n)$ ${\mathbb {F}}$ $D$

Sats 1. Låt oss säga att vi har ett hemligt utrymme = = ${\mathcal {S))$ ${\mathbb {F}}$ $\mathrm{GF}(q^{m})$

Då tillfredsställer: $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

Sats 2. Låta vara ett ändligt fält och . Sedan finns det ett tillförlitligt PIL - ett hemligt delningssystem för tröskelvärden över fältet . $\mathbb {F} =\mathrm {GF} (2^{m})$ $n=\mid \mathbb {F} \mid +1$ $(3,n)$ ${\mathbb {F}}$

Bevis. Egenskapen för fältet är . Alla icke-triviala element (element som inte är lika med eller ) fält har en multiplikationsordning större än . Låta vara fältelement som inte är lika med eller . $\mathbb {F} =\mathrm {GF} (2^{m})$ $2$ $0$ $ett$ ${\mathbb {F}}$ $2$ ${\displaystyle x_{1},x_{2},\cdots ,x_{\mid \mathbb {F} \mid -2))$ ${\mathbb {F}}$ $0$ $ett$

Då kommer distributionsmatrisen att ha följande 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 är PIL- matrisen för tröskelhemlighetsdelningsschemat av storlek $D$ $(3,n)-$ $(\mid \mathbb {F} \mid +1)\ gånger 3.$

Tänk på fullständighet .

Vi numrerar matrisens rader uppifrån och ner. $D$ $ett$ $n$

Fall I. Alla 3 rader från setet kan återställa hemligheten på grund av Vandermonde-matrisens inverterbarhet . $\{1,\cdots ,n-2\}$
Fall II. Låt oss säga givna strängar och och ytterligare en sträng från uppsättningen . Då är det uppenbart att hemligheten kan återfinnas. $\left[0,1,0\right]$ $\left[0,0,1\right]$ $\{1,\cdots ,n-2\}$
Fall III. Anta att en av strängarna tillhör uppsättningen och de andra två är valda från . Sedan, med hjälp av elementära strängtransformationer, kan du ta bort strängen från uppsättningen . Som ett resultat kommer det att finnas ett Vandermont-system av storlek , som är 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 gånger 2$

Fullständighetsegenskapen är bevisad. Bevis på sekretess fungerar på liknande sätt.

För alla fält med en egenskap visar det sig att: ${\mathbb {F}}$ $2$

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

Följaktligen, för fält med karakteristik i Karnin-Green-Hellman-schemat, enligt sats 1, når den den övre gränsen. $2$ $n_{max,3}$

Litteratur

Schneier B. 23.2 Algoritmer för att dela en hemlighet. Karnin - Greene - Hellman // Tillämpad kryptografi. Protokoll, algoritmer, källkod i C-språk = Applied Cryptography. Protocols, Algoritms and Source Code in C. - M . : Triumf, 2002. - S. 590. - 816 sid. - 3000 exemplar. - 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 hemliga delningssystem // Information Theory, IEEE Transactions on. - 2003. - S. 35-41 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1983.1056621 .
Stinson, D. R. Kryptografi: teori och praktik. - Chapman och Hall/CRC, 2005. - ISBN 978-1584885085 .