Tajná schémata sdílení pro libovolné přístupové struktury

Tajná schémata sdílení pro libovolné přístupové struktury (angl. Secret sharing with generalized access structure ) - tajná schémata sdílení , která vám umožňují specifikovat libovolnou množinu skupin účastníků (kvalifikované podmnožiny), které mají schopnost obnovit tajemství (struktura přístupu).

Historie

V roce 1979 navrhl izraelský kryptoanalytik Adi Shamir schéma sdílení tajného prahu mezi stranami, které má následující vlastnosti: $n$

K obnovení tajemství stačí více než jedna strana. $k$
Žádná a stále méně stran bude moci získat jakékoli informace o tajemství. [jeden] $k-1$

Tento přístup našel mnoho aplikací. Například pro víceuživatelskou autorizaci v infrastruktuře veřejného klíče , v digitální steganografii pro skrytý přenos informací v digitálních obrázcích, aby se čelilo útokům na postranní kanály při implementaci algoritmu AES .

Složitější aplikace, kde určité skupiny účastníků mohou mít přístup a jiné ne, však do modelu prahového schématu nezapadají. K vyřešení tohoto problému byla vyvinuta schémata tajného sdílení pro libovolné přístupové struktury.

Japonští vědci Mitsuro Ito, Akiro Saito a Takao Nishizeki jako první studovali tajné sdílení pro libovolné přístupové struktury a v roce 1987 navrhli své schéma. [2] Jejich myšlenku rozvinuli Josh Benalo a Jerry Leichter, kteří v roce 1988 navrhli separační schéma pro monotónní struktury. [3] V roce 1989 Ernest Brickell navrhl schéma, ve kterém účastníci nedostávají podíly na tajemství, ale jejich lineární kombinace. [čtyři]

Definice použitých pojmů

Dealer je účastníkem postupu (protokolu), který se znalostí tajemství vypočítá podíly na tajemství a tyto podíly rozdělí ostatním účastníkům.

Kvalifikovaná podmnožina je sada členů skupiny, pro kterou je povoleno obnovení tajných informací.

Příkladem ilustrujícím vznik kvalifikovaných podmnožin je sdílení tajemství mezi manažery. V případě, že tajemství mohou získat buď všichni tři vedoucí pracovníci nebo kterýkoli výkonný ředitel a kterýkoli viceprezident nebo prezident sám, [1] kvalifikovanou podskupinou budou prezident, viceprezident a výkonný ředitel nebo jakékoli tři vedoucí pracovníci.

Přístupová struktura je výčet kvalifikovaných a nekvalifikovaných podmnožin.

Nechť je množina členů skupiny, je počet členů skupiny a je množina sestávající ze všech možných podmnožin členů skupiny. Nechť je množina skládající se z podmnožin účastníků, kteří mají povoleno získat tajemství (kvalifikované skupiny účastníků), sada skládající se z podmnožin účastníků, kteří nemohou získat tajemství. Přístupová struktura je označena jako ( , ) . $A$ $n$ $2^{[n]}$ $\Gamma$ $\Delta$ $\Gamma$ $\Delta$

O přístupové struktuře se říká, že je monotónní , pokud jsou všechny nadmnožiny kvalifikovaných podmnožin také zahrnuty v , tj. $\Gamma$ $A\in \Gamma ,A\subseteq B\subseteq P\Rightarrow B\in \Gamma$

Předpokládejme , že ( , ) je $\Gamma$ $\Delta$ přístupová struktura na . se nazývá minimální kvalifikovaná podmnožina , pokud vždy, když . Množina minimálních kvalifikovaných podmnožin se označuje a nazývá se základ . Minimální kvalifikovaná podmnožina jednoznačně definuje přístupovou strukturu. $A$ $B\in \Gamma$ $C\not \in \Gamma$ $C\subset B$ $\Gamma$ $\Gamma _{min}$ $\Gamma$

Schéma Benalo-Leichter

Nechť je dána struktura monotónního přístupu a je to sada minimálních kvalifikovaných podmnožin odpovídajících . Nechte _ Pro každý , jsou pro členy této podmnožiny vypočteny tajné podíly pomocí schématu tajného sdílení s libovolným prahem. $A$ $\Gamma _{min}$ $A$ $\Gamma _{min}=\{A_{1},A_{2},...,A_{m}\}$ $A_{i}$ $s_{i1},s_{i2},...,s_{i|A|}$ $(|A_{i}|,|A_{i}|)$

Podíl tajemství je převeden na příslušného účastníka. Výsledkem je, že každý účastník obdrží sadu tajných akcií. Tajný klíč je obnoven podle zvoleného (n, n) - prahového schématu . [3] ${\displaystyle s_{i,j))$

Příklad:

${\displaystyle \Gamma _{min}=\{\{1,2,3\},\{1,4\},\{2,4\},\{3,4\}\))$

$A_{1}=\{1,2,3\}\ \ \ \ \ A_{2}=\{1,4\}\ \ \ \ \ A_{3}=\{2,4\ }\ \ \ \ \ A_{4}=\{3,4\}$

Zde je například druhý v , takže dostane podíly na tajemství $P_{4}$ ${\displaystyle A_{2},A_{3},A_{4))$ ${\displaystyle s_{2,2},s_{3,2},s_{4,2))$

Podobně pro ostatní účastníky

$P_{1}\leftarrow s_{1,1},s_{2,1}\ \ P_{2}\leftarrow s_{1,2},s_{3,1}\ \ P_{3}\ šipka doleva s_{1,3},s_{4,1}\ \$

Nevýhodou tohoto schématu je rostoucí objem tajných akcií pro každého účastníka s nárůstem [5] [6] . $\Gamma _{min}$

Schéma Ito-Saito-Nishizeki

Ito, Saito, Nishizeki představili takzvanou techniku kumulativního pole pro monotónní přístupovou strukturu. [2]

Nechť je monotónní přístupová struktura velikosti a nechť jsou jí odpovídající maximální nekvalifikované podmnožiny účastníků. $A$ $n$ ${\displaystyle A_{1},...,A_{m))$

Kumulativní pole přístupové struktury je matice dimenzí , kde a je označeno jako . To znamená, že sloupce matice odpovídají nekvalifikovaným podmnožinám a hodnota řádků ve sloupci bude jedna, pokud prvek není zahrnut v této podmnožině. $A$ $n\krát m$ ${\displaystyle (C_{i,j}^{A})_{1\leq i\leq n,1\leq j\leq m))$ $C_{i,j}^{A}={\begin{cases}0,&{\text{if }}i\in A_{j}\\1,&{\text{if }}i \not \in A_{j}\end{cases}}$ $C^{A}$

V tomto schématu můžete použít libovolné - prahové tajné schéma sdílení s tajemstvím a odpovídajícími podíly $(m, m)$ $S$ ${\displaystyle s_{1},...,s_{m))$

Sdílené položky odpovídající tajnému klíči budou definovány jako sada : $I_{1},...,I_{n}$ $S$ $s_{j}$ ${\displaystyle I_{i}=\{s_{j}|C_{i,j}^{A}=1\))$

Tajný klíč se obnoví podle zvoleného schématu prahů . $(m, m)$

Složitost implementace tohoto schématu, dosažená v roce 2016, je . [7] $Na)$

Příklad:

Nechte ,. _ $n=4$ $\Gamma =\{\{1,2\},\{3,4\},\{1,2,3\},\{1,2,4\},\{1,3, 4\},\{2,3,4\}\}$

Odpovídající sada minimálních kvalifikovaných podmnožin $A$ ${\displaystyle \Gamma _{min}=\{\{1,2\},\{3,4\}\))$

V tomto případě a . ${\displaystyle \Delta _{max}=\{\{1,3\},\{1,4\},\{2,3\},\{2,4\}\))$ $m=4$

Kumulativní pole přístupové struktury má tvar $A$ $C^{A}={\begin{pmatrix}0&0&1&1\\1&1&0&0\\0&1&0&1\\1&0&1&0\end{pmatrix}}$

Podíly na tajemství účastníků jsou stejné $I_{1}=\{s_{3},s_{4}\};\ \ I_{2}=\{s_{1},s_{2}\};\ \ I_{3}= \{s_{2},s_{4}\};\ \ I_{4}=\{s_{1},s_{3}\}$

Tajná obnova je podobná tajné obnově v Shamirově prahovém schématu. $(4,4)$

Brickellův lineární diagram tajného sdílení

Pro přístupovou strukturu a sadu členů je vytvořena matice velikostí , ve které je délkový řetězec spojen s členem . Pro podmnožinu účastníků , která odpovídá množině řádků matice - , musí být splněna podmínka , že vektor patří do lineárního rozpětí . $A$ $P=\{P_{1},...,P_{n}\}$ $M$ $n\krát m$ $M[i]$ $m$ $i$ $x\subset \Gamma$ $M$ $M_{x}$ $(1,0,...,0)$ $M_{x}$

Dealer zvolí vektor , kde je sdílené tajemství . Tajný podíl účastníka : $r=(r_{0},...,r_{m})$ $s=r_{0}$ $i$ $s_{i}=M[i]r$

Tajné zotavení.

Je vybrán vektor délky , — vektor složený ze souřadnic odpovídajících množině účastníků . $\alpha$ $m$ $\alpha _{x}$ $\alpha$ $x\subset \Gamma$

Pro každou podmínku musí být splněno: . Poté může být tajemství obnoveno vzorcem: $x\subset \Gamma$ $\alpha _{x}M_{x}=(1,0,...,0)$

$\sum _{i\in x}s_{i}\alpha _{i}=\součet _{i\in x}(M[i]r)\alpha _{i}=(\součet _ {i\in x}\alpha _{i}M[i])r=(1,0,...,0)r=s$ [čtyři]

Příklad:

Sada minimálních kvalifikovaných podmnožin . ${\displaystyle \Gamma =\{\{1,2,3\},\{1,4\}\))$

Vhodná matice:

${\begin{pmatrix}0&1&0\\1&0&1\\0&1&-1\\1&1&0\end{pmatrix}}$

$M$ splňuje požadavek na schéma:

pro : $\{1, 2, 3\}$ $(1,0,0)=-(0,1,0)+(1,0,1)+(0,1,-1)$

pro : $\{1,4\}$ $(1,0,0)=-(0,1,0)+(1,1,0)$

Sdílení tajemství každého účastníka:

$P_{1}\leftarrow r_{1};\qquad P_{2}\leftarrow s+r_{2};\qquad P_{3}\leftarrow r_{1}-r_{2};\qquad P_ {4}\leftarrow s+r_{1}\qquad$

Tajné zotavení:

Chcete-li obnovit tajemství, vyberte $\alpha =(-1,1,1,1)$

Potom pro : $x=\{1,2,3\}$ $\alpha _{x}=(-1,1,1)$

$(-1,1,1){\begin{pmatrix}0&1&0\\1&0&1\\0&1&-1\end{pmatrix}}=(1,0,0)$

A pro : $x=\{1,4\}$ $\alpha _{x}=(-1,1)$

$(-1,1){\begin{pmatrix}0&1&0\\1&1&0\end{pmatrix}}=(1,0,0)$

Aplikace

Tato schémata se používají v protokolech podmíněného odhalení tajemství (CDS) [8] , zabezpečených distribuovaných výpočtech [9] [10] [11] , problémech s distribucí klíčů [12] a schématech autentizace více příjemců [13] .

Poznámky

↑ 1 2 Shamir A. Jak sdílet tajemství // Commun. ACM - NYC, USA. - 1979. - T. 22 . - S. 612-613 .
↑ 1 2 Ito M., Saito A., Nishizeki T. Tajné schéma sdílení realizující obecnou přístupovou strukturu // Elektronika a komunikace v Japonsku (část III: Fundamental Electronic Science). - 1987. Archivováno 23. dubna 2021.
↑ 1 2 Benaloh J., Leichter J. Generalized Secret Sharing and Monotone Functions // Advances in Cryptology - CRYPTO' 88. - 1988. - S. 27-35 .
↑ 1 2 Brickell EF Nějaká ideální schémata sdílení tajemství // Journal of Combin. Matematika. a kombinovat. Počítat. Ne. 9. - 1989. - S. 105-113 .
↑ Sreekumar A., Babusundar S. Tajná schémata sdílení pomocí vizuální kryptografie // Cochin University of Science and Technology. — 2009.
↑ Kouya TOCHIKUBO. Konstrukční metoda tajných schémat sdílení na základě autorizovaných podmnožin // Mezinárodní symposium o teorii informace a jejích aplikacích. — 2008.
↑ Lein Harna, Hsu Chingfang, Zhang Mingwua, He Tingtingc, Zhang Maoyuanc. Realizace tajného sdílení s obecnou přístupovou strukturou // Informační vědy. - 2016. - č. 367–368 . - S. 209-220 .
↑ Gertner, Y., Ishai, Y., Kushilevitz, E., Malkin, T. Ochrana soukromí dat ve schématech získávání soukromých informací // Journal of Computer and System Sciences. - 2000. - č. 60(3) . — S. 592–629 .
↑ Ben-Or, M., Goldwasser, S., Wigderson, A. Věty o úplnosti pro nekryptografické distribuované výpočty odolné proti chybám. In: Sborník příspěvků z 20. ročníku sympozia ACM na téma Theory of computing // ACM Press. - 1998. - S. 1-10 .
↑ Cramer, R., Damg˚ard, I., Maurer, U. Obecný bezpečný vícestranný výpočet z jakéhokoli lineárního schématu sdílení tajemství. // Preneel, B. (ed.) EUROCRYPT 2000. - T. 1807 . — S. 316–334 .
↑ Cramer, R., Damg˚ard, I., Nielsen, J.B. Secure Multiparty Computation and Secret Sharing: An Information Theoretic Approach. . (nedostupný odkaz)
↑ Lee, C.-Y., Wang, Z.-H., Harn, L., Chang, C.-C. Bezpečný protokol přenosu klíčů založený na tajném sdílení pro skupinovou komunikaci // IEICE Trans. inf. a Syst.. - 2011. - S. 2069–2076 .
↑ Zhang, J., Li, X., Fu, F.-W. Schéma autentizace více příjemců pro více zpráv založené na lineárních kódech // Huang, X., Zhou, J. (eds.) ISPEC 2014. LNCS. - 2014. - T. 8434 . — S. 287–301 .