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).
1979 föreslog den israeliska kryptoanalytikern Adi Shamir ett hemligt delningssystem för tröskelvärden mellan parter som har följande egenskaper:
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]
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 ( , ) .
En åtkomststruktur sägs vara monoton om alla supermängder av kvalificerade delmängder också ingår i , d.v.s.
Antag att ( , ) är 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.
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.
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]
Exempel:
Här är till exempel den andra i , så den får andelarna av hemligheten
Likadant för andra deltagare
Nackdelen med detta system är den ökande volymen hemliga aktier för varje deltagare med en ökning [5] [6] .
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.
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.
I det här schemat kan du använda valfritt - tröskelhemligt delningsschema med en hemlighet och motsvarande andelar
De aktier som motsvarar hemligheten kommer att definieras som en uppsättning :
Hemligheten återställs enligt det valda tröskelschemat .
Komplexiteten i genomförandet av detta system, som uppnåddes 2016, är . [7]
Exempel:
Låt , .
Motsvarande uppsättning av minimala kvalificerade delmängder
I det här fallet och .
Den kumulativa arrayen av åtkomststrukturen har formen
Delar av deltagarnas hemlighet är lika
Hemlig återhämtning liknar hemlig återhämtning i Shamirs tröskelschema.
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 .
Dealern väljer en vektor där den delade hemligheten är . Deltagarens hemliga andel :
Hemligt tillfrisknande.
En vektor väljs med längd , — en vektor som består av koordinater som motsvarar uppsättningen av deltagare .
För varje villkor måste uppfyllas: . Sedan kan hemligheten återställas med formeln:
[fyra]
Exempel:
Uppsättningen av minimala kvalificerade delmängder av .
Lämplig matris:
uppfyller schemakravet:
För :
För :
Delar av varje deltagares hemlighet:
Hemlig återhämtning:
För att återställa hemligheten, välj
Sedan för :
Och för :
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] .