Shamir 的秘密共享計劃安全性的正式證明
Shamir 的秘密共享方案是完全安全的。
您能否建議我在哪裡可以閱讀 Shamir 的秘密共享方案完全安全的正式證明？
讓我們回憶一下沙米爾的秘密分享。我們在有限的領域工作 $ \mathbb{F}_q $ 紅衣主教 $ q $ . 分享的秘訣是 $ s $ ; 我們想要 $ n $ 有門檻的股份 $ t $ . 我們假設 $ n < q $ （否則，該方案不起作用）。我們通常命名 $ n $ 的非零值 $ \mathbb{F}_q $ : $ x_1 $ , $ x_2 $ … $ x_n $ . 我們究竟如何選擇它們並不重要，只要它們都與零和彼此不同，並且每個人都知道哪個是哪個。如果 $ q $ 是素數（場 $ \mathbb{F}_q $ 是 $ \mathbb{Z}_q $ ，即整數模素數 $ q $ )，那麼我們傳統上會選擇 $ x_i = i \bmod q $ （自從 $ n < q $ ，這行得通：沒有一個 $ x_i $ 為零，並且它們都彼此不同）。按照慣例，我還定義 $ x_0 = 0 $ （這將有助於我的符號）。
分享 $ s $ ，我們生成一個隨機多項式 $ A = \sum_{i=0}^{t-1} a_i X^i $ ， 在哪裡：
- $ a_0 = s $
- 對所有人 $ i = 1 $ 至 $ t-1 $ , $ a_i $ 是隨機且均勻地選擇的 $ \mathbb{F}_q $ （值得注意的是，每個 $ a_i $ 機率為零 $ 1/q $ ).
通過施工， $ A(0) = s $ . 每個使用者的份額 $ i $ 是 $ v_i = A(x_i) $ . 多項式 $ A $ 最多有學位 $ t-1 $ “ （程度 $ A $ 可能低於 $ t-1 $ 因為有可能 $ a_{t-1} = 0 $ ).
重建秘密， $ t $ 股東使用他們各自的股份重新計算多項式 $ A $ , 從而計算 $ A(0) $ ，這是秘密重建使用拉格朗日多項式。我現在假設用於重建的份額是 $ v_1 $ , $ v_2 $ ,… $ v_t $ （這簡化了符號，但由於傳統的命名 $ x_1 $ , $ x_2 $ …是任意的，這種假設不會降低普遍性）。我們定義拉格朗日多項式 $ L_i $ 作為次數的多項式 $ t-1 $ 這樣 $ L_i(x_i) = 1 $ ， 但 $ L_i(x_j) = 0 $ 對於任何 $ j \neq i $ （為了 $ 1\leq i,j\leq t $ ）。拉格朗日多項式計算如下： $$ L_i = \frac{\prod_{1\leq j\leq t, j\neq i}(X - x_j)}{\prod_{1\leq j\leq t, j\neq i}(x_i - x_j)} $$ 由於所有 $ x_j $ 彼此不同，分母必然不為零，因此除法有效；與 $ L_i(x_i) $ ，分子和分母最終是相同的產品，這 $ L_i(x_i) = 1 $ .
使用拉格朗日多項式，可以找到匹配的 $ A $ 有： $$ A = \sum_{i=1}^{t} v_i L_i $$ 自那時候起： $$ A(x_j) = \sum_{i=1}^{t} v_i L_i(x_j) = v_j $$
那 $ A $ 是唯一的解決方案可以用計數論證證明：有 $ q^t $ 可能的元組 $ (v_1, v_2,\cdots v_t) $ ( $ t $ 中的值 $ \mathbb{F}_q $ )，並且對於它們中的每一個，使用拉格朗日多項式進行重建會產生一個匹配多項式 $ A $ 最多學位 $ t-1 $ . 然而，只有 $ q^t $ 最多次數多項式 $ t-1 $ . 因此，每個元組不能有超過一個匹配多項式；否則，你會在某個時候用完多項式。
（事實上，一個多項式至多是一個更一般的結果 $ t-1 $ 由其值唯一定義 $ t $ 不同的輸入；這也適用於無限領域。一個特殊情況是 $ t = 2 $ ，這實際上意味著通過任何兩個不同的點，都恰好通過了一條線。用更多的代數證明了一般結果；對於有限域，上面的計數參數要簡單得多。）
請注意，秘密重建只對秘密感興趣 $ s = A(0) $ ; 擁有完整的多項式只是一個平均值，並不是完全必要的。事實上，我們有： $$ s = A(0) = \sum_{i=1}^{t} v_i L_i(0) $$ 價值 $ L_i(0) $ 取決於涉及哪些股東（即選擇 $ x_1 $ , $ x_2 $ … $ x_t $ )，但不是股票價值 ( $ v_1 $ , $ v_2 $ … $ v_t $ ）。就這樣 $ L_i(0) $ 可以預先計算。這在對同一股東進行多次重組時特別方便；一個典型的案例是使用 $ q = 256 $ （具有正好 256 個元素的有限域）並在多字節秘密值上逐字節應用 Shamir 的秘密共享。
該方案的安全性取決於以下結果：對於任何一組 $ t $ 中的值 $ \mathbb{F}_q $ ，只有一個匹配多項式 $ A $ .
為了簡化符號，我現在假設您有股份 $ v_1 $ , $ v_2 $ … $ v_{t-1} $ . 這些是 $ t-1 $ 份額，即低於門檻值。為了證明方案的絕對安全性，我們需要證明這些 $ t-1 $ 股票不會產生任何關於秘密的資訊 $ s $ . 為此，我們注意到： $$ s = A(0) = \sum_{i=1}^{t} v_i L_i(0) $$ 所以： $$ v_t L_t(0) = s - \sum_{i=1}^{t-1} v_i L_i(0) $$ 另請注意 $ L_t(0) \neq 0 $ : $$ L_t(0) = \frac{\prod_{1\leq j\leq t-1}(0 - x_j)}{\prod_{1\leq j\leq t-1}(x_i - x_j)} $$ （所有 $ x_j $ 和所有的 $ x_i-x_j $ 是非零的，所以產品是非零的。）
因此，給定股票價值 $ v_1 $ 至 $ v_{t-1} $ , 對於任何可能的值 $ s $ , 缺失份額只有一個值 $ v_t $ 這將產生 $ s $ . 就這樣 $ t-1 $ 分享 $ v_1 $ 至 $ v_{t-1} $ 根本不產生任何關於秘密的資訊，因為在那個時候秘密的所有可能值仍然是可能的和等機率的。
請注意這里關於“等機率”的微妙之處。計數論證說有 $ q^{t-1} $ 多項式 $ A $ 最多學位 $ t-1 $ 這樣 $ A(0) = s $ , 對於給定的秘密 $ s $ . 和 $ t-1 $ 分享，即知識 $ t-1 $ 價值觀 $ v_i = A(x_i) $ ，你沒有足夠的知識來精確定位一個多項式 $ A $ ; 事實上，你有 $ q $ 匹配多項式，一個對應於每個可能的秘密值 $ s $ . 這在秘密的可能值之間建立了雙射 $ s $ ，以及缺失份額的可能值 $ v_t $ （上面的公式使雙射明確）。雙射傳輸資訊：您可能在秘密中知道的每條資訊，甚至是統計資訊 $ s $ , 可以通過雙射轉化為缺失共享的相同資訊 $ v_t $ ， 然後回來。這確實意味著 $ t-1 $ 分享，他們自己，教你什麼。現實生活中的秘密價值觀 $ s $ 不是完全隨機和統一的，但這不是重點；關鍵是沒有失去的份額 $ v_t $ , 你不知道更多 $ s $ 比你之前已經知道的要多。這就是沙米爾的秘密分享是無條件安全的意義。
一些額外的說明：
- 所有這些都取決於初始共享多項式的想法 $ A $ 是真正隨機且均勻地選擇的。在實踐中，這並不容易實現：“真正的”隨機性是難以捉摸的。我們通常使用偽隨機生成器將給定的種子（假定為“隨機”）擴展為與隨機性無法區分的任意長字節序列……只要攻擊者擁有不超過給定值的有限計算資源。此外，“種子”本身是從一些被認為是不可預測的物理過程中獲得的，但這也假設攻擊者從物理世界獲取資訊的能力受到限制。因此，沙米爾方案的“無條件”安全性實際上取決於許多其他事情。
（物理學家告訴我們，任何物理系統的狀態都存在根本的不確定性，但沒有多少所謂的“隨機發生器”真正利用這一點。此外，從認識論的角度來看，使用量子不確定性驅動的 RNG 並不是比密碼安全的 PRNG“更強大”；您只是對 Niels Bohr 的信任比對 Alan Turing 的信任更多。）
- 該方案的安全性取決於多項式 $ A $ 是一次性的。如果您使用該方案對多字節秘密值進行逐字節共享，那麼您必須生成一個新的隨機多項式 $ A $ 對於要拆分為共享的每個字節。如果你重複使用相同的 $ A $ 幾個字節，那麼所有的安全都化為烏有。
- 一個實際的實現可以通過不生成係數來利用共享元組和多項式之間的雙射 $ a_i $ 隨機; 相反，它會生成第一個 $ t-1 $ 隨機均勻共享，然後計算共享 $ v_t $ , $ v_{t+1} $ ,… $ v_n $ 使用上述公式，其中 $ L_i(0) $ 值可以預先計算（甚至在實現原始碼中硬編碼）。雙射保證這是安全的。