Partajare secretă verificabilă

Partajarea secretă verificabilă ( VSS ) este o schemă de partajare secretă care permite membrilor grupului să verifice dacă partajările lor sunt consecvente ( coerente în engleză ) [1] , adică recreează același secret . Cu alte cuvinte, această schemă garantează existența unui secret pe care participanții îl pot recupera ulterior, chiar dacă distribuția a fost schimbată în mod deliberat. (Schema obișnuită presupune că alocarea se face corect.) Conceptul de partajare a secretelor verificabile a fost introdus pentru prima dată de Benny Chor, Shafi Goldwasser , Silvio Micali și Baruch Averbuch în 1985 [2] .

Un membru al grupului care împărtășește un secret este numit dealer în protocolul VSS [ 3 ] . Protocolul este împărțit în două etape: separare și recuperare.

Split: Inițial, fiecare participant are intrări aleatorii independente. Dealerul folosește un secret ca intrare. Separarea constă în mai multe etape. În fiecare etapă, orice membru poate trimite mesaje în mod privat altora sau poate trimite public un mesaj tuturor. Fiecare astfel de mesaj este determinat de datele de intrare și de mesajele primite anterior.

Recuperare: În această etapă, fiecare participant furnizează informațiile obținute în etapa de separare. Funcția de recuperare este apoi aplicată și rezultatul acesteia este folosit ca rezultat al protocolului.

În calculul multipartit securizat, intrarea este împărțită în fracții secrete, care sunt folosite pentru a calcula anumite funcții. Există actori rău intenționați care corup datele și se abat de la protocol. VSS [4] este utilizat pentru a preveni influența lor .

Schema lui Feldman

Protocolul Paul Feldman se bazează pe schema de partajare secretă a lui Shamir, combinată cu orice schemă de criptare homomorfă . Se consideră circuitul de prag ( t , n ). Calculele se efectuează cu elemente ale grupului ciclic G de ordinul p cu generator g . Grupul G este ales astfel încât obținerea valorii logaritmului discret în acest grup să aibă o complexitate de calcul ridicată. Apoi dealerul stabilește (și păstrează secret) un polinom P de gradul t − 1 cu coeficienți din Z p , incl. P (0)= s , unde s este secretul. Fiecare dintre cei n participanți va primi valoarea P (1), …, P ( n ) modulo p [5] .

Toate cele de mai sus sunt o implementare a partajării secrete a lui Shamir. Pentru a face această schemă verificabilă, distribuitorul trimite valorile de testare la coeficienții P . Dacă P ( x ) = s + a 1 x + ... + a t − 1 x t − 1 , atunci valorile sunt:

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

În plus, dealer-ul trimite amendamentul z i = g y i , unde y i = P ( i ) , celui - lea participant. Odată făcut acest lucru, orice membru poate verifica consistența cotei sale verificând următoarea egalitate:

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

După ce se asigură, participantul raportează despre asta. Drept urmare, toată lumea știe că toate părțile corespund unui singur polinom și, prin urmare, sunt îmbinate [6] .

Schema lui Benalo

Schema Benalo este, de asemenea, o dezvoltare a schemei Shamir . Odată ce n acțiuni au fost distribuite între participanți, fiecare dintre aceștia trebuie să poată verifica dacă toate acțiunile sunt t - consistente , adică orice subgrup de t participanți din n recuperează același secret [1] . În schema lui Shamir, părțile s 1 , s 2 , …, s n sunt articulații în t dacă și numai dacă gradul polinomului de interpolare construit din punctele (1, s 1 ), (2, s 2 ), …, (n, s n ) nu depășește d = t − 1 [7] . În plus, dacă gradul sumei a două polinoame F și G este mai mic sau egal cu t , atunci fie ambele grade ale polinoamelor F și G sunt mai mici sau egale cu t , fie ambele sunt mai mari decât t . Aceasta rezultă din proprietatea omomorfă a funcției polinomiale.

Exemple:

cazul 1:
$f_{1}=3x$ . . $f_{2}=11x^{6)$ $t=6$
cazul 2:
$f_{1}=18x^{7)$ . . $f_{2}=-18x^{7)$ $t=6$

Proprietatea schemei Shamir descrisă mai sus impune o restricție asupra gradului polinomului de interpolare atunci când se confirmă t -consistența . Pe baza acestei proprietăți omomorfe a polinoamelor, schema lui Benalo permite participanților să efectueze verificarea necesară în timp ce confirmă consistența cotelor lor [8] [7] .

Consecvența poate fi verificată folosind următorul algoritm:

Dealerul specifică un polinom P de gradul t - 1 și alocă acțiuni (ca în schema lui Shamir )
Dealerul creează un număr foarte mare ( k ) de polinoame aleatoare de grad t − 1 și distribuie și acțiunile acestora. $P_{1},...,P_{k)$
Proprietarul acțiunii alege o mulțime aleatorie de m polinoame ( m < k ).
Dealerul dezvăluie cotele m polinoame selectate , însumează restul k − m polinoame și împărtășește rezultatul. $P_{i_{1}},...,P_{i_{m}}$ $P+\textstyle \sum _{j={m+1}}^{k}P_{j}$
Fiecare participant verifică dacă toate polinoamele expandate de gradul t − 1 corespund fracției cunoscute de el.

Dacă dealer-ul urmează cu sinceritate acest algoritm, atunci gradele polinoamelor , și gradele polinoamelor de interpolare recuperate din părțile lor corespund gradului t − 1 al polinoamului secret P prin proprietatea omomorfă. Astfel, cunoscând acțiunile și , orice participant poate fi convins de compatibilitatea t prin proprietatea schemei Shamir. În plus, distribuția polinoamelor aleatoare nu duce la dezvăluirea secretului [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}$

Alegeri secrete

VSS este aplicabil pentru alegeri secrete [10] . Fiecare alegător poate vota pentru (1) sau împotrivă (0), iar suma tuturor voturilor determină rezultatul votului. Trebuie să vă asigurați că sunt îndeplinite următoarele condiții:

Intimitatea alegătorilor nu trebuie compromisă.
Observatorul trebuie să verifice că niciun alegător nu a comis fraudă.

Când se utilizează VSS, un observator va înlocui n contoare de voturi. Fiecare alegător va distribui părți din secretul său între toate cele n ghișee. În acest caz, confidențialitatea alegătorului este păstrată și prima condiție este îndeplinită. Pentru a restabili rezultatul alegerilor, este necesar să existe suficiente k<n contoare pentru a restabili polinomul P . Pentru validarea voturilor, fiecare alegător poate aplica verificarea coerenței distribuției descrisă în secțiunea anterioară [11] .

Eficiență VSS

Complexitatea protocolului VSS este definită ca numărul de etape de schimb de mesaje în etapa divizată, și anume, numărul de acțiuni secrete trimise de dealer, valorile de verificare (în schema Feldman), polinoame aleatoare și așa mai departe. Recuperarea poate fi întotdeauna efectuată într-un singur pas. Acest lucru se poate realiza cu ajutorul difuzării simultane (în engleză simultaneous broadcast ) [12] . Prin urmare, nu există VSS cu 1 etapă cu t>1 , indiferent de numărul de participanți. De asemenea, se spune că un protocol VSS este eficient dacă are complexitate polinomială în funcție de n . Condiții pentru un protocol VSS eficient [13] [14] :

Numărul de etape	Opțiuni
unu	t = 1, n > 4
2	n > 4t
3	n > 3t

Note

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

Literatură

B. Chor, S. Goldwasser, S. Micali, B. Awerbuch. Partajarea secretelor verificabile și realizarea simultaneului în prezența defecțiunilor // IEEE. - 1985. - S. 383-395 .
P. Feldman. O schemă practică pentru partajarea secretelor neinteractive verificabile // IEEE. - 1987. - S. 427-437 .
T. Rabin și M. Ben-Or. Partajare secretă verificabilă și protocoale multipartid cu o majoritate onesta // STOC '89 Proceedings of the 21 annual ACM symposium on Theory of computing. - 1989. - S. 79 .
Chunming Tang, Dingyi Pei, Zhuojun Liu, Yong He. Partajare secretă non-interactivă și teoretică a informațiilor, securizată și verificabilă public // Arhiva ePrint de criptologie IACR. — 2004.
Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, Tal Rabin. Complexitatea rundei a partajării secrete verificabile și a multicastului securizat // STOC '01 Proceedings of the 333 annual ACM symposium on Theory of computing. - 2001. - S. 580-589 .
Matthias Fitzi, Juan Garay, Shyamnath Gollakota, C. Pandu Rangan și Kannan Srinathan. Distribuire de secrete verificabile, optimă și eficientă . - Springer-Verlag Berlin Heidelberg, 2006. - S. 330-342.
Oded Goldreich. The Foundations of Cryptography - Volumul 2. - Cambridge University Press, 2004.
Josh Cohen Benaloh. Omomorfisme de partajare a secretelor: păstrarea acțiunilor unui secret secret // Proceedings on Advances in cryptology---CRYPTO '86. — 1987.