Secret-Sharing

確定以下問題的 Shamir 秘密共享方案

  • January 8, 2018

對於以下問題,我無法解決 Shamir 的秘密共享方案:

問題:某軍事辦公室控制著一枚威力強大的導彈,由六名將軍、五名上校和四名文員組成。描述他們將如何制定一個沙米爾計劃,以便任何五名將軍或任何四名上校和三名服務員或任何三名將軍和三名服務員都可以發射導彈。

我在想這看起來像 Shamir 的方案定義,其中秘密 S 被分為三組( $ n=3 $ ? ),所以我需要描述獲取門檻值方案的過程 $ (k, n) $ , 這 $ k $ 給定問題的份額?或者只是讓自己更加困惑。解決這個問題的任何幫助都會有所幫助。

每個人可能被分配一個以上的秘密。

讓 $ G $ , $ C $ 和 $ D $ 分別表示分配給將軍上校秘書的股份數量,並讓 $ T $ 表示秘密共享方案的值。然後,我們有

$$ \begin{align} T &\leq 5G,\ T &\leq 4C + 3D,\ T &\leq 3G + 3D. \end{align} $$ 你能找到合適的值嗎 $ G,C,D $ ,和 $ T $ ? 總股數為 $ N = 6G + 5C + 4D $ 我們有一個 $ (T,N) $ 秘密共享方案。

$ D=2, C=3, G=4, T=18 $ , 和 $ N = 47 $ 似乎工作。當然,還有其他組合會導致 $ 18 $ 或更多股份,例如, $ 5C+2D $ 或者 $ 4G+D $ 但問題陳述中沒有任何內容表明這是不允許的。請注意, $ 5 $ 上校(或 $ 4 $ 服務台文員)不能自己發動政變;上校必須至少有兩名服務員(或一名將軍)作為同謀。

附錄:本著@IlmariKaronen 的回答精神,

  • 分割秘密 $ S $ 分成6股 $ (5,6) $ 秘密分享計劃,讓六名將軍各分一杯羹。其中任何5個都可以重建 $ S $ .
  • 創建一個隨機二進制向量 $ X $ 只要秘密 $ S $ ,然後做五股 $ S\oplus X $ 在一個 $ (4,5) $ 秘密分享計劃,給每個上校一份。他們中的任何四個都可以重建 $ S\oplus X $ . 創造 $ 4 $ 的股份 $ X $ 在一個 $ (3,4) $ 秘密分享計劃,並將一份分享給每個服務員。任何 $ 3 $ 服務台文員可以重建 $ X $ ,並與 $ S\oplus X $ 來自 $ 4 $ 上校, $ S $ 可以重建。
  • 創造 $ 6 $ 的股份 $ S\oplus X $ 在一個 $ (3,6) $ 秘密分享計劃,並將一份分享給每個將軍。任意三個將軍都可以重構 $ S\oplus X $ ,並與 $ X $ 從三個服務員,可以重新創建 $ S $ .

請注意,與 Ilmari 的方法相比,此方法實施的秘密共享計劃更少,而且辦公桌文員和上校只有一份可以擁有和持有。只有將軍有兩種不同的股份,當他們自己行動和與三個服務員一起行動時,必須記住在兩種不同的情況下使用正確的一種。此外,服務台文員自己只能重建 $ X $ .

引用自:https://crypto.stackexchange.com/questions/53449