Semnătura BLS (Boneh-Lynn-Shacham) este o semnătură electronică bazată pe curbe care sunt ușor de împerecheat și acceptă proprietăți de agregare non-interactive. Adică, pentru un grup de semnături (σ 1 , …, σ n ), se poate compune o semnătură scurtă σ care autentifică întreaga colecție de semnături. Schema de semnătură este simplă, eficientă și poate fi utilizată într-o varietate de protocoale și sisteme de rețea pentru a comprima semnăturile sau lanțurile de certificate. Deoarece problema computațională Diffie-Hellman este de nerezolvat, securitatea circuitului a fost dovedită.
Deoarece semnătura BLS funcționează cu curbe eliptice, este necesar să se modifice funcțiile hash standard astfel încât rezultatul să nu fie un număr, ci coordonatele punctului [1] . Să luăm ca bază funcția de hashing standard, dar rezultatul muncii sale va fi considerat nu un număr finit, ci coordonata x a unui punct. Fiecare x găsit poate avea zero sau două valori y, deci nu fiecare x are un y valid. Prin urmare, vom hash (msg || i) până când obținem rezultatul corect, unde || este funcția de concatenare și i este un număr nenegativ. Rămâne doar să se determine legea pentru alegerea unuia dintre punctele obținute (de exemplu, va exista un punct cu cea mai mare valoare a lui y).
Pentru a crea o semnătură, aveți nevoie de o funcție care va potrivi două puncte ale curbei cu un anumit număr. Să introducem o definiție abstractă a perechii. Fie G, G T grupuri ciclice de ordin prim r generate de un element g. O împerechere este o funcție efectiv calculabilă e : G 1 × G 2 → G T , pentru care sunt valabile următoarele proprietăți:
Cele mai comune în criptografie sunt funcțiile de împerechere ale lui Tate, Weil și împerecherea optimă a lui Ait [2] . Acesta din urmă este considerat cel mai eficient și este cel mai des folosit în practică.
Dacă o funcție de împerechere este definită pentru un grup ciclic, atunci problema de calcul Diffie-Hellman și problema logaritmului discret sunt de nerezolvat pentru acest grup , dar există o soluție eficientă pentru problema de decizie Diffie-Hellman. Astfel de grupuri sunt numite grupuri Diffie-Hellman [3] și implică o schemă de semnătură numită semnătură Bonet-Lynn-Shaham.
Fie G un grup Diffie-Hellman de ordin prim r, unde g ∈ G este un element generator al grupului, m este un mesaj dat.
Cheia privată SK este un număr întreg aleatoriu ales din intervalul [0, r-1]. Cheia publică se numește PK = g SK
Să presupunem că avem un grup de semnături care conține n perechi (S i , PK i ), unde i = [0,n]. Semnătura agregată a sistemului este suma S i peste i. Pentru confirmarea semnăturii, este necesar să se verifice egalitatea e(g, S) = e(PK 1 , H 1 ) ⋅ e(PK 2 , H 2 ) ⋅ … ⋅ e(PK n , H n ).
Pentru verificare , nu este necesar să cunoașteți mesajele corespunzătoare semnăturilor individuale, dar este necesar să cunoașteți toate cheile publice și să efectuați operația de asociere de n + 1 ori.
Verificați (g, S) = e(g, S 1 + S 2 + …+ S n ) = e(g, S 1 )⋅ e(g, S 2 ) ⋅ … ⋅ e(g, S n ) = e (g, H 1 PK 1 ) ⋅ … ⋅ e(g, H n PK n ) = e(g PK 1 , H 1 ) ⋅ … ⋅ e(g PK n , H n ) = e(SK 1 , H 1 ) ) ⋅ e(SK 2 , H 2 )⋅…⋅e(SK n , H n )
Pentru a crea o semnătură multiplă , vom semna aceeași tranzacție cu chei diferite. Apoi, pentru a optimiza memoria, putem combina toate semnăturile și cheile într-o pereche care definește întregul sistem - semnătură, cheie.
Cel mai simplu mod de a combina este adăugarea. Prin urmare, vom numi semnătura S = S 1 + S 2 + ... + S n , iar cheia PK = PK 1 + PK 2 + ... + PK n . În acest caz, corectitudinea valorilor alese este ușor de demonstrat: e(g, S) = e(P, H)
e(g, S) = e(g, S 1 + S 2 + … + S n ) = e(g, H SK 1 + SK 2 + … + SK n ) = e(g SK 1 + SK 2 + … + SK n , H) = e(PK 1 + PK 2 + … + PK n , H) = e(PK, H)
Să adăugăm non-liniaritate la circuit pentru a preveni atacul cheilor false. În loc să adăugăm doar cheile și semnăturile, să înmulțim fiecare termen cu un număr determinist și apoi să găsim suma fiecărui grup:
S = a 1 ×S 1 + a 2 ×S 2 + … + a n ×S n
PK = a 1 × PK 1 + a 2 × PK 2 + … + a n × PK n
Aici, semnătura și coeficienții cheii sunt calculați utilizând o funcție de hashing și iau în considerare toate cheile publice PK n : a i = hash(PK i , {PK 1 ,PK 2 , …, PK n }), hash este un obișnuit funcție de hashing, al cărei rezultat este un număr.
Una dintre aceste funcții este concatenarea cheii publice a semnatarului și a întregului set de chei publice utilizate pentru semnare: a i = hash(P i || P 1 || P 2 || P 3 ). Pentru o schemă mai complicată este valabilă aceeași ecuație de verificare (logica demonstrației nu se schimbă, în ciuda coeficienților suplimentari a i ).
Adesea, n-out-n semnăturile multiple sunt favorizate k-out-n. Deoarece în acest caz, dacă una sau mai multe chei sunt pierdute, sistemul poate funcționa corect. Pentru semnarea BLS, agregarea cheilor funcționează și în acest scenariu.
Să dăm un exemplu de construcție a unei scheme de semnături multiple k-out-n folosind chei (k < n) stocate pe n dispozitive diferite.
Fiecare dintre dispozitive are un număr de semnatar i = 1,2, …, n, care determină numărul de serie din set, o cheie privată SK i și o cheie publică PK i = g SK i .
Calculați cheia publică agregată PK = a 1 × PK 1 + a 2 × PK 2 + … + a n × PK n , unde a i = hash(PK i , {PK 1 ,PK 2 , …, PK n }).
Vom primi o cheie de membru MK i de la fiecare dispozitiv, care va confirma faptul că numărul i este inclus în PK. Fiecare cheie de membru trebuie să fie stocată pe dispozitivul respectiv.
MK i = H(PK, i) a 1 ⋅SK 1 + H(PK, i) a 2 ⋅SK 2 + … + H(PK, i) a n ⋅SK n
Fiecare cheie de participare este o semnătură efectivă n-out-n a mesajului H(PK,i). Prin urmare, pentru fiecare MK i , e(g, MK i )=e(PK, H(PK,i))
Să presupunem că vrem să semnăm un mesaj numai cu cheile SK 1 , SK 2 , …, SK k . Generăm m semnături S 1 , S 2 , …, S k :
S1 = H(PK, m ) SK1 + MK1
S2 = H(PK, m ) SK2 + MK2
…
S k = H(PK, m) SK k + MK k
Le adunăm pentru a obține o pereche semnătură-cheie care va descrie întregul sistem:
(S', PK') = (S 1 + S 2 + … + S k , PK 1 + PK 2 + …+ PK k )
Cheia PK' și semnătura S' sunt diferite de perechea PK, S. Primele depind doar de un subset de semnatari, în timp ce cele din urmă sunt determinate de toate perechile sistemului inițial.
Pentru a verifica semnătura k-out-n primită, verificați condiția:
e(g, S') = e(PK', H(PK, m))⋅e(PK, H(PK, 1)+H(PK, 2)+ … + H(PK, k))
Deoarece cheile de membru MK 1 , MK 2 , ... MK k sunt semnături valide pentru mesajele H(PK, 1), H(PK, 2) ... H(PK, k) semnate cu cheia agregată PK, prin urmare:
e(g, S') = e(g, S 1 + S 2 + … + S n ) = e(g, H(PK, m) SK 1 + H(PK, m) SK 2 + … + H( PK, m) SK k + MK 1 + MK 2 + … + MK k ) = e(g, H(PK, m) SK 1 + H(PK, m) SK 2 + … H(PK, m) SK k ) ⋅ e(g, MK 1 + MK 2 + … + MK k ) = e(g SK 1 + g SK 2 + … + g SK k , H(PK, m)) ⋅ e(PK, H(PK, 1) + H(PK, 2) + … + H(PK, k)) = e(PK', H(PK, m)) ⋅ e(PK, H(PK, 1) + H(PK, 2) + … + H(PK, k))
O schemă similară este aplicabilă pentru orice valoare a lui k și n. Și în loc de 1, 2, ... k, pot fi aleși orice k semnători nerepetați cu numere aparținând intervalului [1, n].
Principalul dezavantaj al acestui tip de semnătură este procesul de împerechere.
În primul rând, este nevoie de ceva timp pentru a calcula împerecherile, așa că uneori poate dura mai mult timp pentru a verifica semnătura unui bloc decât pentru a verifica toate semnăturile de mesaj din bloc. Cu toate acestea, cu un număr mare de tranzacții în bloc, avantajul va fi pe partea BLS a semnăturii.
În al doilea rând, nu toate curbele pot asigura atât securitatea cheii secrete, cât și eficacitatea funcției de împerechere [4] . Mai mult, există MOV - un atac (un atac asupra criptosistemelor cu curbe eliptice), care vizează reducerea securității sistemului prin afectarea funcției de împerechere.