BGW 乘法：它是如何工作的？
我無法理解如何在 BGW 協議中為 3 方執行乘法。參考：https ://crypto.stanford.edu/pbc/notes/crypto/bgw.html
我知道在乘法中，我們計算
r(x) = p(x)q(x)，但這意味著這r(x)是一個多項式 degree2t。這個多項式如何在電路中重新分配，以獲得 O(n^2) 複雜度的 BGW 協議乘法？請注意，
p(x)和q(x)都是度數多項式，t因為我以半誠實對手的情況為例，t < n/2.
我們可以使用源文件的符號，但我會說我們正在嘗試計算 $ ab = c $ （為了 $ a,b,c\in\mathbb{F}_p $ )，所以我可以使用 $ x $ 在討論多項式時作為變數。
讓 $ a_1,\dots, a_n $ 和 $ b_1,\dots, b_n $ 是 $ t $ -在……之外- $ n $ 的秘密分享 $ a, b $ . 回想一下，這意味著它們是通過隨機計算的 $ t $ -度多項式： $$ A(x) = \sum_{i = 0}^t \alpha_i x^i,\quad B(x) = \sum_{i = 0}^t\beta_i x^i $$ 在哪裡 $ A(0) = a, B(0) = b $ （所以隨機受這個條件）。然後通過評估點上的多項式來創建份額 $ {1,2,\dots,n} $ . 尤其是： $$ \forall i \in{1,\dots,n} : a_i = A(i),\quad b_i = B(i) $$ 現在我們要計算產品。多項式 $ C(x) = A(x)B(x) $ 有正確的常數項（如 $ C(0) = A(0)B(0) = ab $ ），但程度太高（正如你提到的）。此外，“股份” $ C(i) $ 可以在本地計算，如 $ C(i) = A(i)B(i) = a_ib_i $ .
但 $ C(x) $ 是學位 $ 2t $ （正如你提到的）。我們想找到一些其他多項式 $ \mathcal{C}(x) $ 這樣：
- $ \mathcal{C}(0) = C(0) = ab $
- $ \mathcal{C}(x) $ 是學位 $ t $
- 計算 $ \mathcal{C}(i) $ 如果您已經知道，則不是“太貴”（在交流中） $ A(i) $ 和 $ B(i) $
那我們該怎麼辦？這個想法是利用有兩種不同的方式來表示程度 $ t $ 多項式：
- 通過他們的 $ t+1 $ 係數（這是“顯而易見的”）方式
- 通過對他們的評估（至少） $ t+1 $ 不同點
這些中的任何一個都足以唯一地重建多項式。令人驚訝的是，您可以使用線性運算從一個轉換為另一個。
要了解我們如何建立這一點，請回想一下 $ n\times n $ 矩陣 $ D $ 和矢量 $ \vec{v} = (v_1,\dots, v_n) $ ，我們有： $$ (D\vec{v})i = \sum{k = 0}^{n-1}D_{i, k} v_k $$
請注意，這類似於表達式： $$ A(x) = \sum_{i = 0}^t \alpha_i x^i $$ 如果我們確定評估點 $ {1,\dots, n} $ ，那麼我們實際上有： $$ A(i) = \sum_{k = 0}^t \alpha_k i^k $$ 這建議設置 $ D_{i, k} = i^k $ 和 $ v_k = \alpha_k $ . 這正是我們要做的，通過定義 Vandermonde 矩陣（關於上述評估點）： $$ V = \begin{pmatrix} 1^0 & 1^1 & \dots & 1^{n-1}\ 2^0 & 2^1 & \dots & 2^{n-1} \ \vdots && \ddots & \vdots\ n^0 & n^1 & \dots & n^{n-1} \end{pmatrix} $$ 注意： $$ V\begin{pmatrix}\alpha_0\\vdots\\alpha_{n-1}\end{pmatrix} =\begin{pmatrix} \sum_{k = 0}^{n-1} \alpha_i 1^i\ \sum_{k = 0}^{n-1} \alpha_i 2^i\ \vdots\ \sum_{k = 0}^{n-1} \alpha_i n^i\ \end{pmatrix} = \begin{pmatrix}A(1)\ A(2)\ \vdots\ A(n) \end{pmatrix} = \begin{pmatrix}a_1\ a_2\ \vdots\ a_n \end{pmatrix} $$ 因此，范德蒙德矩陣將多項式的“係數表示”精確地映射到其“評估表示”。這最終與傅里葉變換密切相關。離散傅里葉變換可以寫成范德蒙德矩陣，而快速傅里葉變換可以解釋為范德蒙德矩陣是 Toeplitz（實際上是循環的），因此允許特別有效的表示和矩陣/向量乘法，但這是非歷史的.
所以，我們有一個（可逆）矩陣，它映射一個 $ n $ 多項式的維“係數向量”表示 $ n $ 多項式的維“評估向量”表示。目前，不要擔心所有人如何在所有股票中移動——只要確保你了解如何進行計算。
我們從“評估向量”表示開始 $ C(i) = A(i)B(i) $ 為了 $ i\in{1,\dots,n} $ ，我們可以寫成 $ \vec c = (c_1,\dots, c_n) $ . 我們通過以下方式將其轉換為“係數向量”表示 $ V^{-1}\vec{c} $ . 這給出了多項式的係數 $ C(x) = A(x)B(x) $ 作為向量。雖然有 $ n $ 係數，如該多項式之前所討論的（唯一地由 $ \vec{c} $ ) 是度數 $ 2t $ ，所以高階係數為 0。
我們可以將其轉換為度數 $ t $ 通過截斷多項式。讓： $$ P = \begin{pmatrix} I_{t+1} & 0\ 0 & 0\end{pmatrix} $$ 豆 $ n\times n $ 塊矩陣，其中 $ I_{t+1} $ 是個 $ (t+1)\times (t+1) $ 單位矩陣。然後 $ PV^{-1}\vec{c} $ 將“丟棄”高階係數，留下一個度數 $ t $ 多項式。重要的是，它不會觸及常數項（所以 $ \mathcal{C}(0) = C(0) = ab $ 被保留）。
剩下的就是轉換回份額，所以從“係數表示”轉換為“評估表示”，再次使用 $ V $ . 因此 $ VPV^{-1}\vec{c} $ 將輸出股份（程度 $ t $ 多項式）你想要的。而且， $ VPV^{-1} $ 可以由協議中的所有參與者預先計算（這只是一些 $ n\times n $ 矩陣。我什至可以在這裡寫出來，但不會）。
這將乘以份額的問題減少為“計算份額的線性方程”的問題，您的消息來源也討論了這個問題（在此連結上）。由於時間越來越長，我將把答案留在這裡，但如果您不理解線性案例，我鼓勵您提出一個新問題。