Schéma Karnin-Green-Hellman

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 16. října 2018; kontroly vyžadují 52 úprav .

Schéma Karnin-Green-Hellman je prahové tajné schéma sdílení založené na řešení soustav rovnic . Autory jsou Ehud D. Karnin , Jonathan W. Greene a Martin E. Hellman .

Úvod

Schéma sdílení prahového tajemství na konečných polích je schéma pro výměnu tajného klíče mezi účastníky takovým způsobem, že kterýkoli z nich může získat tajemství, ale kterákoli skupina nebo méně ne. Schéma se skládá ze dvou fází. V první fázi, alokační fázi , nějaká strana (nazývaná dodavatel ) vytvoří akcie pomocí alokačního algoritmu . U každého odevzdá dodavatel osobně účastnický podíl účastníkovi . Druhá fáze, nazývaná fáze obnovy , nastává, když účastníci chtějí obnovit tajný klíč . $k$ $n$ $t$ $t-1$ $s_1, s_2, \tečky, s_n$ $D$ $i$ $s_{i}$ $P_{i}$ $t$ $P_{i_1}, P_{i_2}, \dots, P_{i_t}$ $k$

Typy prahových schémat

Prahové schéma sdílení tajných informací se říká , že je dokonalé , pokud alespoň strany mohou získat tajemství, ale žádná skupina nebo méně stran ne. $t$ $t-1$
Prahové schéma sdílení tajných informací se nazývá lineární , pokud je tajemství získáno lineární kombinací sázek. $k$ $t$
Prahové schéma sdílení tajného klíče se nazývá ideální , pokud je velikost podílů stejná jako velikost tajného klíče . $k$
Perfektní, ideální a lineární prahové tajné schéma sdílení se nazývá PIL (perfect, ideal and linear) prahové tajné schéma sdílení.

Schéma prahování PIL může být specifikováno z hlediska vlastností distribuční matice $D:$

1.Úplnost - každá skupina, která obsahuje alespoň členů, může vypočítat tajenku . Všechny řádky distribuční matice tedy musí mít interval, který zahrnuje řádek $t$ $k$ $t$ $D$

\left[ 1, 0, 0, \tečky, 0 \right]

2. Důvěrnost – žádná skupina s méně než členy nemůže získat informace o tajném klíči . Jinými slovy, nebo méně řádků distribuční matice nemůže zahrnovat interval, který zahrnuje řádek $t$ $k$ $t-1$ $D$

\left[ 1, 0, 0, \tečky, 0 \right]

Popis

Uvažujme konečné pole . Nechte jednoduchý prvek a nechte $\mathrm{GF}(q^{m})$ $\alpha$ $\mathrm{GF}(q^{m})$

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

Poskytovatel náhodně vybírá z . $a_{1},a_{2},\tečky ,a_{{t-1}}$ $\mathrm{GF}(q^{m})$

Potom vynese vlastní kapitál následovně $n$ $s_{i}$

\left[ \begin{array}{c} s_{1}\\s_{2}\\\vdots \\s_{r}\\s_{r+1} \\ \end{array}\right] = \quad\left[\begin{array}{cccc} 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] \ vlevo[ \begin{array}{c} k\\a_1\\a_2\\\vdots\\a_{t-1}\\ \end{array}\right]

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

Poskytovatel pak pošle účastníkovi a ujistí se, že všechny řádky matice , označené jako , tvoří invertibilní matici . $s_{i}$ $P_{i}$ $t$ $D$ $D_{i_1, i_2, \tečky, i_t}$ $t\krát t$

Tedy , kde vektor je sloupec skládající se z . $\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}}},\tečky ,s_{{i_{t}}}$

Tajemství tak lze vypočítat. $k$

Pro žádné řádky matice nebude zahrnut řádek řádek $t-1$ $D$ $[{\begin{array}{cccc}\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)).$

To znamená, že méně nebo méně účastníků nemůže získat žádné informace o tajemství . Proto je možné vytvořit prahové tajné schéma sdílení pro , kde , to znamená, že počet účastníků se může rovnat velikosti pole. $t-1$ $k$ $r+1$ $r+1=\mid {\mathbb {F}}\mid$ $n$

Z hlediska stanovení maxima tedy můžeme říci, že schéma Karnin-Green-Hellman je efektivnější než schéma Shamir . $n$

Příklad optimálního schématu

$n_{{max,t}}$ je největší , pro které je možné sestavit schéma tajného sdílení prahových hodnot PIL přes konečné pole . $n$ $(t,n)-$ ${\mathbb {F}}$
$D$ - distribuční matice PIL - schéma sdílení tajného prahu nad konečným polem je zapsáno v normální formě KGH , pokud splňuje následující rovnost: $(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]

Pro jakýkoli PIL , prahové tajné schéma sdílení přes konečné pole , lze distribuční matici zapsat v normální formě KGH. $(t,n)$ ${\mathbb {F}}$ $D$

Věta 1. Řekněme, že máme tajný prostor = = ${\mathcal {S))$ ${\mathbb {F}}$ $\mathrm{GF}(q^{m})$

Pak vyhovuje: $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

Věta 2. Nechť je konečné pole a . Pak je tu spolehlivý PIL - prahové tajné schéma sdílení přes pole . $\mathbb {F} =\mathrm {GF} (2^{m})$ $n=\mid \mathbb {F} \mid +1$ $(3,n)$ ${\mathbb {F}}$

Důkaz. Charakteristikou oboru je . Všechna pole netriviálních prvků (prvky, které se nerovnají nebo ) mají násobící pořadí větší než . Dovolit být prvky pole se nerovnají nebo . $\mathbb {F} =\mathrm {GF} (2^{m})$ $2$ $0$ $jeden$ ${\mathbb {F}}$ $2$ ${\displaystyle x_{1},x_{2},\cdots ,x_{\mid \mathbb {F} \mid -2))$ ${\mathbb {F}}$ $0$ $jeden$

Potom bude mít distribuční matice následující tvar:

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]

Tedy je velikost matice PIL prahového tajného schématu sdílení $D$ $(3,n)-$ $(\mid \mathbb {F} \mid +1)\times 3.$

Zvažte úplnost .

Řádky matice číslujeme shora dolů . $D$ $jeden$ $n$

Případ I. Jakékoli 3 řádky ze sady mohou získat tajemství díky invertibilitě Vandermondovy matice . $\{1,\cdots ,n-2\}$
Případ II. Řekněme dané řetězce a a ještě jeden řetězec ze sady . Pak je zřejmé, že tajemství lze získat zpět. $\left[0,1,0\right]$ $\left[0,0,1\right]$ $\{1,\cdots ,n-2\}$
Případ III. Předpokládejme, že jeden z řetězců patří do množiny a zbylé dva jsou vybrány z . Potom pomocí transformací elementárních řetězců můžete řetězec z množiny odstranit . Výsledkem bude Vandermontův systém velikosti , který je reverzibilní. ${\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 krát 2$

Je prokázána vlastnost úplnosti. Obdobně funguje i prokazování mlčenlivosti .

Pro každé pole s charakteristikou se ukazuje, že: ${\mathbb {F}}$ $2$

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

V důsledku toho pro pole s charakteristikou ve schématu Karnin–Green–Hellman podle věty 1 dosahuje horní hranice. $2$ $n_{max,3}$

Literatura

Schneier B. 23.2 Algoritmy pro sdílení tajemství. Karnin - Greene - Hellman // Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M. : Triumf, 2002. - S. 590. - 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 .
Yvo Desmedt, Brian King, Berry Schoenmakers. Revisiting the Karnin, Greene and Hellman Bounds // ICITS '08 Sborník z 3. mezinárodní konference o informační teoretické bezpečnosti. - 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 O systémech tajného sdílení // Information Theory, IEEE Transactions on. - 2003. - S. 35-41 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1983.1056621 .
Stinson, D. R. Kryptografie: teorie a praxe. - Chapman a Hall/CRC, 2005. - ISBN 978-1584885085 .