為什麼 BGW 乘法門有效？
我正在閱讀有關 BGW 協議的實用 MPC（連結）。我還在這裡交叉引用（點擊幻燈片的講座連結） *資訊理論設置的 BGW 構造 – Benny Pinkas 我不明白為什麼乘法門計算可以工作。
首先，讓我們說 $ N $ 聚會，聚會 $ P_i $ 有電線的股份 $ \alpha $ , $ \beta $ 作為 $ [v_{\alpha}] $ , $ [v_{\beta}] $ . 他可以將它們相乘以獲得多項式上的一個點 $ q(x) = p_{\alpha}(x) p_{\beta}(x) $ . 但是每個人的價值觀只能一起重建 $ q(x) $ ， 在哪裡 $ q(x) $ 是學位 $ 2t $ .
有用的事實：我們說存在 $ \lambda_i $ 為了 $ i =1 $ 至 $ N $ （或者可以索引到 $ 2t+1 $ ，但我不知道為什麼）這樣 $ q(0) = \sum_{i=1}^N \lambda_i q(i) $ （我猜派對 $ P_i $ 有價值 $ q(i) $ 在他的手中）。這 $ \lambda_i $ 是“適當的拉格朗日係數”。
每一個聚會 $ P_i $ 可以分享他們的價值 $ q(i) $ . 他們挑選 $ g_i $ 這樣 $ g_i(0) = q(i) $ . （該多項式在書中未命名，但可能使事情更明確）。然後 $ P_i $ 向所有各方共享，因此他們擁有股份 $ [q(i)] $ .
如果我們再想想什麼 $ P_i $ 正在接收，他得到的股份 $ g_j(0) $ 對於每個 $ j $ ，對他來說，這意味著他得到了價值 $ g_j(i) $ .
那麼，每個 $ P_i $ 關於輸入 $ g_j(i) $ 使用這些積分為自己創建共享 $ [q(0)] = \sum_{i=1}^N \lambda_i [q(i)] $ . 派對用 $ P_i $ ，這意味著他可以弄清楚 $ q(i) = \sum_{i=1}^n \lambda_i g_j(i) $ .
價值 $ q(i) $ 原來是他們的份額 $ [v_{\alpha}v_{\beta}] $ .
- 我明白這些 $ \lambda_i $ 應該與有用的事實相同。為什麼？
- 有用的事實從何而來？
- 我還查看了一篇論文（未通讀）A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation 連結，他們說 $ q(x) $ （他們稱之為 $ h(x) $ ) 具有“特定結構”。這是什麼意思？
在哪裡 $ \lambda_i $ 是從哪裡來的？
考慮一個 4 次多項式， $ p(x) = p_4 x^4 + p_3 x^3 + \cdots + p_0 $ . 我們可以將多項式評估寫成對係數的線性運算：
$$ \begin{bmatrix} p(1) \ p(2) \ p(3) \ p(4) \ p(5) \end{bmatrix}
\begin{bmatrix} 1^0 & 1^1 & 1^2 & 1^3 & 1^4 \ 2^0 & 2^1 & 2^2 & 2^3 & 2^4 \ 3^0 & 3^1 & 3^2 & 3^3 & 3^4 \ 4^0 & 4^1 & 4^2 & 4^3 & 4^4 \ 5^0 & 5^1 & 5^2 & 5^3 & 5^4 \end{bmatrix} \begin{bmatrix} p_0 \ p_1 \ p_2 \ p_3 \ p_4 \end{bmatrix} $$
中間的矩陣是 Vandermonde 矩陣，因此它具有滿秩。
現在這也意味著范德蒙德矩陣的行構成了一個基。所以另一個向量像 $ [1~0~0~0~0] $ 可以寫成這些行的線性組合，比如：
$$ \begin{bmatrix}1 & 0 & 0 & 0 & 0\end{bmatrix}
\begin{bmatrix}\lambda_1 & \lambda_2 & \lambda_3 & \lambda_4 & \lambda_5\end{bmatrix} \begin{bmatrix} 1^0 & 1^1 & 1^2 & 1^3 & 1^4 \ 2^0 & 2^1 & 2^2 & 2^3 & 2^4 \ 3^0 & 3^1 & 3^2 & 3^3 & 3^4 \ 4^0 & 4^1 & 4^2 & 4^3 & 4^4 \ 5^0 & 5^1 & 5^2 & 5^3 & 5^4 \end{bmatrix} $$
在右邊乘以係數向量，你可以看到
$$ p(0) = p_0 = \sum_i \lambda_i p(i) $$
更一般地說，如果你有 $ d+2 $ 不同點 $ x_0, x_1, \ldots, x_{d+1} $ ，則存在係數 $ \lambda_1, \ldots, \lambda_{d+1} $ 具有以下屬性：對於任何學位- $ d $ 多項式 $ p $ ， 你可以寫 $ p(x_0) = \sum_{i=1}^{d+1} \lambda_i p(x_i) $ . 這 $ \lambda_i $ 係數是“范德蒙德矢量”的係數 $ x_0 $ 當寫在 Vandermonde 矩陣的基礎上時 $ x_1, \ldots, x_{d+1} $ ，這確實是一個非奇異矩陣。
什麼是“特定結構”？
它在下一句中說（第 14 頁）：
此外， $ h(x) $ 以這種方式生成的不是“隨機多項式”，而是具有特定的結構。例如， $ h(x) $ 通常是不可約的（因為它可以表示為 $ f_a(x) $ 和 $ f_b(x) $ )，這可能會洩露資訊。
如果我要改寫他們所說的話：鑑於學位- $ t $ 沙米爾的分享 $ a $ 和 $ b $ ，每個人都可以在本地（即無需通信）倍增他們的份額。結果是一個學位- $ 2t $ 分享。但是有兩個問題：
- 如果這條線用於隨後的乘法門，我們需要在一個度數上共享該值- $ t $ 多項式。
- 這條線可能不會在後續的乘法門中使用。考慮它是輸出線的情況，那麼我們在這種情況下唯一要做的就是打開所有共享（以顯示輸出）。現在確實，多項式的次數並不重要。但是多項式的分佈很重要，因為整個多項式在股份公佈時都會被披露。
這裡的多項式已知是兩個度的乘積 $ t $ 多項式。因此，如果多項式被揭示，它的因子也被揭示，並且很明顯 $ a $ 是一個因子的常數項，並且 $ b $ 是另一個因子的常數項。換句話說，協議會洩露 $ a $ 和 $ b $ 而我們只想要產品 $ ab $ 顯示為輸出。
我會注意到第二個“問題”也可以通過添加隨機 $ 2t $ - 共享 0（而不是進行互動式程度降低步驟）。但無論哪種情況，局部相乘的“原始”結果都不適合直接使用。該協議必須包含一些“清理”它的機制。