Întrebarea este legată de schema de partajare multi-secretă descrisă în următoarea lucrare:
[FY92] Matthew K. Franklin, Moti Yung:
Complexitatea de comunicare a calculului securizat (Rezumat extins). STOC
1992: 699-710 (Legătură)
Următoarele sunt câteva fonduri. Cu toate acestea, dacă sunteți familiarizat cu lucrarea respectivă, puteți sări direct la întrebarea principală de mai jos (evidențiată cu font aldine pentru antet).
A $(t-k+1,t+1;k,n)$-schema de partajare cu mai multe secrete, așa cum este definită în [FY92], permite unui dealer să partajeze $k $ secrete printre $n$ jucători, astfel încât orice subset de $t+1$ jucătorii sau mai mulți pot recupera $k$ secrete și orice subset de jucători de până la $t-k+1$ nu pot afla nicio informație despre $k$ secrete.
Schema de partajare multi-secretă din [FY92] utilizează următorii parametri de setare/sistem:
- Lăsa $F$ fi un câmp finit.
- Lăsa $s_1,\cdots,s_n \în F$ fie secretele dealerului.
- Lăsa $\alpha_1,\cdots,\alpha_n$ și $e_1,\cdots,e_n$ fie elemente preselectate ale $F$ care sunt cunoscute de toate partidele.
- Lăsa $p(x) = q(x) \prod_{i=1}^{k}(x-e_i) + \sum_{i=1}^{k} s_i L_i(x)$, Unde $q(x) \in_R F[x]$ cu $deg(q(x))=(t-k)$, și
$$L_i(x)= \frac{\prod_{j\neq i}(x-e_j)}{\prod_{j\neq i}(e_i-e_j)}$$
Dealerul distribuie cota $p(\alpha_i)$ stratul de deasupra $P_i$, pentru $1\leq i \leq n$.
Orice subset de jucători de dimensiune $\geq t+1$, își pot pune acțiunile împreună și pot reconstrui polinomul $p(x)$, apoi calculează secretele $s_i = p(e_i)$ pentru $1\leq i \leq n$.
Dimpotrivă, pentru orice subset de $t-k+1$ acțiuni există un singur polinom acele acțiuni și orice $k$ secrete. Prin urmare, orice subset de $t-k+1$ jucătorii învață orice informații despre $k$ secrete.
Calcularea cotelor produsului secretelor din cotele secretelor individuale
Lăsa $(y_1,\cdots,y_n)$ fi multi-partea de secrete $(s'_1,\cdots,s'_n)$, și $(z_1,\cdots,z_n)$ fi multi-partea de secrete $(s''_1,\cdots,s''_n)$. [FY92] descrie un algoritm pentru a calcula multi-share $(v_1,\cdots,v_n)$ a produsului secretelor $(s'_1 s''_1,\cdots,s'_n s''_n)$ din acțiunile multiple individuale $(y_1,\cdots,y_n)$ și $(z_1,\cdots,z_n)$.
Algoritmul funcționează după cum urmează:
- Fiecare jucător $P_i$ calculează $w_i = y_i \times z_i$. Rezultă un tuplu $(w_1,\cdots,w_n)$ care codifică secretele $(s'_1 s''_1,\cdots,s'_n s''_n)$ folosind un 2t $-polinom de grad.
- Deoarece o partajare multi-secretă trebuie să folosească a $t$-polinom de grad, tuplu $(w_1,\cdots,w_n)$ nu este o multi-share validă a secretelor. În schimb, se numește pseudo multi-share.
- Este necesară o procedură de reducere a gradului pentru a converti $(w_1,\cdots,w_n)$ pseudo-multi-share la un multi-share valid $(v_1,\cdots,v_n)$, adică unul care utilizează un grad-$t$ polinom al formei $p(x) = q(x) \prod_{i=1}^{k}(x-e_i) + \sum_{i=1}^{k} s_i L_i(x)$ așa cum este descris mai sus.
Pasul de reducere a gradului și obiectivul/întrebarea principală a acestei postări
[FY92] oferă următoarea formulă pentru calcularea cotei multiple $(v_1,\cdots,v_n)$ din pseudo-acțiunea multiplă $(w_1,\cdots,w_n)$.
$$(w_1,\cdots,w_n). A = (v_1,\cdots,v_n)$$
Unde
$$ A = \sum_{k=1}^{\ell} B_\ell^{-1} Chop_{t-k+1} B_\ell M_\ell$$
și
- $B_\ell$ este matricea vandermonde a cărei $(i,j)$ intrarea este $(\alpha_j - e_\ell)^{i-1}$
- $Chop_{t-k+1}$ este matricea de proiecție pe prima ${t-k+1}$ vectori ai bazei spațiale.
- $M_\ell$ este matricea a cărei $(i,j)$ intrarea este $L_\ell(\alpha_i)$ pentru $i=j$, și zero peste tot.
Întrebarea principală a acestei postări
Autorii nu explică cum au derivat formula.
$$ A = \sum_{k=1}^{\ell} B_\ell^{-1} Chop_{t-k+1} B_\ell M_\ell$$
Mă poate ajuta cineva să obțin această formulă sau să-i dovedesc corectitudinea? [Nu am nicio îndoială că este corect. Vreau doar să-mi dau seama cum l-au derivat autorii]
Iată câteva dintre abordările pe care le-am încercat până acum.
În primul rând, rețineți că putem rescrie polinomul folosit pentru partajare ca o sumă a $k$ termenii după cum urmează.
$$
\begin{alignat*}{2}
p(x) &= q(x) \prod_{\ell=1}^{k}(x-e_\ell) + \sum_{\ell=1}^{k} s_\ell L_\ell(x ) \
&= q(x) \ \frac{1}{k} \sum_{\ell=1}^{k} \left(\prod_{\ell=1}^{k}(x-e_\ell)\ dreapta) + \sum_{\ell=1}^{k} s_\ell L_\ell(x) \
&= q(x) \ \sum_{\ell=1}^{k} \left(\frac{(x-e_\ell)}{k} L_\ell(x) \right) + \sum_{\ ell=1}^{k} s_\ell L_\ell(x) \
&= \sum_{\ell=1}^{k} \left(\frac{q(x)(x-e_\ell)}{k} +s_\ell \right) L_\ell(x) \
&= \sum_{\ell=1}^{k} q'_\ell(x) L_\ell(x)
\end{alignat*}
$$
Unde $q'_\ell(x)=\frac{1}{k}q(x)(x-e_\ell) +s_\ell$ este o $(t-k+1)$-polinom de grad.
Acum presupunem că avem două seturi de secrete $(s'_1,\cdots,s'_n)$ și $(s''_1,\cdots,s''_n)$ împărtășită prin polinoame $p_1(x)$ și $p_2(x)$. Produsul $P(x)=p_1(x)p_2(x)$ este o 2t $-polinom de grad care poate fi scris și ca o sumă de $k$ termeni după cum se arată mai jos:
$$
\begin{alignat*}{2}
P(x) &= p_1(x) p_2(x) \
&= \sum_{\ell=1}^{k} q'_\ell(x) p_2(x) L_\ell(x)\
&= \sum_{\ell=1}^{k} Q_\ell(x) L_\ell(x)\
&= \sum_{\ell=1}^{k} Q'_\ell(x-e_\ell) L_\ell(x)\
\end{alignat*}
$$
Unde
- $Q_\ell(x)= q'_\ell(x) \ p_2(x)$ este o $(2t-k+1)$-polinom de grad, astfel încât $Q_\ell(e_\ell)=s_\ell$ ($s_\ell = s'_\ell s''_\ell$ este produsul secretelor pe care vrem să le calculăm.)
- Polinomul $Q'_\ell(x)$ se obtine din $Q_\ell(x)$ printr-o schimbare de variabilă, astfel încât $Q'_\ell(x-e_\ell) = Q_\ell(x)$. În special, $Q'_\ell(0) = Q_\ell(e_\ell) = s_\ell$.
Lăsa $H_\ell=(h_{0,\ell},\cdots,h_{2t-k,\ell},0,\cdots,0)$ notează vectorul mărimii $n$ conţinând coeficienţii de $Q'_\ell$. În special, avem $h_{0,\ell} = s_\ell$.
Lăsa $(w_1,\cdots,w_n)$ fi un pseudo-multi-share de secrete $(s_1,\cdots,s_n)$. Atunci noi avem
$$
\begin{alignat*}{2}
(w_1,\cdots,w_n) &= (P(\alpha_1),\cdots,P(\alpha_n))\
&= \sum_{\ell=1}^{k} H_\ell \ . Clopot \ . M_\ell
\end{alignat*}
$$
Unde $B_\ell$ este matricea de mărime vandermonde $n$ a caror $(i,j)$ intrarea este $(\alpha_j-e_\ell)^{i-1}$, și $M_\ell$ este o matrice pătrată de dimensiune $n$ a caror $(i,j)$ intrarea este $L_\ell(\alpha_i)$ pentru $i=j$, și $0$ oriunde altundeva.
Pe de altă parte, lasă $(v_1,\cdots,v_n)$ să fie o multi-partă de secrete $(s_1,\cdots,s_n)$ si lasa $R(x)$ fie gradul corespunzător-$t$ polinom. Atunci noi avem
$$
\begin{alignat*}{2}
(v_1,\cdots,v_n) &= (R(\alpha_1),\cdots,R(\alpha_n))\
&= \sum_{\ell=1}^{k} H_\ell \ . Chop_{t-k+1} \ . Clopot \ . M_\ell
\end{alignat*}
$$
Cele de mai sus sunt valabile deoarece polinomul $R(x)$ definit mai jos este într-adevăr un grad-$t$ polinom astfel încât $R(e_\ell) = s_\ell$ pentru toți $1 \leq \ell \leq k$.
$$
\begin{alignat*}{2}
R(x) &= \sum_{\ell=1}^{k} Q''_\ell(x-e_\ell) L_\ell(x)\
\end{alignat*}
$$
cu $Q''_\ell(x-e_\ell)$ A $(t-k+1)$-polinom de grad astfel încât $Q''_\ell(0)=s_\ell$ pentru toți $1 \leq \ell \leq k$.
De cand $Q''_\ell(0)=Q'_\ell(0)=h_{0,\ell}=s_\ell$ pentru toți $1 \leq \ell \leq k$, următorul tuplu este un set valid de coeficienți pentru $Q''_\ell(x)$:
$$
\begin{alignat*}{2}
Iad \ . Chop_{t-k+1} &= (h_{0,\ell},\cdots,h_{2t-k,\ell},0,\cdots,0) \ . Chop_{t-k+1}\
&= (h_{0,\ell},\cdots,h_{t-k,\ell},0,\cdots,0)
\end{alignat*}
$$
Acum din cele două expresii ale $(w_1,\cdots,w_n)$ și $(v_1,\cdots,v_n)$ mai sus, trebuie să ajungem la formulă
$$(w_1,\cdots,w_n). A = (v_1,\cdots,v_n)$$ cu
$$ A = \sum_{k=1}^{\ell} B_\ell^{-1} Chop_{t-k+1} B_\ell M_\ell$$
Ceva gânduri sau sugestii?
