RS Erasure Coding 和 Shamir 的秘密分享
所以我試圖理解糾刪碼和秘密共享之間的基本區別，我找到了這篇論文（你可以在這里或這裡找到）。
據我了解，它指出沙米爾的秘密分享基本上是里德-所羅門密碼的一個特定實例；
但是，從安全的角度來看，我無法真正理解任何 RS 程式碼和 SS 編碼之間的區別。
想像一下，我有一個 RS 程式碼 (m,n) 和一個要編碼的數據塊。對數據進行編碼後，我將擁有 n 個塊，如果我想重建數據，我至少需要 m 個數據，對吧？
這與 Shamir 的秘密共享 (m,n) 實例有何不同，我需要 n 中的 m 個共享來重建秘密？它們是完全等效的，還是 SS 更安全？
我承認對這兩者如何工作的詳細技術/數學方面真的一無所知，我對實際的觀點更感興趣。
Shamir 的 (m,n) 秘密共享方案有一個秘密 $ s_0 $ 表示為有限域的一個元素 $ \mathbb F_q $ 的 $ q $ 元素。還有 $ m-1 $ 其他“隨機選擇”的元素 $ s_1, s_2, \ldots, s_{m-1} $ 設計師使用的。該方案創建一個多項式
$$ S(x) = s_0 + s_1x + \cdots + s_{m-1}x^{m-1} $$並評估 $ S(x) $ 在 $ n $
不同的非零 元素 $ \alpha_1, \alpha_2, \ldots, \alpha_n $ . 注意 $ n $ 必須至少與 $ m $ 並且不能大於 $ q-1 $ . 這 $ n $ 分發給共享秘密的人的秘密就是這些多項式值 $ S(\alpha_1), S(\alpha_2), \ldots, S(\alpha_n) $ . 給定 $ m $ 的 $ n $ 股，拉格朗日插值公式給出了唯一的多項式 $ T(x) $ 學位 $ m-1 $ 或更少通過這些插值 $ m $ 點，即每份 $ [\alpha_j, S(\alpha_j)] $ 可用於重構器， $ T(\alpha_j) $ 等於股票價值 $ S(\alpha_j) $ . 所以， $ T(x)-S(x) $ 是一個多項式 $ m-1 $ 或更少 $ m $ 根在該領域，並且根據代數基本定理，必須為零。因此， $ T(0) = s_0 $ 是秘密。如果 $ m $ 共享可用，秘密可以恢復。
如果超過 $ m $ 股票是可用的，任何 $ m $ 其中的一個可以用來重建秘密。Shamir 還表明，如果小於 $ m $ 共享可用，則無法恢復秘密；事實上，所有可能 $ q $ 如果一個人插值小於 $ m $ 分享。
通過 Reed-Solomon 碼對該方案的 McEliece-Sarwate 推廣有兩個方面。
- 首先，通過使用糾錯由於 Reed-Solomon 碼的特性，即使某些共享錯誤，也可以恢復秘密。在這裡，錯誤意味著股東送出的股票價值與給予他/她的價值不同。此類錯誤可能是出於惡意，也可能是由於意外（例如，保存共享的快閃記憶體驅動器被遺忘在口袋中並在洗衣機中清洗）。在標準的 Shamir 重建中，損壞的份額與有效份額沒有什麼不同，拉格朗日插值幾乎總是會重建一個與原始份額不同的“秘密”。除非秘密中內置了錯誤控制（例如 CRC 校驗和），否則無法知道恢復的“秘密”與原始的不同。另一方面，里德-所羅門碼的性質表明，如果 $ m+t $ 最多可用的股票 $ \lfloor t/2\rfloor $ 是錯誤的，那麼通過使用 Reed-Solomon 解碼算法，可以成功恢復秘密。重構器不需要知道哪些共享是錯誤的（如果知道，則可以忽略損壞的共享！）。解碼算法還指示哪些共享（如果有） $ m+t $ 送出的份額是錯誤的，也就是說，可以辨識作弊者（或洗錢者！），當然可以計算正確的份額值並將其提供給新快閃記憶體驅動器上的無辜股東。如果超過 $ \lfloor t/2\rfloor $ 如果共享錯誤，Reed-Solomon 解碼算法很可能會拒絕重建秘密，並且只會在極少數情況下重建與原始“秘密”不同的“秘密”。請注意，無法重建秘密並不是致命的（除非 $ m+t = n $ ) 因為人們總是可以等待送出更多有效份額，以便克服無效份額的影響。在這種形式下，Shamir 方案和 Reed-Solomon 編碼方案的安全性沒有區別。
- McEliece-Sarwate 論文中考慮的 Reed-Solomon 編碼方案的第二個方面是不需要填寫 $ S(x) $ 和 $ m-1 $ 隨機選擇的符號。其實秘密可以是全部 $ m $ 符號 $ s_0,\ldots,s_{m-1} $ 而不僅僅是 $ s_0 $ 成為秘密。一個優點是我們可以使用更小的有限域。如果秘密是 $ 1000 $ 位，說，和 $ m=10 $ , Shamir 的計劃將在 $ \mathbb F_{2^{1000}} $ 並且秘密的每一部分也將是 $ 1000 $ 位長。 $ 10 $ 千比特 ( $ 10 $ 一千比特份額）將需要恢復秘密。另一方面，Reed-Solomon 編碼方案可以將秘密分為 $ 10 $ $ 100 $ -位符號和操作 $ \mathbb F_{2^{100}} $ . 每一股也將是 $ 100 $ 比特長，和以前一樣，只需要十個這樣的短份額來恢復秘密。欄位大小的這種減少確實以安全性為代價。要是 $ 9 $ 股份可供陰謀集團使用，他們猜測所需股份的十分之一的可能值，他們可以提出一個“短名單”，只有 $ 2^{100} $ 的值 $ 1000 $ 位秘密可能有。在類似的困境中，沙米爾的計劃將有一個列表 $ 2^{1000} $ 秘密的可能值，從而提供完美的安全性。降低安全性和易於實施以及儲存每個秘密共享之間的權衡是需要針對每個應用程序進行評估的事情。最安全的方案具有與秘密一樣長的共享，而 Reed-Solomon 方案可用於以降低安全性為代價來減小共享大小。
編輯另一個版本的秘密共享提供了 $ i $ -第股東的價值 $ \alpha_i $ 以及份額 $ S(\alpha_i) $ （這需要兩倍的儲存空間）。因此， $ m $ 如果股東知道拉格朗日插值並且可以訪問執行所需有限域算術的電腦，而其他任何人都不知道，他們就可以重建這個秘密。在標準場景中， $ i $ -th 股東只有 $ S(\alpha_i) $ 在沒有任何知識的情況下 $ \alpha_i $ ，只有官方的重建者知道喬布洛是 $ i $ -th 股東和查找 $ \alpha_i $ 當喬出於重建目的送出他的份額時。在這種情況下，秘密重建只能由官方重建者進行；一個陰謀集團 $ m $ 叛逆的股東不能私下重建秘密並用它來推翻邪惡帝國。當股東實際擁有 $ [\alpha_i,S(\alpha_i)] $ ，作弊者可以改變數量或兩者，無辜的錯誤也可能這樣做。這個問題的解決方法比較困難。對於在這種情況下可以做什麼，例如，請參見此處。