Puncte:-1

Shamir Secret Sharing și recuperați funcția polinomială din acțiuni

drapel co

Am lucrat prima parte a schemei SSS, astfel încât să pot folosi un număr secret ca intrare și să pot genera o funcție polinomială aleatorie și să creez acțiuni simple ca perechi (xi, yi).

Sarcina este cum să obțineți secretul reconstruit din acțiuni? Știm cu toții că trebuie să facem niște ghicituri matematice inteligente pentru a găsi coeficii. Care sunt opțiunile sau algoritmii/abordările pentru a găsi coefurile? Care sunt avantajele și dezavantajele fiecăruia? Cum ar fi diferit în câmpuri finite?

kelalaka avatar
drapel in
Bun venit la Cryptgraphy.SE SSS trebuie să funcționeze în câmpuri finite. Vrei să ne descrii pentru a recupera secretul dat de share? Este bine scris în [Wikipedia](https://en.wikipedia.org/wiki/Shamir's_Secret_Sharing#Computationally_efficient_approach). Dacă ceva nu este clar, puteți întreba despre asta.
Macko avatar
drapel co
Vreau să știu în special în abordarea clasică cum să găsesc coeficii polinomului care a fost folosit în momentul generării primelor acțiuni. Știu că există unul, dar are câteva dezavantaje în implementare - mă refer la gaussian.
poncho avatar
drapel my
De ce vă pasă de coeficienți? Nu-i așa că singurul lucru pe care ești interesat să-l recuperezi este secretul?
Macko avatar
drapel co
Desigur, există mai multe: cum ar fi ușor de implementat, execuție rapidă și nu este vulnerabil la atacuri (timing). Următorul pas este modul de atenuare a problemelor în abordarea clasică Shamir - cum ar fi furnizorul de acțiuni malefice pentru reconstrucție (cum se codifică share pentru a fi invulnerabil la manipulare).
kelalaka avatar
drapel in
De ce ai nevoie de atacul de sincronizare? Construiți secretul pe un computer local off-line? Există lucrări academice despre SSS fără dealer [Shamir secret shamir with no dealer](https://crypto.stackexchange.com/q/84143/18298) și [Duckduckgo](https://duckduckgo.com/?q=shamir +partajare+secretă+fără+dealer&t=canonical&ia=web)
Macko avatar
drapel co
Așa că am uitat să menționez ideea principală: cunoașterea coefurilor este crucială pentru că vreau să generez mai multe acțiuni de la cele care ies.
kelalaka avatar
drapel in
Împărțiți din nou fiecare cotă cu SSS?
Macko avatar
drapel co
dacă împart fiecare cotă din nou cu SSS și folosesc o parte din acțiunile din primul pool generat și unele acțiuni divizate, înseamnă că îmi pot reconstrui secretul?
poncho avatar
drapel my
Dacă aveți acțiuni $t$ (unde $t$ este pragul), este simplu să generați mai multe acțiuni fără să vă obosiți să calculați coeficienții interni.
Macko avatar
drapel co
wow, te rog descrie-l cât mai simplu posibil, deoarece singurul mod pe care îl știu a fost prin rezolvarea ecuațiilor liniare
poncho avatar
drapel my
Ei bine, știți că logica standard de reconstrucție a secretelor ia o serie de cote $(x_1, y_1), (x_2, y_2), ..., (x_t, y_t)$ și returnează secretul partajat, care este polinomul evaluat la 0. Deci, pentru a construi cota la coordonata x $x'$, luăm cotele artificiale $(x_1 - x', y_1), (x_2 - x', y_2), ..., (x_t - x', y_t)$ și dați asta logicii de reconstrucție secretă - care vă oferă polinomul original evaluat la $x'$, adică coordonatele corespunzătoare $y'$ - noua cotă este $(x', y')$ . Clătiți și repetați pentru toate acțiunile suplimentare de care aveți nevoie
Macko avatar
drapel co
Deci, în general, această formulă de interpolare funcționează, dar interesant este că, dacă generez o cotă, acea xi este în intervalul [1..10] decât pentru toate combinațiile de tupluri de cotă, pot găsi o valoare secretă. Acest lucru este valabil și atunci când generez mai multe acțiuni [15...20], dar o parte interesantă este că atunci când amestec perechile din această serie 2, decât xi-urile îndepărtate oferă un răspuns greșit în interpolare. Deci am un bug în codul meu (ceea ce nu cred) sau Lagrange este foarte limitat în interpolare.
Macko avatar
drapel co
Deci, vreo idee pentru înlocuirea interpolării Lagrange?
Macko avatar
drapel co
Reconstrucția @poncho nu funcționează așa cum era de așteptat: am pregătit numărul prag de puncte (acțiuni) pe care le generau la început, apoi am creat puncte noi (xn-x' ,yn) apoi le-am pus la funcția mea de interpolare și le-am calculat la x '. Noile acțiuni au noul xi corect, dar rezultatul din interpolare le oferă tuturor aceeași valoare. Vă rog să dați un exemplu?
poncho avatar
drapel my
@Macko: „Le-am pus la funcția mea de interpolare și calculez la x’”; nu, calculați interpolarea la 0 (adică faceți exact logica standard de reconstrucție secretă)
Macko avatar
drapel co
@poncho Super! Da! Funcționează ca un farmec :) și nu se folosesc duble, nu se rezolvă ecuații, asta am vrut :) Mulțumesc mult...
Puncte:1
drapel sd

Să folosim o formă de prag (, ) pentru a partaja o valoare secretă. - 1 numere întregi aleatoare 1, 2, ..., â 1 sunt selectate în timp ce 0 = . Pe baza acestor factori, se construiește polinomul. fx....

Pe baza acestui lucru, obținem puncte aleatoare (, ()) ⶠâ 0. Fiecare punct este comunicat unuia dintre. Participanții. Pentru orice subset de puncte, polinomul poate fi reconstruit folosind interpolarea Lagrange. Având polinomul (), pentru valoarea = 0 obținem valoarea (0) = 0 care este secretul .

Rețineți că pentru o secretizare adecvată, toate operațiunile se fac cu elemente ale unui câmp finit cu dimensiunea unde primul număr este mai mare decât toate valorile coeficientului polinomului, precum și valorile t și n.

Macko avatar
drapel co
Este interpolarea Lagrange mai bună decât eliminarea gaussiană în găsirea coeficienților polinomi? poate descrie cum se face interpolarea probei folosind Lagrange pentru a găsi coefuri?
Pegasus avatar
drapel sd
Fie un polinom de gradul t: f (x) = a0 + a1x + ··· +atxt Poate fi reconstruit din t + 1 puncte (xi, f (xi)) cu secțiuni diferite (într-un mod unic) , Există polinoame de grade infinite ale lui t care trec prin t astfel de puncte.
Macko avatar
drapel co
Puteți da toate constrângerile atunci când generați noi acțiuni pentru un anumit secret: ca pragul nu mai puțin de 2? etc
Pegasus avatar
drapel sd
Noile acțiuni pot fi adăugate cu ușurință fără a le schimba pe cele vechi: Calcularea punctelor noi. Rețineți că poate exista mai mult de 1 share, de asemenea, polinomul poate fi editat fără a fi nevoie să schimbați secretul.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.