基於Shamir的低效訪問結構的資訊理論安全
我研究了 Sharmir 的方案以及 M. Ito 提出的多重分配方案。我的問題是，是否有人可以告訴我以下方案在理論上是否安全：
條款：
P = 參與者集
B = 訪問結構
A = 訪問集（訪問結構內的授權集）
t = Access 結構的基數 ( |B| )
d = 訪問集的基數 ( |A| )
S = 秘密
因此該方案效率極低，因為它涉及創建恰好t個不同 ( d,d ) 的 Shamir 方案，因此將有t個不同的隨機選擇的多項式，它們都共享相同的秘密s
編輯：
所以該方案是一個訪問結構秘密共享方案，基本上它定義了一組參與者的某些子組，這些子組是有效的，因此可以重建一個秘密。
例如，如果有一組人 p1,p2,p3 和 {p1p2, p1p3} 的訪問結構，那麼只有 p1 和 p2 或 p1 和 p3 的組合才能發現秘密。所以 p1p2 和 p1p3 是有效的子組，而 p2p3 是無效的子組，因此應該無法發現秘密。
如果無效組可以發現任何資訊，則該方案理論上是不安全的。這包括發現或計算一個不是 S（秘密）的數字並知道該數字不是秘密。因此，如果 p2p3 計算他們的份額並找到一個他們知道不是秘密的數字 S’，那麼該方案是不安全的！
例子：
令S = 6, P = {P1,P2,P3}, B = {P1-P2,P1-P3) 使得 P1 和 P2 可以像 P1 和 P3 一樣找到秘密
現在我們生成 2 個具有相同秘密的 shamir 方案：
f1(x) = 6 + 4x
f2(x) = 6 + 7x
所以我們需要每個方案的兩個份額：
s1, s2 = (1,10) 和 (2,14)
s'1, s'2 = (1,13) 和 (2,20)
P1 得到s1和s'2
P2 得到s2
P3 獲得s'2
誰能想到這個方案在理論上不安全的任何原因，它的效率非常低，但據我所知它是安全的，我只是不知道如何證明或反駁它。
非常感謝
是的，您的方案非常正確和安全。這源於以下事實：
- Shamir 的秘密共享是正確的：任何至少具有門檻值共享數量的參與者組都可以可靠地重建秘密；和
- Shamir 的秘密共享是完全安全的：共享數量低於門檻值的任何一組參與者都無法了解有關秘密的任何資訊。
由於您的子方案是獨立建構的，除了具有相同的秘密之外，從一個子方案中學到的知識可以幫助打破另一個子方案的唯一方法是，如果該知識以某種方式涉及秘密。但是，由於 Shamir 的秘密共享通過建構，在沒有訪問門檻值共享數量的情況下不會透露有關秘密的資訊，因此這是不可能的。
另一種表明這一點的方法是假設一個組對於每個子方案已經擁有比該子方案的門檻值數量少一個的訪問權限。（我們可以在不失一般性的情況下做到這一點，因為讓攻擊者訪問更多共享永遠不會損害他們恢復秘密的機會。）然後證明，對於任何可能的秘密值，每個子方案都存在唯一的失去共享分配這將重建那個秘密。（這基本上是基本 Shamir 秘密共享安全性的標准證明，只需使用多組共享和多項式。）
另請注意，由於您的子方案總是 $ (n,n) $ 方案（即它們總是需要所有共享來重建秘密），您實際上並不需要 Shamir 方案的全部功能。特別是，瑣碎的秘密共享，例如基於 XOR 或模加法，也可以正常工作。