Schema Karnin-Green-Hellman

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 16 octombrie 2018; verificările necesită 52 de modificări .

Schema Karnin-Green-Hellman este o schemă de partajare a secretelor de prag bazată pe rezolvarea sistemelor de ecuații . Autorii sunt Ehud D. Karnin , Jonathan W. Greene și Martin E. Hellman .

Introducere

O schemă de partajare a secretelor de prag pe câmpuri finite este o schemă pentru schimbul unei chei secrete între participanți, astfel încât oricare dintre ei să poată recupera secretul, dar orice grup sau mai puțin nu poate. Schema constă din două faze. În prima fază, faza de alocare , o parte (numită furnizor ) creează acțiuni folosind un algoritm de alocare . Pentru fiecare , furnizorul acordă personal cota de participare participantului . A doua fază, numită faza de recuperare , are loc atunci când participanții doresc să recupereze cheia secretă . $k$ $n$ $t$ $t-1$ $s_1, s_2, \dots, s_n$ $D$ $i$ $si}$ $P_{i}$ $t$ $P_{i_1}, P_{i_2}, \dots, P_{i_t}$ $k$

Tipuri de scheme de prag

Se spune că o schemă de partajare a secretelor de prag este perfectă dacă cel puțin părțile pot recupera secretul, dar orice grup de părți sau mai puține nu pot. $t$ $t-1$
O schemă de partajare a secretelor de prag se numește liniară dacă secretul este recuperat prin luarea unei combinații liniare de mize. $k$ $t$
O schemă de partajare a secretelor de prag este numită ideală dacă dimensiunea acțiunilor este aceeași cu cea a secretului . $k$
O schemă de partajare secretă cu prag perfectă, ideală și liniară se numește schemă de partajare secretă cu prag PIL (perfect, ideal and linear) .

Schema de prag PIL poate fi specificată în termeni de proprietăți ale matricei de distribuție $D:$

1.Completitudine - orice grup care include cel puțin membri poate calcula secretul . Astfel, orice rând din matricea de distribuție trebuie să aibă un interval care să includă rândul $t$ $k$ $t$ $D$

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

2. Confidențialitate - niciun grup cu mai puțin de membri nu poate obține informații despre cheia secretă . Cu alte cuvinte, sau mai puține rânduri ale matricei de distribuție nu pot include un interval care include rândul $t$ $k$ $t-1$ $D$

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

Descriere

Luați în considerare un câmp finit . Lasă un element simplu și lasă $\mathrm{GF}(q^{m})$ $\alfa$ $\mathrm{GF}(q^{m})$

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

Furnizorul alege aleatoriu dintre . $a_{1},a_{2},\dots ,a_{{t-1}}$ $\mathrm{GF}(q^{m})$

Apoi grafică capitalul propriu după cum urmează $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] \ stânga[ \begin{matrice}{c} k\\a_1\\a_2\\\vdots\\a_{t-1}\\ \end{matrice}\right]

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

Furnizorul trimite apoi participantului , asigurându-se că orice rânduri ale matricei , notate ca , formează o matrice inversabilă . $si}$ $P_{i}$ $t$ $D$ $D_{i_1, i_2, \dots, i_t}$ $t\ ori t$

Prin urmare, , unde vectorul este o coloană formată din . $\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}}}$

Astfel, secretul poate fi calculat. $k$

De asemenea, pentru orice rând de matrice , rândul nu va fi inclus în $t-1$ $D$ $[{\begin{array}{ccccc}\gamma ,0,0,\cdots ,0\\\end{array}}]$ $\forall \gamma \in \mathrm {GF} (q^{m})\setminus \{0\)$ $D_{i_{1},i_{2},\dots,i_{t-1)).$

Aceasta înseamnă că mai puțini sau mai puțini participanți nu pot obține informații despre secret . Prin urmare, este posibil să se construiască o schemă de partajare secretă de prag pentru , unde , adică numărul de participanți poate fi egal cu dimensiunea câmpului. $t-1$ $k$ $r+1$ $r+1=\mid {\mathbb {F}}\mid$ $n$

Astfel, din punctul de vedere al determinării maximului , putem spune că schema Karnin-Green-Hellman este mai eficientă decât schema Shamir . $n$

Un exemplu de schemă optimă

$n_{{max,t}}$ este cel mai mare pentru care este posibil să se construiască o schemă de partajare secretă a pragului PIL pe un câmp finit . $n$ $(t,n)-$ ${\mathbb {F}}$
$D$ - matricea de distribuție PIL - schema de partajare secretă prag peste câmpul final se scrie în forma normală KGH dacă satisface următoarea egalitate: $(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&1&\ cdots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\cdots &1\\\end{array}}\right]

Pentru orice PIL , o schemă de partajare a secretelor de prag pe un câmp finit , matricea de distribuție poate fi scrisă în forma normală KGH. $(t,n)$ ${\mathbb {F}}$ $D$

Teorema 1. Să presupunem că avem un spațiu secret = = ${\mathcal {S))$ ${\mathbb {F}}$ $\mathrm{GF}(q^{m})$

Apoi satisface: $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

Teorema 2. Fie un câmp finit și . Apoi există un PIL de încredere - o schemă de partajare a secretelor de prag pe teren . $\mathbb {F} =\mathrm {GF} (2^{m})$ $n=\mid \mathbb {F} \mid +1$ $(3,n)$ ${\mathbb {F}}$

Dovada. Caracteristica domeniului este . Toate câmpurile elementelor netriviale (elementele care nu sunt egale cu sau ) au o ordine multiplicativă mai mare decât . Fie elemente de câmp care nu sunt egale cu sau . $\mathbb {F} =\mathrm {GF} (2^{m})$ $2$ $0$ $unu$ ${\mathbb {F}}$ $2$ $x_{1},x_{2},\cdots,x_{\mid \mathbb {F} \mid -2)$ ${\mathbb {F}}$ $0$ $unu$

Apoi matricea de distribuție va lua următoarea 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]

Astfel, este matricea PIL a schemei de partajare secretă de prag de dimensiune $D$ $(3,n)-$ $(\mid \mathbb {F} \mid +1)\times 3.$

Luați în considerare completitudinea .

Numerotăm rândurile matricei de sus în jos. $D$ $unu$ $n$

Cazul I. Orice 3 rânduri din set poate recupera secretul datorită invertibilității matricei Vandermonde . $\{1,\cdots ,n-2\}$
Cazul II. Să spunem șiruri date și și încă un șir din set . Atunci este evident că secretul poate fi recuperat. $\left[0,1,0\right]$ $\left[0,0,1\right]$ $\{1,\cdots ,n-2\}$
Cazul III. Să presupunem că unul dintre șiruri aparține mulțimii , iar celelalte două sunt selectate din .Apoi, folosind transformări elementare de șiruri, puteți elimina șirul din mulțime . Ca urmare, va exista un sistem Vandermont de dimensiuni , care este reversibil. ${\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]\))$ $de 2 ori 2$

Proprietatea de completitudine este dovedită. Dovada confidențialității funcționează în mod similar.

Pentru orice domeniu cu o caracteristică , rezultă că: ${\mathbb {F}}$ $2$

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

În consecință, pentru câmpurile cu caracteristică în schema Karnin–Green–Hellman, prin Teorema 1, aceasta atinge limita superioară. $2$ $n_{max,3}$

Literatură

Schneier B. 23.2 Algoritmi pentru partajarea unui secret. Karnin - Greene - Hellman // Criptografie aplicată. Protocoale, algoritmi, cod sursă în limbaj C = Criptografie aplicată. Protocoale, algoritmi și cod sursă în C. - M. : Triumf, 2002. - S. 590. - 816 p. - 3000 de exemplare. - ISBN 5-89392-055-4 .
Yvo Desmedt, Brian King, Berry Schoenmakers. Revizuirea limitelor Karnin, Greene și Hellman // 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 Despre sistemele de partajare secretă // Teoria informațiilor, Tranzacțiile IEEE pe. - 2003. - S. 35-41 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1983.1056621 .
Stinson, D. R. Criptografia: teorie și practică. - Chapman și Hall/CRC, 2005. - ISBN 978-1584885085 .