Puncte:0

Shamir Secret Sharing și înlocuirea interpolării Lagrange

drapel co

Shamir Secter Sharing în versiunea standard (versiunea de hârtie) funcționează destul de bine cu Lagrange Interpolation pentru a genera mai multe acțiuni. Problemele apar atunci când generați mai multe perechi (xi, yi) și încercați să reconstruiți secretul din acțiuni care sunt cam îndepărtate unele de altele. Algoritmul funcționează, dar valoarea secretului pe care îl obțineți este oarecum diferită, ceea ce este inacceptabil pentru utilizarea în producție. Cred că are legătură cu Fenomenul Runge.

Deci care sunt opțiunile? Există interpolări mai bune de folosit? Poate că există un fel de modalitate de a genera (xi,yi) din secret care ar putea da rezultate stabile de către Lagrange?

În prezent, am trecut la gaussian ca fiind cel mai stabil din punct de vedere computațional.

Morrolan avatar
drapel ng
Asta nu pare corect. Lucrezi într-un câmp finit cu valori întregi? Nu ar trebui să existe nicio pierdere de precizie în perechile coeficient/valoare, astfel încât interpolarea (cu o cantitate suficientă de puncte) ar trebui să producă un rezultat exact. Vezi și asta: https://crypto.stackexchange.com/questions/14608/does-runge-phenomenon-affect-shamirs-secret-sharing-scheme?rq=1
Macko avatar
drapel co
Nu lucrez într-un domeniu finit. Eu generez 5 acțiuni la pornire cu pragul setat la 2. Decat mai generez 5 acțiuni trecând ca intrare cel puțin 2 acțiuni de la generarea de pornire.
poncho avatar
drapel my
Dacă nu lucrezi într-un domeniu finit, de ce crezi că ceea ce faci este sigur?
Macko avatar
drapel co
Deci, afirmi că, dacă fac interpolarea în câmp finit, Lagrange va funcționa corect? Să rămânem la întrebarea...
Morrolan avatar
drapel ng
Da. Într-un câmp finit nu veți suferi nici un fel de pierdere de precizie, astfel încât interpolarea este garantată pentru a produce polinomul original cu care am început. Consultați răspunsul de mai sus pentru mai multe detalii. Dar este important să înțelegeți că lucrul într-un domeniu finit este **absolut necesar** pentru securitate.Împărtășirea secretă a lui Shamir asupra realului oferă foarte puțin în ceea ce privește securitatea.
Daniel avatar
drapel ru
@Morrolan Am postat asta de mai multe ori săptămâna aceasta, dar este important să risipiți ideea greșită că aveți absolut nevoie de *un câmp finit. **Orice** inel finit funcționează atâta timp cât punctele pe care le alegeți pentru evaluare satisfac anumite proprietăți (diferențele diferite de zero fiind inversabile) https://crypto.stackexchange.com/a/96507/13843 . Desigur, numerele reale, fiind infinite, nu se încadrează în această categorie.
Mark avatar
drapel ng
De asemenea, merită menționat faptul că SSS nu necesită interpolare lagrange, iar extensiile acesteia pot fi utile. În special, SSS poate fi reformat în termeni de coduri Reed-Solomon. Folosind decodarea standard Reed-Solomon (să zicem Berklamp-Massay), se poate obține o versiune de SSS care este tolerantă la un anumit număr de acțiuni care sunt corupte (codul Reed-Solomon de bază „corectează” aceste „erori”). Totuși, acest lucru necesită schimbarea algoritmului de reconstrucție/decodificare.
Macko avatar
drapel co
@Daniel, deci dacă nu am nevoie neapărat de câmp finit, cum să aleg punctele? Dacă aleg puncte în conformitate cu o anumită regulă (are nevoie de explicații), atunci ar trebui să funcționeze interpolarea pentru ele?
Macko avatar
drapel co
@Mark Reed-Solomon folosește câmp finit sub capotă? Este Reed-Solomon o versiune generalizată a SSS?
Macko avatar
drapel co
Așa că aleg opțiunea de schimbare a interpolării: ce zici de Chebyshev?
Mark avatar
drapel ng
@Macko să intre în aceste detalii probabil că te-ar deruta în acest moment. Aprecierea dvs. ar trebui să fie că SSS necesită „aritmetică finită” (puteți simplifica în câmpuri finite pentru a începe) pentru ca dovada de securitate să treacă. În această setare de câmp finit, interpolarea lagrange funcționează bine. Există și alte opțiuni (cum ar fi Berkleamp Massay) dacă aveți cerințe mai specializate, dar nu v-ați exprimat încă. În setarea aritmetică finită, nu există niciun fenomen Runge, așa că problema dvs. ar trebui rezolvată (și construcția dvs. va fi de fapt sigură - în prezent nu este)

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.