Acțiunile Shamir împărtășesc în secret numere aleatoare distribuite uniform?

Lăsa $t$ să fie un prag în schema Shamir secret sharing (SSS).

Să presupunem că știm $t'<t$ acțiuni. Să presupunem că ni se oferă niște valori aleatoare alese uniform din același câmp ca cel folosit în SSS.

Întrebare: putem distinge valorile aleatoare de acțiunile cu o probabilitate deloc neglijabilă?

Să presupunem că știm $t'<t$ acțiuni. Să presupunem că ni se oferă niște valori aleatoare alese uniform din același câmp ca cel folosit în SSS.

Întrebare: putem distinge valorile aleatoare de acțiunile cu o probabilitate deloc neglijabilă?

Depinde.

Acum, există două moduri posibile de a vă interpreta întrebarea (și deși răspunsul este același pentru ambele, logica diferă ușor). Iată modurile în care văd:

• Aceste $r$ „valorile aleatorii” trebuie considerate dintr-o dată ca acțiuni potențiale; adică adversarului i s-a dat un total de $t' + r$ acțiuni, $t'$ dintre care sunt adevărate acțiuni și $r$ dintre care ar putea fi valori aleatorii sau (în ceea ce privește adversarul) ar putea fi și acțiuni adevărate. Dacă este cazul, urmați logica de mai jos.

• Aceste $r$ „valorile aleatoare” sunt toate posibilitățile cotei lipsă. Acesta este, $r-1$ dintre ele sunt valori aleatorii (și adversarul știe asta), acea ultimă valoare ar putea fi, de asemenea, o valoare aleatoare sau poate fi o valoare adevărată - adversarul nu știe care și, de asemenea, nu știe care ar putea fi valoare adevarata. Dacă este cazul, urmați logica de mai jos, dar cu $r=1$, și iterați prin diferitele posibilități pentru cota cinstită.

Voi presupune, de asemenea, că atacatorul are unele cunoștințe despre care ar putea fi secretul partajat; s-ar putea să nu știe valoarea exactă, dar s-ar putea să știe că valoarea este una dintr-un set mic de posibilități (sau cel puțin, să știe că există un set mare de valori care nu poate fi).

În acest caz, dacă $t' + r < t$, atunci adversarul nu poate determina nimic; toate aceste acțiuni par aleatorii. Adică, pentru orice valoare a acțiunilor cunoscute și orice valoare a secretului partajat, există posibili coeficienți pentru polinomul necunoscut care ar face ca să conducă la valorile observate (și se dovedește că există un număr egal de posibilități independente de valorile observate, prin urmare adversarul nici măcar nu poate obține nicio informație probabilistică).

Pe de altă parte, dacă $t' + r \ge t$, atunci adversarul are o abordare; el poate lua acțiunile pe care le are (atât cele cunoscute bune, cât și cele cu providență îndoielnică) și să reconstituie ce secret comun ar implica acestea; ar verifica apoi să vadă dacă acel secret împărtășit era posibil. Dacă nu este una dintre valorile posibile, el știe că unele dintre acțiunile pe care le-a folosit au fost incorecte.

Fiecare valoare a gradului $t-1$ polinom SSS complet $P$ evaluat la orice $x$ în câmpul finit $F$ este definit peste este distribuit uniform în $F$. Vedea acest raspuns de exemplu.

Acum presupuneți $tâ<t$ acțiunile sunt dezvăluite, spunem că sunt $Sâ=\{(x_1,P(x_1)),\ldots,(x_{tâ},P(x_{tâ}))\}.$

Dacă setul inițial de acțiuni a fost $S$ multimea nevid $T=S\setminus Sâ$ acum determină în mod unic în mod obișnuit un polinom de interpolare Lagrange valid de grad $t-tâ-1$ dat oricare $t-tâ$ puncte $x$ în $K \setminus \{x_1,\ldots,x_{tâ}\}$.

Algoritm distinctiv: Lăsa $k>t-tâ$ și lăsați acțiuni revendicate $$C=\{(x_j,y_j):1\leq j \leq k\}$$ să se acorde. Dacă acestea sunt acțiuni autentice vreuna $t-tâ$ dintre ele vor da același polinom de interpolare Lagrange ca orice alt astfel de submulțime de aceeași dimensiune. Dacă $y_j$ sunt aleatorii, două interpolări Lagrange distincte spun că două sunt susținute $$A=\{x_1,\ldots,x_{t-tâ}\}$$ și pe $$Aâ=\{x_2,\ldots,x_{t-tâ},x_{t-tâ+1}\}$$ va da diferit Polinoame de interpolare Lagrange cu probabilitate $$1-\frac{1}{q}$$ Unde $q$ este dimensiunea câmpului pe care îl folosim.

De fapt, chiar dacă doar un singur acționează $A \bigcup Aâ$ este aleatorie, această proprietate va fi valabilă deoarece cel puțin una dintre interpolări va produce un polinom aleatoriu.

Nu, nu putem.Știm că SSS este perfect, ceea ce înseamnă că cunoașterea (t-1) sau mai puține acțiuni nu oferă informații despre s - prin urmare despre alte acțiuni -