反向沙米爾的秘密分享算法？
Shamir 的秘密共享算法通過將單個秘密分解為多個部分來工作。雖然在 $ n $ -在……之外- $ n $ 方案，如何實施 $ m $ -在……之外- $ n $ 計劃是 $ k $ 預定義共享 $ (k < m) $ 是否包含在共享池中？
很明顯，由此產生的秘密將是隨機的但確定性派生的。
讓我們先回顧一下沙米爾的秘密分享的正常構造：
我們在有限的領域工作 $ \mathbb{K} $ . 這通常是 $ \mathbb{F}{256} $ （具有 256 個元素的二進製欄位），因此可以方便地在每個字節的基礎上進行共享。我們想要一個 $ m $ -在……之外- $ n $ 方案，所以有限域必須至少有 $ n+1 $ 元素。對於要共享的每個值，一個隨機多項式 $ P \in \mathbb{K}[X] $ 最多學位 $ m-1 $ ： 我們寫 $ P = \sum{i=1}^{m-1} p_i X^i $ 在哪裡 $ p_i $ 是隨機且均勻地選擇的 $ \mathbb{K} $ ， 除了 $ p_0 $ ，我們將其設置為要共享的秘密值。
因此， $ P(0) = p_0 $ 是秘密值。“股份”是 $ P(v_1) $ , $ P(v_2) $ … $ P(v_n) $ , 其中 $ v_j $ 值是 $ n $ 的不同非零元素 $ \mathbb{K} $ ，通過固定的公共約定任意選擇（確切使用哪個約定無關緊要）。
從 $ m $ 分享，我們真的重建了多項式 $ P $ ，使用拉格朗日多項式。讓 $ N_i \in \mathbb{K}[X] $ 為以下多項式：
$$ N_i = \left(\prod_{1\leq j\leq n, j\neq i} (X - v_j) \right) $$ 很容易看出 $ N_i(v_j) = 0 $ 對於任何 $ j \neq i $ ， 但 $ N_i(v_i) \neq 0 $ . 因此，我們定義了拉格朗日多項式 $ L_i = N_i / N_i(v_i) $ ; 它有價值 $ 1 $ 上 $ v_i $ ， 和 $ 0 $ 在所有其他 $ v_j $ . 然後， $ P $ 被重構為拉格朗日多項式的線性組合。如果我們有股票 $ P(v_1) $ , $ P(v_2) $ ,… $ P(v_m) $ ，那麼我們可以寫：
$$ P = \sum_{i=1}^{m} P(v_i) L_i $$ 因此，秘訣是： $$ p_0 = P(0) = \sum_{i=1}^{m} P(v_i) L_i(0) $$ 在實際實現中，係數 $ L_i(0) $ 將被預先計算，並且重建不需要實際重建多項式 $ P $ ; 它只是重新計算秘密 $ p_0 $ 作為股份的線性組合 $ p_i $ .
**現在，讓我們檢查手頭的問題：**你有 $ k $ 預定義的“共享”並希望在秘密共享中使用它們。為此，您只需應用上面的重建，並在需要時使用新的隨機值。換句話說，您首先聲明多項式 $ P $ 確實存在，而且 $ k $ 預定義的份額是 $ P(v_1) $ , $ P(v_2) $ ,… $ P(v_k) $ . 然後，您隨機且均勻地生成 $ m-k-1 $ 額外的股份，你稱之為 $ P(v_{k+1}) $ , $ P(v_{k+2}) $ ,… $ P(v_{m-1}) $ . 最後，您定義您的秘密值是 $ P(0) $ . 在這一點上，你有評估 $ P $ 正好在 $ m $ 值（ $ 0 $ , 和非零元素 $ v_1 $ 至 $ v_{m-1} $ ）。然後，您為一組值定義新的拉格朗日多項式，其中包括 $ 0 $ :
$$ \begin{eqnarray*} N’0 &=& \prod{1\leq j\leq m-1} (X - v_j) \ N’i &=& X \prod{1\leq j\leq m-1, j\neq i} (X - v_j) \ L’_0 &=& N’_0 / N’_0(0) \ L’_i &=& N’_i / N’_i(0) \ \end{eqnarray*} $$ 這時候，你可以找到 $ P $ : $$ P = P(0) L’0 + \sum{i=1}^{m-1} P(v_i) L’_i $$ 這裡發生的是你重建了一個多項式 $ P $ 與您的預定義份額和目標秘密值相匹配；您還生成了新的隨機份額，以便有足夠的價值來製作獨特的候選人 $ P $ . 現在你有了多項式 $ P $ ，您可以計算盡可能多的額外份額 $ P(v_i) $ （為了 $ i\geq m $ ) 根據需要。
一些額外的說明：
- 如果 $ k < m $ ，您仍然可以選擇秘密值，如上圖所示。它不需要是“隨機的”。如果您不想選擇共享密鑰，您可以簡單地創建 $ m-k $ 額外股份（而不是 $ m-k-1 $ ) 並使用正常的拉格朗日插值得到 $ P $ ，此時您可以獲得 $ P(0) $ 作為共享秘密。對於所有輸入值，計算始終有效（確實，這就是該方案的安全性）。如果您從確切開始，也會出現這種情況 $ m $ 預定義份額：如果你想要一個門檻值 $ m $ 並且已經有了 $ m $ 股的話，就沒有選擇秘籍的餘地了。
- 在上述所有內容中，我使用了 $ P(0) $ 秘密，但這純粹是傳統的。 $ 0 $ 這裡並不特別。拉格朗日插值的要點是，對於任何一組值 $ P(v_i) $ 上 $ m $ 不同的欄位元素 $ v_i $ , 存在唯一匹配多項式 $ P $ 學位小於 $ m $ （即可以表示為的多項式 $ m $ 係數）。