Scheme de partajare secretă pentru structurile de acces arbitrar

Scheme de partajare secretă pentru structuri de acces arbitrare (ing. Partajare secretă cu structură de acces generalizată ) - scheme de partajare secretă care vă permit să specificați un set arbitrar de grupuri de participanți (subseturi calificate) care au capacitatea de a restaura secretul (structura de acces).

Istorie

În 1979, criptoanalistul israelian Adi Shamir a propus o schemă de partajare secretă de prag între părți, care are următoarele proprietăți: $n$

Pentru a restabili secretul , este suficientă mai mult de o parte. $k$
Nu și mai puține părți vor putea obține informații despre secret. [unu] $k-1$

Această abordare și-a găsit multe aplicații. De exemplu, pentru autorizarea multi-utilizator într- o infrastructură cu cheie publică , în steganografia digitală pentru transmiterea sub acoperire a informațiilor în imagini digitale, pentru a contracara atacurile pe canale laterale la implementarea algoritmului AES .

Cu toate acestea, aplicațiile mai complexe, unde anumite grupuri de participanți pot avea acces și altele nu, nu se încadrează în modelul schemei de prag. Pentru a rezolva această problemă, au fost dezvoltate scheme de partajare secretă pentru structurile de acces arbitrare.

Oamenii de știință japonezi Mitsuro Ito, Akiro Saito și Takao Nishizeki au fost primii care au studiat partajarea secretelor pentru structurile de acces arbitrare și în 1987 au propus schema lor. [2] Gândirea lor a fost dezvoltată de Josh Benalo și Jerry Leichter, care au propus în 1988 o schemă de separare a structurilor monotone. [3] În 1989, Ernest Brickell a propus o schemă în care participanților li se oferă nu părți din secret, ci combinații liniare ale acestora. [patru]

Definiția termenilor folosiți

Un dealer este un participant la o procedură (protocol) care, cunoscând secretul, calculează cotele secretului și le distribuie celorlalți participanți.

Un subset calificat este setul de membri ai grupului pentru care recuperarea secretă este permisă.

Un exemplu care ilustrează apariția unor subseturi calificate este împărtășirea unui secret între manageri. În cazul în care secretul poate fi recuperat fie de către toți cei trei directori, fie de către orice director executiv și orice vicepreședinte, fie numai de către președinte, [1] subseturile calificate vor fi președintele, vicepreședintele și executivul sau oricare trei directori.

Structura de acces este o enumerare de subseturi calificate și necalificate.

Să fie un set de membri ai grupului, să fie numărul de membri ai grupului și să fie un set format din toate subseturile posibile de membri ai grupului. Să fie un set format din subseturi de participanți cărora li se permite să recupereze secretul (seturi calificate de participanți), un set format din subseturi de participanți care nu pot recupera secretul. O structură de acces este notată ca ( , ) . $A$ $n$ $2^{[n]}$ $\Gamma$ $\Delta$ $\Gamma$ $\Delta$

Se spune că o structură de acces este monotonă dacă toate supraseturile de subseturi calificate sunt de asemenea incluse în , i.e. $\Gamma$ $A\in \Gamma, A\subseteq B\subseteq P\Rightarrow B\in \Gamma$

Să presupunem că ( , ) este $\Gamma$ $\Delta$ o structură de acces pe . se numește submulțimea minimă calificată a , dacă întotdeauna, când . Setul de submulțimi minime calificate este notat ca și se numește bază . Subsetul minim calificat definește în mod unic structura de acces. $A$ $B\in \Gamma$ $C\nu \in \Gamma$ $C\subset B$ $\Gamma$ $\Gamma _{min}$ $\Gamma$

Schema lui Benalo-Leichter

Fie dată o structură de acces monotonă și să fie mulțimea de submulțimi minime calificate corespunzătoare . Lasă . Pentru fiecare , cotele secrete sunt calculate pentru membrii acestui subset folosind orice schemă de partajare secretă cu orice prag. $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}|)$

Cota de secret este transferată participantului corespunzător. Ca rezultat, fiecare participant primește un set de acțiuni secrete. Secretul este restaurat în conformitate cu schema de prag selectată ( n , n) . [3] $s_{i,j}$

Exemplu:

${\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\}$

Aici, de exemplu, este al doilea în , așa că primește cotele secretului $P_{4}$ ${\displaystyle A_{2},A_{3},A_{4))$ ${\displaystyle s_{2,2},s_{3,2},s_{4,2))$

La fel și pentru ceilalți participanți

$P_{1}\leftarrow s_{1,1},s_{2,1}\\P_{2}\leftarrow s_{1,2},s_{3,1}\\P_{3}\ săgeată stânga s_{1,3},s_{4,1}\ \$

Dezavantajul acestei scheme este creșterea volumului de acțiuni secrete pentru fiecare participant cu o creștere [5] [6] . $\Gamma _{min}$

Schema lui Ito-Saito-Nishizeki

Ito, Saito, Nishizeki au introdus așa-numita tehnică cumulative array pentru o structură de acces monotonă. [2]

Fie o structură de acces monotonă de dimensiune și fie subseturile maxime necalificate de participanți corespunzătoare acesteia. $A$ $n$ $A_{1},...,A_{m)$

Matricea cumulativă a structurii de acces este o matrice de dimensiuni , unde și este notat ca . Adică, coloanele matricei corespund unor subseturi necalificate, iar valoarea rândurilor din interiorul coloanei va fi una dacă elementul nu este inclus în acest subset. $A$ $de n\ ori 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 \nu \în A_{j}\end{cases}}$ $C^{A}$

În această schemă, puteți utiliza orice - schema de partajare a secretelor de prag cu un secret și acțiunile corespunzătoare $(m,m)$ $S$ $s_{1},...,s_{m)$

Acțiunile corespunzătoare secretului vor fi definite ca un set : $I_{1},...,I_{n}$ $S$ $s_{j}$ $I_{i}=\{s_{j}|C_{i,j}^{A}=1\)$

Secretul este restaurat conform schemei de prag selectate . $(m,m)$

Complexitatea implementării acestei scheme, realizată în 2016, este de . [7] $Pe)$

Exemplu:

Să , . $n=4$ $\Gamma =\{\{1,2\},\{3,4\},\{1,2,3\},\{1,2,4\},\{1,3, 4\},\{2,3,4\}\}$

Setul corespunzător de subseturi minime calificate $A$ $\Gamma _{min}=\{\{1,2\},\{3,4\}\)$

În acest caz și . ${\displaystyle \Delta _{max}=\{\{1,3\},\{1,4\},\{2,3\},\{2,4\}\))$ $m=4$

Matricea cumulativă a structurii de acces are forma $A$ $C^{A}={\begin{pmatrix}0&0&1&1\\1&1&0&0\\0&1&0&1\\1&0&1&0\end{pmatrix}}$

Cotele de secret ale participanților sunt egale $I_{1}=\{s_{3},s_{4}\};\\I_{2}=\{s_{1},s_{2}\};\\I_{3}= \{s_{2},s_{4}\};\ \ I_{4}=\{s_{1},s_{3}\}$

Recuperarea secretă este similară cu recuperarea secretă din schema de prag a lui Shamir. $(4,4)$

Diagrama liniară a partajării secrete a lui Brickell

Pentru structura de acces și setul de membri , se construiește o matrice de dimensiuni în care șirul de lungime este asociat membrului . Pentru submulțimea de participanți , care corespunde setului de rânduri ale matricei- , trebuie îndeplinită condiția ca vectorul să aparțină intervalului liniar acoperit de . $A$ $P=\{P_{1},...,P_{n}\}$ $M$ $de n\ ori m$ $M[i]$ $m$ $i$ $x\subset \Gamma$ $M$ $M_{x}$ $(1,0,...,0)$ $M_{x}$

Dealerul alege un vector unde secretul partajat este . Cota secretă a participantului : $r=(r_{0},...,r_{m})$ $s=r_{0}$ $i$ $s_{i}=M[i]r$

Recuperare secretă.

Se alege un vector , de lungime , — un vector compus din coordonate corespunzatoare setului de participanti . $\alfa$ $m$ $\alpha _{x}$ $\alfa$ $x\subset \Gamma$

Pentru fiecare condiție trebuie îndeplinite: . Apoi secretul poate fi restaurat prin formula: $x\subset \Gamma$ $\alpha _{x}M_{x}=(1,0,.....,0)$

$\sum _{i\in x}s_{i}\alpha _{i}=\sum _{i\in x}(M[i]r)\alpha _{i}=(\sum _ {i\in x}\alpha _{i}M[i])r=(1,0,...,0)r=s$ [patru]

Exemplu:

Setul de subseturi minime calificate ale . $\Gamma =\{\{1,2,3\},\{1,4\}\}$

Matrice adecvată:

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

$M$ satisface cerința schemei:

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

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

Partajarea secretului fiecărui participant:

$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$

Recuperare secretă:

Pentru a restabili secretul, selectați $\alpha =(-1,1,1,1)$

Apoi pentru : $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)$

Si pentru : $x=\{1,4\}$ $\alpha _{x}=(-1,1)$

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

Aplicație

Aceste scheme sunt utilizate în protocoalele de divulgare condiționată a secretelor (CDS) [8] , în calculul distribuit securizat [9] [10] [11] , în problemele de distribuție a cheilor [12] și în schemele de autentificare cu mai multe receptori [13] .

Note

↑ 1 2 Shamir A. Cum să împărtășești un secret // Commun. ACM - NYC, SUA. - 1979. - T. 22 . - S. 612-613 .
↑ 1 2 Ito M., Saito A., Nishizeki T. Schema de partajare secretă pentru realizarea structurii generale de acces // Electronics and Communications in Japan (Partea a III-a: Fundamental Electronic Science). - 1987. Arhivat la 23 aprilie 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 Câteva scheme ideale de partajare a secretelor // Journal of Combin. Matematică. și combină. Calculator. Nu. 9. - 1989. - S. 105-113 .
↑ Sreekumar A., Babusundar S. Secret Sharing Schemes using Visual Cryptography // Cochin University of Science and Technology. — 2009.
↑ Kouya TOCHIKUBO. O metodă de construcție a schemelor de partajare secretă bazată pe subseturi autorizate // Simpozion internațional despre teoria informației și aplicațiile sale. — 2008.
↑ Lein Harna, Hsu Chingfang, Zhang Mingwua, He Tingtingc, Zhang Maoyuanc. Realizarea partajării secrete cu structură generală de acces // Științe informaționale. - 2016. - Nr. 367–368 . - S. 209-220 .
↑ Gertner, Y., Ishai, Y., Kushilevitz, E., Malkin, T. Protecting data privacy in private information retrieval schemes // Journal of Computer and System Sciences. - 2000. - Nr. 60(3) . — S. 592–629 .
↑ Ben-Or, M., Goldwasser, S., Wigderson, A. Teoreme de completitudine pentru calcul distribuit noncriptografic tolerant la erori. În: Proceedings of the 20th annual ACM symposium on Theory of computing // ACM Press. - 1998. - S. 1-10 .
↑ Cramer, R., Damg˚ard, I., Maurer, U. Calcul general securizat cu mai multe părți din orice schemă liniară de partajare a secretelor. // Preneel, B. (ed.) EUROCRYPT 2000. - T. 1807 . — S. 316–334 .
↑ Cramer, R., Damg˚ard, I., Nielsen, J.B. Secure Multiparty Computation and Secret Sharing: O Information Theoretic Approach. . (link indisponibil)
↑ Lee, C.-Y., Wang, Z.-H., Harn, L., Chang, C.-C. Protocol securizat de transfer de chei bazat pe partajarea secretelor pentru comunicații de grup // IEICE Trans. inf. și Syst.. - 2011. - S. 2069–2076 .
↑ Zhang, J., Li, X., Fu, F.-W. Schema de autentificare multi-receptor pentru mai multe mesaje bazate pe coduri liniare // Huang, X., Zhou, J. (eds.) ISPEC 2014. LNCS. - 2014. - T. 8434 . — S. 287–301 .