沒有經銷商的 Shamir 秘密分享

假設我們有一組 $ N $ 派對。我正在尋找一種生成隨機秘密份額的方案 $ s $ 其中任何大小的參與者子集 $ k $ 可以恢復類似於沙米爾計劃的秘密。此外，集團以外的任何一方，例如經銷商，都無法訪問 $ s $ .

我認為這可以通過任何附加秘密共享方案（Shamir 的方案）相對簡單地完成。該方案背後的基本思想（製作一個 $ (n, k) $ 無經銷商秘密共享方案）是：

1. 每一方都採樣一個統一的隨機值 $ s_i\in\mathbb{F}_p $
2. 各方使 $ n $ 該值的份額（使用添加劑 $ (n, k) $ 秘密共享方案），我們稱之為 $ {s_{i, j}} $ 為了 $ j\in[n] $
3. 對所有人 $ (i, j)\in[n]^2 $ ， 聚會 $ i $ 發送 $ s_{i, j} $ 聚會 $ j $ .
4. 對所有人 $ i\in[n] $ ， 派對 $ i $ 套 $ s_i’ = \sum_{j\in[n]}s_{i, j} $
5. 所有各方都留下了共享 $ s’ = \sum_{i \in[n]} s_i $

為什麼這應該是安全的想法（達到門檻值 $ k $ ) 是對手可以做三件事：

1. 選擇 $ s_i $ 不均勻（並且在 $ k-1 $ 各方，以某種方式選擇他們依賴）
2. 發送“不正確”的秘密分享
3. 計算 $ s_i’ $ 錯誤地

前兩點可以看作是等價的，因為發送“不正確”的共享與發送錯誤採樣秘密的正確共享是一樣的。如果你知道一群誠實的人會重建秘密，這些錯誤採樣的秘密就不會成為問題（總和 $ s’ = \sum_{i\in[n]}s_i $ 將均勻分佈，只要任何 $ s_i $ 是單獨均勻分佈的，所有其他秘密都與這個值無關）。

我不知道上述內容對重建過程中的損壞有多大的容忍度，但這似乎不是你要問的。我想它與“基本”附加秘密共享方案大致一樣寬容，但沒有現成的論據（因此將省略這一點，同時提到這是一件有趣的事情）。

這也具有相對較高的通信複雜度（ $ O(n^2) $ 在分享過程中——感覺就像 $ O(nk) $ 可能是可能的，但我現在不想過度優化它），並且只能在欄位上採樣秘密 $ \mathbb{F}_p $ Shamir’s 是安全的（所以你必須採取 $ p $ 呈指數級增長，因此如果您只需要商定一個“小”秘密，那麼它會浪費通信量（而不僅僅是消息數量），這對我來說似乎是它的主要“缺點” .

引用自：https://crypto.stackexchange.com/questions/84143