Câu hỏi liên quan đến lược đồ chia sẻ nhiều bí mật được mô tả trong bài báo sau:
[FY92] Matthew K. Franklin, Moti Yung:
Sự phức tạp trong giao tiếp của tính toán an toàn (Tóm tắt mở rộng). CỔ PHIẾU
1992: 699-710 (liên kết)
Sau đây là một số nền tảng. Tuy nhiên, nếu bạn đã quen thuộc với bài báo đó, bạn có thể bỏ qua trực tiếp đến câu hỏi chính bên dưới (được đánh dấu bằng phông chữ tiêu đề in đậm).
Một $(t-k+1,t+1;k,n)$-kế hoạch chia sẻ nhiều bí mật, như được định nghĩa trong [FY92], cho phép đại lý chia sẻ $ k $ bí mật giữa $n$ người chơi, sao cho bất kỳ tập hợp con nào của $t+1$ người chơi trở lên có thể khôi phục $k$ bí mật và bất kỳ tập hợp con người chơi nào có kích thước tối đa $t-k+1$ không thể tìm hiểu bất kỳ thông tin về $k$ bí mật.
Sơ đồ chia sẻ đa bí mật trong [FY92] sử dụng các tham số hệ thống/cài đặt sau:
- Để cho $F$ là một trường hữu hạn.
- Để cho $s_1,\cdots,s_n \in F$ là bí mật của đại lý.
- Để cho $\alpha_1,\cdots,\alpha_n$ và $e_1,\cdots,e_n$ được chọn trước các yếu tố của $F$ mà tất cả các bên đều biết.
- Để cho $p(x) = q(x) \prod_{i=1}^{k}(x-e_i) + \sum_{i=1}^{k} s_i L_i(x)$, ở đâu $q(x) \in_R F[x]$ với $deg(q(x))=(t-k)$, và
$$L_i(x)= \frac{\prod_{j\neq i}(x-e_j)}{\prod_{j\neq i}(e_i-e_j)}$$
Các đại lý phân phối cổ phần $p(\alpha_i)$ cho người chơi $P_i$, vì $1\leq i \leq n$.
Bất kỳ tập hợp con nào của người chơi có kích thước $\geq t+1$, có thể gộp các cổ phần của chúng lại với nhau và xây dựng lại đa thức $p(x)$, và sau đó tính toán các bí mật $s_i = p(e_i)$ vì $1\leq i \leq n$.
Ngược lại, đối với bất kỳ tập hợp con nào của $t-k+1$ chia sẻ có một đa thức duy nhất mà chia sẻ và bất kỳ $k$ bí mật. Do đó, bất kỳ tập con nào của $t-k+1$ người chơi tìm hiểu bất kỳ thông tin nào về $k$ bí mật.
Tính phần chia của tích bí mật từ phần chia của các bí mật riêng lẻ
Để cho $(y_1,\cdots,y_n)$ là người chia sẻ nhiều bí mật $(s'_1,\cdots,s'_n)$, và $(z_1,\cdots,z_n)$ là người chia sẻ nhiều bí mật $(s''_1,\cdots,s''_n)$. [FY92] mô tả một thuật toán để tính toán tỷ lệ chia sẻ nhiều $(v_1,\cdots,v_n)$ của sản phẩm bí mật $(s'_1 s''_1,\cdots,s'_n s''_n)$ từ các cổ phiếu đa phần riêng lẻ $(y_1,\cdots,y_n)$ và $(z_1,\cdots,z_n)$.
Các thuật toán hoạt động như sau:
- Mỗi người chơi $P_i$ tính toán $w_i = y_i \times z_i$. Điều này dẫn đến một tuple $(w_1,\cdots,w_n)$ mã hóa những bí mật $(s'_1 s''_1,\cdots,s'_n s''_n)$ sử dụng một $2t$-đa thức bậc.
- Vì một chia sẻ đa bí mật phải sử dụng một $t$-đa thức bậc, bộ $(w_1,\cdots,w_n)$ không phải là một chia sẻ bí mật hợp lệ. Thay vào đó, nó được gọi là giả đa chia sẻ.
- Một thủ tục giảm mức độ là cần thiết để chuyển đổi $(w_1,\cdots,w_n)$ giả đa chia sẻ thành đa chia sẻ hợp lệ $(v_1,\cdots,v_n)$, tức là, một trong đó sử dụng một mức độ-$t$ đa thức có dạng $p(x) = q(x) \prod_{i=1}^{k}(x-e_i) + \sum_{i=1}^{k} s_i L_i(x)$ như đã mô tả ở trên.
Bước giảm độ và trọng tâm/câu hỏi chính của bài đăng này
[FY92] đưa ra công thức sau để tính toán tỷ lệ đa chia sẻ $(v_1,\cdots,v_n)$ từ đa chia sẻ giả $(w_1,\cdots,w_n)$.
$$(w_1,\cdots,w_n). A = (v_1,\cdots,v_n)$$
ở đâu
$$ A = \sum_{k=1}^{\ell} B_\ell^{-1} Chặt_{t-k+1} B_\ell M_\ell$$
và
- $B_\ell$ là ma trận vandermonde có $(i,j)$ mục nhập là $(\alpha_j - e_\ell)^{i-1}$
- $Chop_{t-k+1}$ là ma trận chiếu trên đầu tiên ${t-k+1}$ vectơ của cơ sở không gian.
- $M_\ell$ là ma trận có $(i,j)$ mục nhập là $L_\ell(\alpha_i)$ vì $i=j$, và không ở mọi nơi khác.
Câu hỏi chính của bài viết này
Các tác giả không giải thích làm thế nào họ lấy được công thức.
$$ A = \sum_{k=1}^{\ell} B_\ell^{-1} Chặt_{t-k+1} B_\ell M_\ell$$
Ai đó có thể giúp tôi rút ra công thức đó hoặc chứng minh tính đúng đắn của nó không? [Tôi không nghi ngờ gì nó đúng. Tôi chỉ muốn tìm hiểu làm thế nào các tác giả bắt nguồn nó]
Đây là một số cách tiếp cận tôi đã thử cho đến nay.
Đầu tiên, lưu ý rằng chúng ta có thể viết lại đa thức dùng để chia dưới dạng tổng của $k$ các điều khoản như sau.
$$
\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)\ phải) + \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*}
$$
ở đâu $q'_\ell(x)=\frac{1}{k}q(x)(x-e_\ell) +s_\ell$ là một $(t-k+1)$-đa thức bậc.
Bây giờ giả sử chúng ta có hai bộ bí mật $(s'_1,\cdots,s'_n)$ và $(s''_1,\cdots,s''_n)$ chia sẻ thông qua đa thức $p_1(x)$ và $p_2(x)$. Sản phẩm $P(x)=p_1(x)p_2(x)$ là một $2t$-đa thức bậc cũng có thể được viết dưới dạng tổng của $k$ các điều khoản như hình dưới đây:
$$
\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*}
$$
ở đâu
- $Q_\ell(x)= q'_\ell(x) \ p_2(x)$ là một $(2t-k+1)$-đa thức bậc sao cho $Q_\ell(e_\ell)=s_\ell$ ($s_\ell = s'_\ell s''_\ell$ là sản phẩm của bí mật mà chúng tôi muốn tính toán.)
- đa thức $Q'_\ell(x)$ được lấy từ $Q_\ell(x)$ thông qua một sự thay đổi của biến, sao cho $Q'_\ell(x-e_\ell) = Q_\ell(x)$. Đặc biệt, $Q'_\ell(0) = Q_\ell(e_\ell) = s_\ell$.
Để cho $H_\ell=(h_{0,\ell},\cdots,h_{2t-k,\ell},0,\cdots,0)$ biểu thị vectơ kích thước $n$ chứa các hệ số của $Q'_\ell$. Đặc biệt, chúng tôi có $h_{0,\ell} = s_\ell$.
Để cho $(w_1,\cdots,w_n)$ là một giả chia sẻ nhiều bí mật $(s_1,\cdots,s_n)$. Sau đó chúng tôi có
$$
\begin{alignat*}{2}
(w_1,\cdots,w_n) &= (P(\alpha_1),\cdots,P(\alpha_n))\
&= \sum_{\ell=1}^{k} H_\ell \ . Chuông \ . M_\ell
\end{alignat*}
$$
ở đâu $B_\ell$ là ma trận vandermonde có kích thước $n$ của ai $(i,j)$ mục nhập là $(\alpha_j-e_\ell)^{i-1}$, và $M_\ell$ là một ma trận vuông có kích thước $n$ của ai $(i,j)$ mục nhập là $L_\ell(\alpha_i)$ vì $i=j$, và $0$ mọi nơi khác.
Mặt khác, hãy để $(v_1,\cdots,v_n)$ được chia sẻ nhiều bí mật $(s_1,\cdots,s_n)$ và để cho $R(x)$ là mức độ tương ứng-$t$ đa thức. Sau đó chúng tôi có
$$
\begin{alignat*}{2}
(v_1,\cdots,v_n) &= (R(\alpha_1),\cdots,R(\alpha_n))\
&= \sum_{\ell=1}^{k} H_\ell \ . Chặt_{t-k+1} \ . Chuông \ . M_\ell
\end{alignat*}
$$
Điều trên là hợp lệ vì đa thức $R(x)$ định nghĩa dưới đây thực sự là một mức độ-$t$ đa thức sao cho $R(e_\ell) = s_\ell$ cho tất cả $1 \leq \ell \leq k$.
$$
\begin{alignat*}{2}
R(x) &= \sum_{\ell=1}^{k} Q''_\ell(x-e_\ell) L_\ell(x)\
\end{alignat*}
$$
với $Q''_\ell(x-e_\ell)$ một $(t-k+1)$-đa thức bậc sao cho $Q''_\ell(0)=s_\ell$ cho tất cả $1 \leq \ell \leq k$.
Từ $Q''_\ell(0)=Q'_\ell(0)=h_{0,\ell}=s_\ell$ cho tất cả $1 \leq \ell \leq k$, bộ sau đây là một tập hợp các hệ số hợp lệ cho $Q''_\ell(x)$:
$$
\begin{alignat*}{2}
Địa ngục \ . Chặt_{t-k+1} &= (h_{0,\ell},\cdots,h_{2t-k,\ell},0,\cdots,0) \ . Chặt_{t-k+1}\
&= (h_{0,\ell},\cdots,h_{t-k,\ell},0,\cdots,0)
\end{alignat*}
$$
Bây giờ từ hai biểu thức của $(w_1,\cdots,w_n)$ và $(v_1,\cdots,v_n)$ ở trên, chúng ta cần đi đến công thức
$$(w_1,\cdots,w_n). A = (v_1,\cdots,v_n)$$ với
$$ A = \sum_{k=1}^{\ell} B_\ell^{-1} Chặt_{t-k+1} B_\ell M_\ell$$
Bất kỳ suy nghĩ hoặc đề nghị?
