Hemliga delningsscheman för godtyckliga åtkomststrukturer

Hemliga delningsscheman för godtyckliga åtkomststrukturer (eng. Hemlig delning med generaliserad åtkomststruktur ) - hemliga delningsscheman som låter dig specificera en godtycklig uppsättning av grupper av deltagare (kvalificerade delmängder) som har förmågan att återställa hemligheten (åtkomststruktur).

Historik

1979 föreslog den israeliska kryptoanalytikern Adi Shamir ett hemligt delningssystem för tröskelvärden mellan parter som har följande egenskaper: $n$

För att återställa hemligheten räcker det med mer än en sida. $k$
Inga och färre parter kommer att kunna få någon information om hemligheten. [ett] $k-1$

Detta tillvägagångssätt har funnit många tillämpningar. Till exempel, för auktorisering av flera användare i en offentlig nyckelinfrastruktur , i digital steganografi för hemlig överföring av information i digitala bilder, för att motverka sidokanalattacker vid implementering av AES - algoritmen .

Mer komplexa applikationer, där vissa grupper av deltagare kan ha tillgång och andra inte, passar dock inte in i tröskelschemamodellen. För att lösa detta problem har hemliga delningsscheman utvecklats för godtyckliga åtkomststrukturer.

De japanska forskarna Mitsuro Ito, Akiro Saito och Takao Nishizeki var de första som studerade hemlig delning för godtyckliga åtkomststrukturer och föreslog 1987 deras system. [2] Deras tanke utvecklades av Josh Benalo och Jerry Leichter, som 1988 föreslog ett separationsschema för monotona strukturer. [3] 1989 föreslog Ernest Brickell ett system där deltagarna inte får del av hemligheten utan deras linjära kombinationer. [fyra]

Definition av termer som används

En återförsäljare är en deltagare i ett förfarande (protokoll) som, med kännedom om hemligheten, beräknar andelarna av hemligheten och delar ut dessa andelar till resten av deltagarna.

En kvalificerad delmängd är den uppsättning gruppmedlemmar för vilka hemlig återställning är tillåten.

Ett exempel som illustrerar uppkomsten av kvalificerade delmängder är delning av en hemlighet mellan chefer. I händelse av att hemligheten kan återfinnas antingen av alla tre cheferna, eller av vilken som helst verkställande direktör och valfri vicepresident, eller av presidenten ensam, [1] kommer de kvalificerade undergrupperna att vara presidenten, vicepresidenten och verkställande direktören, eller vilka som helst tre chefer.

Åtkomststrukturen är en uppräkning av kvalificerade och okvalificerade delmängder.

Låt vara en uppsättning gruppmedlemmar, vara antalet gruppmedlemmar och vara en uppsättning som består av alla möjliga undergrupper av gruppmedlemmar. Låt vara en uppsättning som består av delmängder av deltagare som får återställa hemligheten (kvalificerade uppsättningar av deltagare), en uppsättning som består av delmängder av deltagare som inte kan återställa hemligheten. En åtkomststruktur betecknas som ( , ) . $A$ $n$ $2^{[n]}$ $\Gamma$ $\Delta$ $\Gamma$ $\Delta$

En åtkomststruktur sägs vara monoton om alla supermängder av kvalificerade delmängder också ingår i , d.v.s. $\Gamma$ $A\in \Gamma ,A\subseteq B\subseteq P\Rightarrow B\in \Gamma$

Antag att ( , ) är $\Gamma$ $\Delta$ en åtkomststruktur på . kallas den minsta kvalificerade delmängden av , om alltid, när . Uppsättningen av minimala kvalificerade delmängder betecknas som och kallas en bas . Den minsta kvalificerade delmängden definierar åtkomststrukturen unikt. $A$ $B\in \Gamma$ $C\not \in \Gamma$ $C\subset B$ $\Gamma$ $\Gamma _{min}$ $\Gamma$

Schema för Benalo-Leichter

Låt en monoton åtkomststruktur ges och vara den uppsättning av minimala kvalificerade delmängder som motsvarar . Låt . För varje , beräknas hemliga andelar för medlemmar i denna delmängd med användning av ett hemligt delningsschema med valfri tröskel. $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}|)$

Andelen av hemligheten överförs till lämplig deltagare. Som ett resultat får varje deltagare en uppsättning hemliga aktier. Hemligheten återställs enligt det valda (n, n ) -tröskelschemat . [3] ${\displaystyle s_{i,j))$

Exempel:

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

Här är till exempel den andra i , så den får andelarna av hemligheten $P_{4}$ ${\displaystyle A_{2},A_{3},A_{4))$ ${\displaystyle s_{2,2},s_{3,2},s_{4,2))$

Likadant för andra deltagare

$P_{1}\leftarrow s_{1,1},s_{2,1}\ \ P_{2}\leftarrow s_{1,2},s_{3,1}\ \ P_{3}\ vänsterpil s_{1,3},s_{4,1}\ \$

Nackdelen med detta system är den ökande volymen hemliga aktier för varje deltagare med en ökning [5] [6] . $\Gamma _{min}$

Schema för Ito-Saito-Nishizeki

Ito, Saito, Nishizeki introducerade den så kallade kumulativa array-tekniken för en monoton åtkomststruktur. [2]

Låt vara en monoton åtkomststruktur av storlek och låt vara den maximala okvalificerade delmängden av deltagare som motsvarar den. $A$ $n$ ${\displaystyle A_{1},...,A_{m))$

Den kumulativa matrisen för åtkomststrukturen är en matris av dimensioner , där och betecknas som . Det vill säga att matrisens kolumner motsvarar okvalificerade delmängder, och värdet på raderna inuti kolumnen kommer att vara ett om elementet inte ingår i denna delmängd. $A$ $n\ gånger 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 \inte \i A_{j}\end{cases}}$ $C^{A}$

I det här schemat kan du använda valfritt - tröskelhemligt delningsschema med en hemlighet och motsvarande andelar $(m,m)$ $S$ ${\displaystyle s_{1},...,s_{m))$

De aktier som motsvarar hemligheten kommer att definieras som en uppsättning : $I_{1},...,I_{n}$ $S$ $s_{j}$ ${\displaystyle I_{i}=\{s_{j}|C_{i,j}^{A}=1\))$

Hemligheten återställs enligt det valda tröskelschemat . $(m,m)$

Komplexiteten i genomförandet av detta system, som uppnåddes 2016, är . [7] $På)$

Exempel:

Låt , . $n=4$ $\Gamma =\{\{1,2\},\{3,4\},\{1,2,3\},\{1,2,4\},\{1,3, 4\},\{2,3,4\}\}$

Motsvarande uppsättning av minimala kvalificerade delmängder $A$ ${\displaystyle \Gamma _{min}=\{\{1,2\},\{3,4\}\))$

I det här fallet och . ${\displaystyle \Delta _{max}=\{\{1,3\},\{1,4\},\{2,3\},\{2,4\}\))$ $m=4$

Den kumulativa arrayen av åtkomststrukturen har formen $A$ $C^{A}={\begin{pmatrix}0&0&1&1\\1&1&0&0\\0&1&0&1\\1&0&1&0\end{pmatrix}}$

Delar av deltagarnas hemlighet är lika $I_{1}=\{s_{3},s_{4}\};\ \ I_{2}=\{s_{1},s_{2}\};\ \ I_{3}= \{s_{2},s_{4}\};\ \ I_{4}=\{s_{1},s_{3}\}$

Hemlig återhämtning liknar hemlig återhämtning i Shamirs tröskelschema. $(4,4)$

Brickells linjära diagram över hemlig delning

För åtkomststrukturen och medlemsuppsättningen konstrueras en storleksmatris där längdsträngen är associerad med medlemmen . För delmängden av deltagare , som motsvarar uppsättningen av rader i matrisen- , måste villkoret vara uppfyllt att vektorn tillhör det linjära spann som spänns av . $A$ $P=\{P_{1},...,P_{n}\}$ $M$ $n\ gånger m$ $M[i]$ $m$ $i$ $x\subset \Gamma$ $M$ $M_{x}$ $(1,0,...,0)$ $M_{x}$

Dealern väljer en vektor där den delade hemligheten är . Deltagarens hemliga andel : $r=(r_{0},...,r_{m})$ $s=r_{0}$ $i$ $s_{i}=M[i]r$

Hemligt tillfrisknande.

En vektor väljs med längd , — en vektor som består av koordinater som motsvarar uppsättningen av deltagare . $\alfa$ $m$ $\alpha _{x}$ $\alfa$ $x\subset \Gamma$

För varje villkor måste uppfyllas: . Sedan kan hemligheten återställas med formeln: $x\subset \Gamma$ $\alpha _{x}M_{x}=(1,0,....,0)$

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

Exempel:

Uppsättningen av minimala kvalificerade delmängder av . $\Gamma =\{\{1,2,3\},\{1,4\}\}$

Lämplig matris:

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

$M$ uppfyller schemakravet:

För : $\{1, 2, 3\}$ $(1,0,0)=-(0,1,0)+(1,0,1)+(0,1,-1)$

För : $\{1,4\}$ $(1,0,0)=-(0,1,0)+(1,1,0)$

Delar av varje deltagares hemlighet:

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

Hemlig återhämtning:

För att återställa hemligheten, välj $\alpha =(-1,1,1,1)$

Sedan för : $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)$

Och för : $x=\{1,4\}$ $\alpha _{x}=(-1,1)$

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

Applikation

Dessa scheman används i protokoll för villkorad avslöjande av hemligheter (CDS) [8] , säker distribuerad datoranvändning [9] [10] [11] , nyckeldistributionsproblem [12] och autentiseringssystem för flera mottagare [13] .

Anteckningar

↑ 1 2 Shamir A. Hur man delar en hemlighet // Commun. ACM - NYC, USA. - 1979. - T. 22 . - S. 612-613 .
↑ 1 2 Ito M., Saito A., Nishizeki T. Hemligt delningsschema som realiserar allmän åtkomststruktur // Elektronik och kommunikation i Japan (Del III: Fundamental Electronic Science). - 1987. Arkiverad den 23 april 2021.
↑ 1 2 Benaloh J., Leichter J. Generaliserad hemlighetsdelning och monotona funktioner // Advances in Cryptology - CRYPTO' 88. - 1988. - S. 27-35 .
↑ 1 2 Brickell EF Några idealiska hemlighetsdelningssystem // Journal of Combin. Matematik. och kombinera. Comput. Nej. 9. - 1989. - S. 105-113 .
↑ Sreekumar A., Babusundar S. Hemliga delningsscheman med hjälp av visuell kryptografi // Cochin University of Science and Technology. — 2009.
↑ Kouya TOCHIKUBO. En konstruktionsmetod för hemliga delningsscheman baserade på auktoriserade delmängder // Internationellt symposium om informationsteori och dess tillämpningar. — 2008.
↑ Lein Harna, Hsu Chingfang, Zhang Mingwua, He Tingtingc, Zhang Maoyuanc. Förverkliga hemlig delning med allmän åtkomststruktur // Informationsvetenskap. - 2016. - Nr 367–368 . - S. 209-220 .
↑ Gertner, Y., Ishai, Y., Kushilevitz, E., Malkin, T. Protecting data privacy in private information retriever system // Journal of Computer and System Sciences. - 2000. - Nr 60(3) . — S. 592–629 .
↑ Ben-Or, M., Goldwasser, S., Wigderson, A. Fullständighetsteorem för icke-kryptografisk feltolerant distribuerad beräkning. I: Proceedings of the 20th annual ACM symposium on Theory of computing // ACM Press. - 1998. - S. 1-10 .
↑ Cramer, R., Damg˚ard, I., Maurer, U. Allmän säker flerpartsberäkning från vilket linjärt hemlighetsdelningsschema som helst. // Preneel, B. (red.) 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. . (inte tillgänglig länk)
↑ Lee, C.-Y., Wang, Z.-H., Harn, L., Chang, C.-C. Säkert nyckelöverföringsprotokoll baserat på hemlig delning för gruppkommunikation // IEICE Trans. inf. och Syst.. - 2011. - S. 2069–2076 .
↑ Zhang, J., Li, X., Fu, F.-W. Multi-mottagare autentiseringsschema för flera meddelanden baserat på linjära koder // Huang, X., Zhou, J. (red.) ISPEC 2014. LNCS. - 2014. - T. 8434 . — S. 287–301 .