Cu această întrebare mă refer la multiplicarea BGW de Gennaro et al (PDF Aici).
Înmulțirea este descrisă pe pagina a 4-a.
(O altă sursă pentru mine a fost „O introducere pragmatică în calculul securizat cu mai multe părți” p. 43-44)
Rezumatul procedurii de înmulțire a BGW:
Pentru a face multiplicarea a 2 valori secrete $\alpha$ și $\beta$ a fiecărui jucător $P_i$ trebuie să aibă cota $f_{\alpha}(i)$ și $f_{\beta}(i)$ Unde $f_{\alpha}$ și $f_{\beta}$ sunt polinoamele aleatoare de grad t din partajarea secretă Shamir.
Acum fiecare jucător $P_i$ calculează $f_{\alpha}(i) \cdot f_{\beta}$ și trimite acțiuni de această valoare $h_i(j)$ creat cu polinomul de grad aleator t $h_i$ (astfel încât $h_i(0) = (f_{\alpha} \cdot f_{\beta})(i)$) stratul de deasupra $P_j$ pentru $1 \le j \le n$.
În continuare, lucrarea de mai sus descrie modul în care jucătorii pot obține cote aleatorii de grad t ale valorii $\alpha \cdot \beta$ (pentru ca apoi să reconstruiască rezultatul înmulțirii cu aceste acțiuni):
Fiecare jucător $P_i$ calculează valoarea $H(i)$ din polinomul de gradul t $H$ care este definit ca:
$$H(x) = \sum_{i=1}^{n} \lambda_i h_i(x)$$
($lambda_i$s sunt coeficienții Lagrange adecvați).
$H$ este un polinom aleatoriu cu
$$H(0) = \sum_{i=1}^{n} \lambda_i h_i(0) = \sum_{i=1}^{n} \lambda_i (f_{\alpha} \cdot f_{\beta })(i) = (f_{\alpha} \cdot f_{\beta})(0) = \alpha \cdot \beta$$
Intrebarea mea: H(x) este într-adevăr de gradul t? N-ar putea fi și mai mare pentru că $n$ puncte de la diferit polinoame de gradul t $h_i$ pentru $1 \le i \le n$ sunt folosite pentru interpolare? De obicei se argumentează că operațiile liniare pe $(t,n)$ acțiunile partajate rezultă în noi $(t,n)$ acțiuni și pentru că $h_i$ funcţiile sunt de grad $t$ combinații liniare de valori $h_i{j}$ pentru $1 \le i \le i$ ar trebui să aibă ca rezultat $(t,n)$ acțiunile de asemenea. Este valabil și în acest scenariu, deoarece combinăm întotdeauna valori de diferite grade $t$ polinoame în același timp $x$ valoare?
Alta intrebare: De asemenea, se remarcă faptul că $t$ trebuie să fie astfel încât $2t+1 \le n$. Este chiar necesar acest lucru? N-ar fi $t+1 \le n$ suficient pentru că $H(x)$ este gradul $t$ oricum sau informațiile de la 2t+1 acțiuni sunt necesare pentru a construi corect $H(x)$? (Ipoteza mea a fost că, fără $2t+1$ Coeficienții Lagrange $\lambda_i$, $H(0)$ nu ar fi $\alpha \cdot \beta$)
„Introducerea pragmatică” p. 44 spune că numai cu $2t+1 \le n$ jucătorii au suficiente informații pentru a determina valoarea $(f_{\alpha} \cdot f_{\beta})(0)$. De ce este acesta cazul?
