Verifierbar hemlighetsdelning

Verifiable secret sharing ( VSS ) är ett hemligt delningsschema som låter gruppmedlemmar verifiera att deras delningar är konsekventa ( engelska konsekventa ) [1] , det vill säga de återskapar samma hemlighet . Detta system garanterar med andra ord att det finns en hemlighet som deltagarna senare kan återfå, även om fördelningen avsiktligt ändrades. (Det vanliga schemat förutsätter att tilldelningen görs korrekt.) Begreppet verifierbar hemlighetsdelning introducerades först av Benny Chor, Shafi Goldwasser , Silvio Micali och Baruch Averbuch 1985 [2] .

En gruppmedlem som delar en hemlighet kallas för återförsäljare i VSS- protokollet [ 3 ] . Protokollet är uppdelat i två steg: separation och återhämtning.

Split: Till en början har varje deltagare oberoende slumpmässiga ingångar. Dealern använder en hemlighet som input. Separationen består av flera steg. I varje steg kan alla medlemmar skicka meddelanden privat till andra eller offentligt skicka meddelanden till alla. Varje sådant meddelande bestäms av indata och tidigare mottagna meddelanden.

Återhämtning: I detta skede tillhandahåller varje deltagare den information som erhållits under separationssteget. Återställningsfunktionen tillämpas sedan och dess resultat används som utdata från protokollet.

I säker flerpartsberäkning delas indata in i hemliga bråk, som används för att beräkna någon funktion. Det finns illvilliga aktörer som korrumperar data och avviker från protokollet. VSS [4] används för att förhindra deras inflytande .

Feldmans schema

Paul Feldman-protokollet är baserat på Shamirs hemliga delningsschema kombinerat med vilket homomorfiskt krypteringsschema som helst . Betrakta tröskelkretsen ( t , n ). Beräkningarna utförs med element av den cykliska gruppen G av ordningen p med generatorn g . Gruppen G väljs så att erhållande av värdet av den diskreta logaritmen i denna grupp har en hög beräkningskomplexitet. Sedan sätter (och håller dealern hemligt) ett polynom P av graden t − 1 med koefficienter från Z p , inkl. P (0)= s , där s är hemligheten. Var och en av de n deltagarna kommer att få värdet P (1), …, P ( n ) modulo p [5] .

Allt ovanstående är en implementering av Shamirs hemliga delning. För att göra detta schema verifierbart skickar återförsäljaren testvärden till koefficienterna P . Om P ( x ) = s + a 1 x + ... + a t − 1 x t − 1 , då är värdena:

c 0 = g s ,
c 1 \ u003d g a 1 ,
…
c t − 1 = g a t − 1 .

Dessutom skickar dealern ändringen z i = g y i , där y i = P ( i ) , till den i :te deltagaren. När detta är gjort kan vilken medlem som helst kontrollera konsekvensen i sin andel genom att verifiera följande likhet:

g^{v}=c_{0}c_{1}^{i}c_{2}^{i^{2}}\cdots c_{t-1}^{i^{(t-1 )}}=\prod _{j=0}^{t-1}c_{j}^{i^{j}}=\prod _{j=0}^{t-1}g^{a_{ j}i^{j}}=g^{\sum _{j=0}^{t-1}a_{j}i^{j}}=g^{y_{i}}

Efter att ha försäkrat sig rapporterar deltagaren om det. Som ett resultat vet alla att alla delar motsvarar ett polynom och därför är gemensamma [6] .

Scheme of Benalo

Benalo-systemet är också en utveckling av Shamir-systemet . När n aktier har fördelats mellan deltagarna måste var och en av dem kunna verifiera att alla aktier är t - konsistenta , det vill säga att varje undergrupp av t deltagare av n återvinner samma hemlighet [1] . I Shamirs schema är delarna s 1 , s 2 , …, s n t - fogade om och endast om graden av interpolationspolynomet konstruerat från punkterna (1, s 1 ), (2, s 2 ), …, (n, s n ) inte överstiger d = t − 1 [7] . Dessutom, om graden av summan av två polynom F och G är mindre än eller lika med t , så är antingen båda graderna av polynomen F och G mindre än eller lika med t , eller båda är större än t . Detta följer av polynomfunktionens homomorfa egenskap.

Exempel:

fall 1:
$f_{1}=3x$ ... _ ${\displaystyle f_{2}=11x^{6))$ $t=6$
fall 2:
${\displaystyle f_{1}=18x^{7))$ ... _ ${\displaystyle f_{2}=-18x^{7))$ $t=6$

Egenskapen för Shamir-schemat som beskrivs ovan medför en begränsning av graden av interpolationspolynomet när t -konsistens bekräftas . Baserat på detta och polynomens homomorfa egenskaper tillåter Benalos schema deltagarna att utföra den nödvändiga kontrollen samtidigt som de bekräftar överensstämmelsen hos deras andelar [8] [7] .

Konsistens kan kontrolleras med hjälp av följande algoritm:

Dealern specificerar ett polynom P av graden t − 1 och allokerar aktier (som i Shamirs system )
Dealern skapar ett mycket stort antal ( k ) slumpmässiga polynom med graden t − 1 och fördelar också deras andelar. ${\displaystyle P_{1},...,P_{k))$
Ägaren av andelen väljer en slumpmässig uppsättning av m polynom ( m < k ).
Dealern avslöjar andelarna av m valda polynom , summerar de återstående k − m polynomen och delar resultatet. $P_{i_{1}},...,P_{i_{m}}$ $P+\textstyle \sum _{j={m+1}}^{k}P_{j}$
Varje deltagare kontrollerar att alla expanderade polynom med graden t − 1 motsvarar den bråkdel som han känner till.

Om dealern ärligt följer denna algoritm, så motsvarar graderna av polynomen och graderna av interpolationspolynomen som återvinns från deras delar graden t − 1 av det hemliga polynomet P av den homomorfa egenskapen. Genom att känna till aktierna och , kan alla deltagare övertygas om t -kompatibilitet genom Shamir-programmets egendom. Dessutom leder fördelningen av slumpmässiga polynom inte till att hemligheten avslöjas [9] . $P_{i_{1}},...,P_{i_{m}}$ $P+\textstyle \sum _{j={m+1}}^{k}P_{j}$ $P_{i_{1}},...,P_{i_{m}}$ $P+\textstyle \sum _{j={m+1}}^{k}P_{j}$

Hemliga val

VSS är tillämpligt för hemliga val [10] . Varje väljare kan rösta för (1) eller emot (0), och summan av alla röster avgör resultatet av omröstningen. Du måste se till att följande villkor är uppfyllda:

Väljarnas integritet får inte äventyras.
Observatören måste verifiera att ingen väljare har gjort sig skyldig till bedrägeri.

När du använder VSS kommer en observatör att ersätta n rösträknare. Varje väljare kommer att dela ut andelar av sin hemlighet mellan alla n räknare. I detta fall bevaras väljarnas integritet och det första villkoret är uppfyllt. För att återställa valresultatet är det nödvändigt att ha tillräckligt många k<n -räknare för att återställa polynomet P . För att validera röster kan varje väljare tillämpa den kontroll av fördelningen som beskrivs i föregående avsnitt [11] .

VSS effektivitet

Komplexiteten hos VSS-protokollet definieras som antalet meddelandeutbytessteg i det delade steget, nämligen antalet hemliga aktier som skickas av återförsäljaren, kontrollvärden (i Feldman-schemat), slumpmässiga polynom och så vidare. Återhämtning kan alltid utföras i ett steg. Detta kan uppnås med hjälp av samtidig sändning ( engelska simultaneous broadcast ) [12] . Därför finns det ingen 1-stegs VSS med t>1 , oavsett antal deltagare. Ett VSS-protokoll sägs också vara effektivt om det har polynomkomplexitet beroende på n . Villkor för ett effektivt VSS-protokoll [13] [14] :

Antal etapper	alternativ
ett	t = 1, n > 4
2	n > 4t
3	n > 3t

Anteckningar

↑ 1 2 Josh Cohen Benaloh, 1987 , sid. 256.
↑ B. Chor, S. Goldwasser, S. Micali, B. Awerbuch, 1985 .
↑ B. Chor, S. Goldwasser, S. Micali, B. Awerbuch, 1985 , sid. 387.
↑ Oded Goldreich, 2004 .
↑ P. Feldman, 1987 , sid. 429.
↑ P. Feldman, 1987 , sid. 433.
↑ 1 2 Josh Cohen Benaloh, 1987 , sid. 256-257.
↑ Josh Cohen Benaloh, 1987 , sid. 252-253.
↑ Josh Cohen Benaloh, 1987 , sid. 256-258.
↑ Chunming Tang, Dingyi Pei, Zhuojun Liu, Yong He, 2004 .
↑ Josh Cohen Benaloh, 1987 , sid. 258.
↑ B. Chor, S. Goldwasser, S. Micali, B. Awerbuch, 1985 , sid. 383-387.
↑ Matthias Fitzi, Juan Garay, Shyamnath Gollakota, C. Pandu Rangan och Kannan Srinathan, 2006 , sid. 331-332.
↑ Matthias Fitzi, Juan Garay, Shyamnath Gollakota, C. Pandu Rangan och Kannan Srinathan, 2006 , sid. 340.

Litteratur

B. Chor, S. Goldwasser, S. Micali, B. Awerbuch. Verifierbar hemlighetsdelning och uppnå samtidighet i närvaro av fel // IEEE. - 1985. - S. 383-395 .
P. Feldman. Ett praktiskt schema för icke-interaktiv verifierbar hemlighetsdelning // IEEE. - 1987. - S. 427-437 .
T. Rabin och M. Ben-Or. Verifierbar hemlighetsdelning och flerpartiprotokoll med ärlig majoritet // STOC '89 Proceedings of the twenty-fire annual ACM symposium on Theory of computing. - 1989. - S. 79 .
Chunming Tang, Dingyi Pei, Zhuojun Liu, Yong He. Icke-interaktiv och informationsteoretisk säker offentligt verifierbar hemlighetsdelning // IACR Cryptology ePrint Archive. – 2004.
Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, Tal Rabin. The Round Complexity of Verifiable Secret Sharing and Secure Multicast // STOC '01 Proceedings of the trettiotree årliga ACM symposiet on Theory of computing. - 2001. - S. 580-589 .
Matthias Fitzi, Juan Garay, Shyamnath Gollakota, C. Pandu Rangan och Kannan Srinathan. Rundoptimal och effektiv verifierbar hemlighetsdelning . - Springer-Verlag Berlin Heidelberg, 2006. - S. 330-342.
Oded Goldreich. The Foundations of Cryptography - Volym 2. - Cambridge University Press, 2004.
Josh Cohen Benaloh. Homomorfismer för hemlig delning: Att hålla andelar i en hemlig hemlighet // Proceedings on Advances in cryptology --- CRYPTO '86. — 1987.