是否有基於 XOR 的有效三分之二的秘密共享方案？
我想知道是否存在基於 XOR 的有效秘密共享方案，以便將消息的一部分提供給三個人，並且至少兩個人必須合併他們的份額才能構造消息？
到目前為止我已經嘗試過：
假設我收到一條消息 $ M $ ，還有A、B、C三個人。那我做的是
- 一個得到 $ a_1 = M \oplus \alpha $ 和 $ a_2 = \beta $
- B 得到 $ b_1 = M \oplus \beta $ 和 $ b_2 = \alpha $
- C 得到 $ c_1 = \alpha $ 和 $ c_2 = \beta $
在哪裡 $ \alpha $ 和 $ \beta $ 是消息大小的兩個隨機生成的位。
這很好用（有一些修改），但問題是每個人都必須儲存兩倍大小的消息。有沒有更高效的？
假設消息是 $ \ell $ 有點長，我們將在伽羅瓦領域工作 $ \operatorname{GF}(2^\ell) $ 其中加法是異或。如果 Alice、Bob 和 Charlie事先就生成器達成一致 $ \alpha \in \operatorname{GF}(2^\ell) $ （或至少一個大於 3 的元素），那麼我們可以選擇 $ u $ 均勻隨機分配給他們股份 $ (1, m + u \alpha) $ , $ (2, m + u \alpha^2) $ ， 和 $ (3, m + u \alpha^3) $ . 也就是各方商店 $ (i, f(\alpha^i)) $ 在哪裡 $ f(x) = m + u x $ ; 給定兩股 $ s_i = m + u \alpha^i $ 和 $ s_j = m + u \alpha^j $ 為了 $ i \ne j $ , 很容易恢復$$ m = s_i - \frac{s_i - s_j}{\alpha^i - \alpha^j} \alpha^i = s_j - \frac{s_i - s_j}{\alpha^i - \alpha^j} \alpha^j $$從線上的兩點 $ f $ .
這是 Shamir 的 2-of-3 秘密共享方案$$ 1 $$（免費）。每方儲存是一個小整數加上一個 $ \ell $ 位共享。當然，各方都必須事先就發電機達成一致 $ \alpha $ ，但無論如何，他們也必須就其餘的計算達成一致。一般來說， Shamir 的每方儲存成本 $ t $ -的- $ n $ 秘密共享方案是 $ \ell + \lceil\log_2 t\rceil $ . 這個成本接近資訊論的下限 $ \ell $ 位。
但是我們可以使用密碼學來降低成本。以機智$$ 2 $$:
- 加密消息 $ m $ 在秘鑰下 $ k $ 給出密文 $ c $ .
- 將密文拆分為共享 $ c_1, c_2, \dots, c_n $ 其中任何一個 $ t $ 足以重構 $ c $ 使用糾刪碼，如 Reed-Solomon 碼或 Rabin 的資訊傳播算法，這種算法很有效，但不會向對手隱瞞任何事情。
- 將密鑰拆分為共享 $ k_1, k_2, \dots, k_n $ 其中任何一個 $ t $ 足以重構 $ k $ 使用秘密共享，例如 Shamir 的秘密共享方案，這種方案效率低下，但對任何少於 $ t $ 分享。
如果密文是 $ \ell $ 位長（如果您簽署它以阻止惡意方破壞其共享，則說明可能的密文擴展）並且密鑰是 $ \lambda $ 位長，每方儲存是 $ \ell - \lfloor\log_2 t\rfloor + \lambda $ 位。我們通過使用擦除編碼而不是秘密共享在多方之間拆分消息來節省空間，但我們必須通過對密鑰進行秘密共享來彌補它。
最後，請注意，秘密共享總是會帶來一個實際問題：當您第一次建構股份時，經銷商必須將整個秘密放在一個地方開始，並且每次您要重建股份時，行事的一方重建總是必須將全部秘密放在一個地方。多方計算（如門檻值簽名）更好地服務於許多應用程序，其中任何一方都無法在任何時候單方面訪問整個秘密。