如何使用秘密共享為任意單調訪問結構分配共享
考慮4個人， $ A $ , $ B $ , $ C $ , $ D $ , & 一個秘密 $ s\in{0,1}^k $ . 建構一個方案，使以下人的子集能夠檢索秘密 $ {A,B} $ , $ {A,C} $ , $ {B,C,D} $ .
我知道我們可以使用 Shamir 的秘密共享方案來做到這一點，並且 A 應該比其他人分配更多的份額。但是，當給定任意單調訪問結構時，我們如何進行分配呢？
我將首先觀察並非每個單調訪問結構都可以通過以下方式實現 $ (t,n) $ 門檻值秘密共享（這裡我們需要 $ t $ 出 $ n $ 股票需要可用於重建）。
首先讓我們定義一個單調訪問結構。讓 $ P $ 成為一組參與者。訪問結構 $ \Gamma $ 是冪集的非空子集的集合 $ 2^P $ . 這種結構稱為單調，如果 $ X\in \Gamma $ 暗示 $ Y\in \Gamma $ 對於所有超集 $ Y\supseteq X $ .
請注意，在秘密共享的上下文中定義單調訪問結構非常有意義，因為訪問結構中的每個集合都可以重建秘密，因此包含該集合的每個超集都可以輕鬆做到這一點。
Shamir 沒有提供通用的解決方案
讓我們建構一個門檻值秘密共享的反例：
考慮一組參與者 $ P={A,B,C,D} $ 和單調的訪問結構 $ \Gamma={{A,B},{C,D}} $ . 我們假設我們使用一個 $ (t,4) $ 共享秘密的門檻值方案 $ k $ 在參與者中 $ A,B,C,D $ 和 $ k $ 只能由作為元素的子集重建 $ \Gamma $ .
現在讓 $ a,b,c $ 和 $ d $
是分配給使用者的份額的權重 $ P $ . 那麼它必須持有 $ a+b\geq t $ 和 $ c+d \geq t $ ， 在哪裡 $ t $ 是門檻值。WLOG讓 $ a\geq b $ 和 $ c \geq d $ . 自從
- $ a+b\geq t $ 和 $ a\geq b $ 我們有 $ a+a\geq a+b \geq t $ 這給出了 $ a\geq t/2 $ .
- 此外，由於 $ c+d\geq t $ 和 $ c\geq d $ 它遵循 $ c\geq t/2 $ .
這意味著 $ a+c \geq t $ 因此 $ A $ 和 $ C $ 能夠重建 $ k $ ， 但 $ {A,C}\notin \Gamma $ .
單調訪問結構的秘密共享
好的，現在我們繼續實現通用單調訪問結構的秘密共享。讓 $ P={P_1,\ldots,P_n} $ 成為參與者的集合。我們首先需要一些定義：
**最小授權子集：**讓 $ \Gamma $ 然後是一個訪問結構 $ {\cal C}\in \Gamma $ 是最小授權子集，如果 $ H \notin \Gamma $ 每當 $ H\subset {\cal C} $ （即，每當我們刪除參與者時，該集合將不再被授權）。
現在我們稱與 $ \Gamma $ 一個基礎，並表示為 $ \Gamma_0 $ . 以後使用基礎就足夠了（如 $ \Gamma $ 可以通過取閉包來獲得，即通過單調性）。
如果我們看一個 $ (t,n) $ 門檻值方案，那麼我們有 $ \Gamma = {G \subseteq P : |G|\geq k} $
和 $ \Gamma_0 = {G \subseteq P : |G| = k} $ .**最大未授權子集：**讓 $ \Gamma $ 是一個訪問結構並呼叫 $ M={{\cal B}_1,\ldots,{\cal B}_m} $ 最大未經授權子集 的集合，如果對於每個 $ {\cal B}_i $ 持有： $ {\cal B}_i\notin \Gamma $ 和 $ {\cal B}_i\cup P_j\in \Gamma $ 對於每個 $ P_j\notin {\cal B}_i $ （即，每當我們選擇尚未包含的參與者時，我們將獲得授權集）
現在我們可以定義訪問結構的雙重表示 $ \Gamma $ 表示為 $ \Gamma^* $ .
我們可以寫一個訪問結構 $ \Gamma = \bigvee_{{\cal B}\in \Gamma} \bigwedge_{P_i\in \cal B} P_i $ 或作為產品的總和（將連詞替換為 $ \cdot $ 和析取 $ + $ ).
然後通過交換運算符得到雙重訪問結構，即 $ \Gamma^* = \bigwedge_{{\cal B}\in \Gamma} \bigvee_{P_i\in \cal B} P_i $ （或作為總和的乘積）。
我們有以下內容：讓 $ \Gamma $ 是一個訪問結構 $ P $ 和 $ M={{\cal B}_1,\ldots,{\cal B}_m} $ 最大未授權子集的集合，則 $ \Gamma_0^*={{\cal A}_1,\ldots,{\cal A}_m} $ 這樣 $ {\cal B}_i=P\setminus {\cal A}_i $
是對偶形式的最小授權子集的集合。好的，讓我們在素數域上進行加法完美秘密共享 $ Z_p $ ，即秘密 $ k $ 被代表 $ k=\sum_{i=1}^m s_i \pmod p $ 對於隨機 $ s_i $ .
然後我們可以得出以下矩陣，我們有 $ b_{i,j}=1 $ 如果 $ P_i\in {\cal A_j} $ 和 $ b_{i,j}=0 $ 除此以外。
現在，我們可以分配股票 $ s_1,\ldots,s_m $ 通過以下方式。每個使用者 $ P_i $ 獲得股份集合 $ S_i={s_j: b_{i,j}=1} $ （即，如果參與者出現在相應的對偶基集合中，則參與者獲得份額，或者等效地，如果參與者出現在最大未授權子集的相應集合中，則不獲得份額）。
今天我不會再舉一個明確的例子了。但是這種秘密共享使每個授權的子集 $ \Gamma $ 重建秘密 $ k $ 並且任何非授權集都將無法這樣做。
