線性秘密共享方案中的重構向量
假設我們有一個政策 $ A \wedge ( D \vee (B \wedge C)) $ 有屬性 $ {{A,B,C,D}} $ . 滿足該策略的屬性子集是 $ {{{{A,D}},{{A,B,C}},{{A,B,D}},{{A,C,D}}}} $ 其中 $ {{{{A,D}},{{A,B,C}}}} $ 是最小子集的集合。
我們將上面的布爾公式轉換成一個 LSSS 矩陣 $ L = {{{{1,1,0}},{{0,-1,1}},{{0,0,-1}},{{0,-1,0}}}} $ 根據此（第 30 頁）。
我們通常會找到一個向量 $ g $ 這樣 $ g^T \cdot L = (1,0,0) $ 對於所有此類授權子集，使得 $ \forall i \in [4], (g_i = 0) \vee (g \in Attr) $ .
如果我理解正確，假設使用者具有屬性 $ Attr ={{A,D}} $ . 這意味著在這種情況下他的輸入向量將是 $ V = (1,0,0,1) $ . 由於他沒有 $ B,C $ 那些 $ g_i $ s（假屬性）將被分配 $ 0 $ 然後我們求解未知方程 $ g = (x_1,0,0,x_2) $ 要得到 $ x_1 = 1 $ 和 $ x_2 = 1 $ . 所以在這種情況下，事實證明 $ g = V $ . 這是正確的計算方法嗎 $ g $ ?
假設上述計算方式 $ g $ 是正確的，如果他有 $ Attr ={{A,B,D}} $ ，那麼如果我們繼續進行與上述相同的過程（未知方程將是 $ (x_1,x_2,0,x_3) $ )，我們如何進行計算 $ g $ 因為我們有兩個案例？. 我知道 $ {{A,B,D}} \supset {{A,D}} $ 就像單調政策一樣。
另一種方式是該矩陣的行的每個子集包括 $ \mathcal{e} = (1,0,0) $ 當且僅當相應的屬性滿足公式時，在其範圍內。我們取對應的行 $ {{A,D}} $ 並找到係數 $ (1,1) $ 以便 $ e $ 在跨度內。**那為什麼 $ {A,B,D} $ 和 $ {A,C,D} $ 具有相同的係數，即 (1,0,1)？**我有一種模糊的直覺，但不確定。
正確的計算方法是什麼 $ g $ ?
此答案中的符號與對同一 LSSS 結構的問題的答案相同。
這是計算g的正確方法嗎？
你是正確的，你解決 $ g $ 通過設置屬性 $ B $ 和 $ C $ 為零。你實際上在做的是計算一個解向量，我將用它來表示 $ \mathbf{g}{{A,D}} \in \mathbb{F}^2 $ ， 至 $ \mathbf{g}{{A,D}} \cdot M_{{A,D}} = (1,0,0) $ 在哪裡
$ M_{{A,D}} = \begin{pmatrix} 1 & 1 & 0 \ 0 & -1 & 0 \end{pmatrix}, $
然後通過填充提升到解決方案 $ 0 $ s 得到一個完整的向量 $ \mathbf{g} $ . 所以在這裡你會發現 $ \mathbf{g}_{{A,D}}=(1,1) $ （在這種情況下恰好是唯一的），然後我們用 $ 0 $ s 在向量的對應分量中 $ V $ 要得到 $ (1,0,0,1) $ . 這個最終的解決方案（在填充之後）被稱為這個集合的重組向量。
向量 $ V $ 只是一種表示允許組合哪些行以嘗試獲得目標向量的方式 $ (1,0,0) $ . 如果你喜歡你可以考慮尋找 $ \mathbf{g} $ 就像找到方程的解一樣
$ \mathbf{g} \cdot \begin{pmatrix} 1 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 \end{pmatrix} \cdot M = (1,0,0) $
其中中間矩陣是一個零平方矩陣，將前導對角線替換為 $ V $ . 本質上是無關緊要的 $ V=\mathbf{g} $ 在這種情況下：關鍵是向量的支持（這裡是指非零分量的索引集） $ \mathbf{g} $ ，表示為 $ supp(\mathbf{g})={1,4} $ , 包含在 $ supp(V)={1,4} $ .
由於我們有兩種情況，我們如何繼續計算 g？
如果一個向量 $ \mathbf{g} $ 適用於較小的集合 $ {A,D} $ ，那麼它也適用於更大的集合 $ {A,B,D} $ ，因為目標向量已經位於由屬性索引的行的線性範圍內 $ {A,D} $ . 換句話說，相同的解決方案有效，因為 $ supp(\mathbf{g}) = {1,4} \subseteq supp((1,0,0,1)) = {1,4} \subseteq supp((1,1,0,1)) = {1,2,4} $ .
確實，很容易檢查您的解決方案 $ \mathbf{g}=(1,0,0,1) $ 也解決了
$ \mathbf{g} \cdot \begin{pmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 \ \end{pmatrix} \cdot M = (1,0,0). $
因此，通常計算重組向量就足夠了 $ \mathbf{g} $ 僅適用於最小授權集：則適用於任何授權集 $ A $ 我們可以採取任何 $ \mathbf{g} $ 對於任何包含該集合的最小授權集合 $ A $ 它也適用於 $ A $ .
那麼為什麼 {A,B,D} 和 {A,C,D} 具有相同的係數，即 (1,0,1)？
在這個例子中只有一個向量，即 $ \mathbf{g}=(1,0,0,1) $ 對於所有三組 $ {A,D} $ $ {A,B,D} $ 和 $ {A,C,D} $ ，這意味著你得到 $ \mathbf{g}{{A,B,D}} = \mathbf{g}{{A,C,D}} = (1,0,1) $ . 這是因為要結合向量 $ { (1,1,0), (0,-1,1), (0,-1,0)} $ 擁有者 $ {A,B,D} $ ，我們必須有零貢獻 $ (0,-1,1) $ ; 同樣，組合向量 $ { (1,1,0), (0,0,-1), (0,-1,0)} $ 擁有者 $ {A,B,D} $ ，我們必須有零貢獻 $ (0,0,-1) $ , 否則第三個分量不會 $ 0 $ 因為它必須用於建構目標向量 $ (1,0,0) $ .