Verificerbar hemmelig deling

Verifiable secret sharing ( VSS ) er et hemmeligt delingsskema , der giver gruppemedlemmer mulighed for at verificere, at deres delinger er konsistente ( engelsk konsistent ) [1] , det vil sige, at de genskaber den samme hemmelighed . Med andre ord garanterer denne ordning, at der eksisterer en hemmelighed, som deltagerne senere kan genvinde, selvom fordelingen bevidst blev ændret. (Den sædvanlige ordning forudsætter, at allokeringen er udført korrekt.) Konceptet med verificerbar hemmelig deling blev først introduceret af Benny Chor, Shafi Goldwasser , Silvio Micali og Baruch Averbuch i 1985 [2] .

Et gruppemedlem, der deler en hemmelighed, kaldes en forhandler i VSS -protokollen [ 3 ] . Protokollen er opdelt i to faser: adskillelse og genopretning.

Split: I første omgang har hver deltager uafhængige tilfældige input. Dealeren bruger en hemmelighed som input. Adskillelse består af flere faser. På hvert trin kan ethvert medlem privat sende beskeder til andre eller offentligt sende en besked til alle. Hver sådan besked bestemmes af inputdata og tidligere modtagne beskeder.

Genopretning: På dette stadium giver hver deltager de oplysninger, der er opnået under separationsfasen. Gendannelsesfunktionen anvendes derefter, og dens resultat bruges som output af protokollen.

I sikker multiparty computing er input opdelt i hemmelige fraktioner, som bruges til at beregne en eller anden funktion. Der er ondsindede aktører, der korrumperer dataene og afviger fra protokollen. VSS [4] bruges til at forhindre deres indflydelse .

Feldmans skema

Paul Feldman-protokollen er baseret på Shamirs hemmelige delingsskema kombineret med et hvilket som helst homomorfisk krypteringsskema . Overvej tærskelkredsløbet ( t , n ). Beregningerne udføres med elementer af den cykliske gruppe G af orden p med generator g . Gruppen G er valgt således, at opnåelse af værdien af den diskrete logaritme i denne gruppe har en høj beregningsmæssig kompleksitet. Derefter sætter (og hemmeligholder) dealeren et polynomium P af grad t − 1 med koefficienter fra Z p , inkl. P (0)= s , hvor s er hemmeligheden. Hver af de n deltagere vil modtage værdien P (1), …, P ( n ) modulo p [5] .

Alt ovenstående er en implementering af Shamirs hemmelige deling. For at gøre denne ordning verificerbar sender forhandleren testværdier til koefficienterne P . Hvis P ( x ) = s + a 1 x + ... + a t − 1 x t − 1 , så er værdierne:

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

Derudover sender forhandleren ændringen z i = g y i , hvor y i = P ( i ) , til den i -te deltager. Når dette er gjort, kan ethvert medlem kontrollere konsistensen af deres andel ved at verificere følgende lighed:

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 at have sikret sig, rapporterer deltageren om det. Som et resultat ved alle, at alle dele svarer til et polynomium og derfor er fælles [6] .

Ordning af Benalo

Benalo-ordningen er også en udvikling af Shamir-ordningen . Når n aktier er blevet fordelt blandt deltagerne, skal hver af dem være i stand til at verificere, at alle aktier er t - konsistente , det vil sige , at enhver undergruppe af t deltagere ud af n genfinder den samme hemmelighed [1] . I Shamirs skema er delene s 1 , s 2 , …, s n t - led, hvis og kun hvis graden af interpolationspolynomiet konstrueret ud fra punkterne (1, s 1 ), (2, s 2 ), …, (n, s n ) ikke overstiger d = t − 1 [7] . Desuden, hvis graden af summen af to polynomier F og G er mindre end eller lig med t , så er enten begge grader af polynomierne F og G mindre end eller lig med t , eller begge er større end t . Dette følger af polynomfunktionens homomorfe egenskab.

Eksempler:

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

Egenskaben af Shamir-skemaet beskrevet ovenfor pålægger en begrænsning på graden af interpolationspolynomiet ved bekræftelse af t -konsistens . Baseret på dette og polynomiers homomorfe egenskab, giver Benalos skema deltagerne mulighed for at udføre den nødvendige kontrol, mens de bekræfter konsistensen af deres andele [8] [7] .

Konsistens kan kontrolleres ved hjælp af følgende algoritme:

Dealeren angiver et polynomium P af graden t − 1 og tildeler aktier (som i Shamirs skema )
Dealeren opretter et meget stort antal ( k ) af tilfældige polynomier af graden t − 1 og fordeler også deres andele. ${\displaystyle P_{1},...,P_{k))$
Ejeren af andelen vælger et tilfældigt sæt af m polynomier ( m < k ).
Dealeren afslører andele af m udvalgte polynomier , opsummerer de resterende k − m polynomier og deler resultatet. $P_{i_{1}},...,P_{i_{m}}$ $P+\textstyle \sum _{j={m+1}}^{k}P_{j}$
Hver deltager kontrollerer, at alle udvidede polynomier af grad t − 1 svarer til den brøk, han kender.

Hvis forhandleren ærligt følger denne algoritme, svarer graderne af polynomierne og graderne af interpolationspolynomier, der er gendannet fra deres dele, til graden t − 1 af det hemmelige polynomium P af den homomorfe egenskab. Ved at kende aktierne og , kan enhver deltager således blive overbevist om t -kompatibilitet af Shamir-ordningens ejendom. Derudover fører fordelingen af tilfældige polynomier ikke til afsløringen af hemmeligheden [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}$

Hemmelige valg

VSS gælder for hemmelige valg [10] . Hver vælger kan stemme for (1) eller imod (0), og summen af alle stemmer bestemmer resultatet af afstemningen. Du skal sikre dig, at følgende betingelser er opfyldt:

Vælgernes privatliv må ikke kompromitteres.
Observatøren skal verificere, at ingen vælgere har begået bedrageri.

Ved brug af VSS vil én observatør erstatte n stemmetællere. Hver vælger vil fordele andele af sin hemmelighed blandt alle n tællere. I dette tilfælde bevares vælgernes privatliv, og den første betingelse er opfyldt. For at genoprette valgresultatet er det nødvendigt at have nok k<n tællere til at genoprette polynomiet P . For at validere stemmer kan hver vælger anvende fordelingskonsistenskontrollen beskrevet i det foregående afsnit [11] .

VSS effektivitet

Kompleksiteten af VSS-protokollen er defineret som antallet af meddelelsesudvekslingstrin i splitfasen, nemlig antallet af hemmelige aktier sendt af forhandleren, checkværdier (i Feldman-skemaet), tilfældige polynomier og så videre. Genopretning kan altid udføres i ét trin. Dette kan opnås ved hjælp af simultan udsendelse ( engelsk simultaneous broadcast ) [12] . Derfor er der ingen 1-trins VSS med t>1 , uanset antal deltagere. Også en VSS-protokol siges at være effektiv, hvis den har polynomisk kompleksitet afhængig af n . Betingelser for en effektiv VSS-protokol [13] [14] :

Antal etaper	Muligheder
en	t = 1, n > 4
2	n > 4t
3	n > 3t

Noter

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

Litteratur

B. Chor, S. Goldwasser, S. Micali, B. Awerbuch. Verificerbar hemmelig deling og opnåelse af samtidighed ved tilstedeværelse af fejl // IEEE. - 1985. - S. 383-395 .
P. Feldman. En praktisk ordning for ikke-interaktiv verificerbar hemmelig deling // IEEE. - 1987. - S. 427-437 .
T. Rabin og M. Ben-Or. Verificerbar hemmelig deling og flerpartsprotokoller med ærligt flertal // STOC '89 Proceedings of the enogtyvende årlige ACM symposium on Theory of computing. - 1989. - S. 79 .
Chunming Tang, Dingyi Pei, Zhuojun Liu, Yong He. Ikke-interaktiv og informationsteoretisk sikker offentligt verificerbar hemmelig deling // IACR Cryptology ePrint Archive. – 2004.
Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, Tal Rabin. Den runde kompleksitet af verificerbar hemmelig deling og sikker multicast // STOC '01 Proceedings af det treogtredive årlige ACM symposium om teori om computing. - 2001. - S. 580-589 .
Matthias Fitzi, Juan Garay, Shyamnath Gollakota, C. Pandu Rangan og Kannan Srinathan. Rund-optimal og effektiv verificerbar hemmelighedsdeling . - Springer-Verlag Berlin Heidelberg, 2006. - S. 330-342.
Oded Goldreich. The Foundations of Cryptography - bind 2. - Cambridge University Press, 2004.
Josh Cohen Benaloh. Secret Sharing Homomorphisms: Keeping Shares of a Secret Secret // Proceedings on Advances in cryptology --- CRYPTO '86. - 1987.