關於 LSSS 中的重建向量的問題
假設我們有一個政策 $ 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 頁）。
我對取自此（第 7 頁）的黃色標記線有疑問。
$ \textbf{Is the resulting 0 a vector in $w \cdot M_i$ ? Is the first entry of the vector $w$ -1? } $ $ \textbf{How do one go on to calculate this $w$?} $ . 如果有人可以使用上面的上述 LSSS 矩陣和未經授權的子集進行解釋，將會很有幫助 $ {{A,B}} $ .
對於 tl;dr，請參閱最後幾段。
LSSS 背景
您所指的線性秘密共享的建構基於稱為單調跨度程序的計算模型。 其他論文 更詳細，應該有助於解決進一步的問題。
引起您的問題的論文是一種從給定的布爾公式（等效地，從訪問結構）構造 LSSS 的建議方法。現在，我們將假設他們的方法是正確的，並且 LSSS 矩陣的推導如他們所描述的那樣：
$ \begin{array}{c} A \ B \ C \ D \end{array} \begin{pmatrix} 1 & 1 & 0 \ 0 & -1 & 1 \ 0 & 0 & -1 \ 0 & -1 & 0 \end{pmatrix} $
我們將這個矩陣表示為 $ M $ 並假設我們在一個領域工作 $ \mathbb{F} $ . 讓經銷商分享秘密 $ s \in \mathbb{F} $ 在這個方案中，他做了以下事情：
- 選擇任何向量 $ \mathbf{x}\in \mathbb{F}^3 $ 這樣 $ \langle \mathbf{x}, (1,0,0) \rangle = s $ （即與目標向量的內積是秘密）；
- 計算 $ \mathbf{y} := M\cdot \mathbf{x} $ ;
- 給 $ \mathbf{y}[i] $ （這 $ i^{\text{th}} $ 的組成部分 $ \mathbf{y} $ ) 分配給矩陣對應行的一方 $ M $ . 所以在這種情況下，例如派對 $ C $ 將收到的第三部分 $ \mathbf{y} $ .
現在假設 LSSS 矩陣的構造是正確的，那麼任何一組合格的當事人都應該能夠結合他們的股份來獲得秘密。這是因為 LSSS 的構造要求任何一組合格方持有的所有行的跨度必須在其線性跨度中包含目標向量。
在這個例子中， $ {A,D} $ 應該是合格的，實際上是第一行的一倍到第四行的一倍，即計算 $ 1 \cdot (1, 1, 0) + 1 \cdot (0, -1, 0) = (1, 0, 0) $ ，給他們目標向量。
這很有用，因為通過線性，各方 $ A $ 和 $ D $ 可以使用他們的份額使用相同的線性組合來計算秘密：即 $ 1 \cdot \mathbf{y}[1] + 1 \cdot \mathbf{y}[4] = s $ .
所需的線性組合被編碼在一個向量中：在執行範例中 $ {A,D} $ ，重組向量為 $ \mathbf{r}=(1,0,0,1) $ ，因為我們需要將第一行添加到第四行。
再次假設 LSSS 的構造是正確的，我們還將要求未經授權的各方集沒有關於秘密的資訊。當且僅當目標向量不位於這些方持有的行的線性範圍內時，這是正確的。
讓我們用 $ M_U $ 的子矩陣 $ M $ 我們只選擇了一些未經授權的各方擁有的行 $ U $ . 所以我們有，例如
$ M_{{A,B}} = \begin{pmatrix} 1 & 1 & 0 \ 0 & -1 & 1 \end{pmatrix} $
看到勾結的各方 $ {A,B} $ 不學習任何資訊，觀察如果 $ (1,0,0)^\top \not \in \text{im}(M_{{A,B}}^\top) $ 然後由線性代數基本定理， $ (1,0,0)^\top \not \in \text{ker}(M_{{A,B}})^\perp $ 所以一定存在一些向量 $ \mathbf{w} \in \mathbb{F}^3 $ 這樣 $ M_{{A,B}} \cdot \mathbf{w} = 0 $ 和 $ \langle \mathbf{w} ,(1,0,0)^\top\rangle \ne 0 $ . （換句話說， $ \mathbf{w} $ 必須存在，否則每個向量 $ \text{ker}(M_{{A,B}}) $ 垂直於 $ (1,0,0)^\top $ , 矛盾的 $ (1,0,0)^\top \not \in \text{im}(M_{{A,B}}^\top)=\text{ker}(M_{{A,B}})^\perp $ .)
特別是，我們可以找到任何 $ \mathbf{v} $ 這樣 $ \langle \mathbf{v} ,(1,0,0)\rangle \ne 0 $ 和 $ M_{{A,B}}^\top \cdot \mathbf{v} = 0 $ 然後設置 $ \mathbf{w} = \frac{\mathbf{v}}{-|\mathbf{v}|2} $ 以便 $ \langle \mathbf{w} ,(1,0,0)\rangle = -1 $ 和 $ M{{A,B}} \cdot \mathbf{w} = M_{{A,B}} \cdot \frac{\mathbf{v}}{-|\mathbf{v}|_2} = \mathbf{0} $ . 這是您強調的主張。
我們發現的事實 $ \mathbf{w} $ 已經表明，未經授權方持有的股份的聯合沒有提供有關秘密的資訊，因為添加向量 $ k \cdot \mathbf{w} $ 到向量 $ \mathbf{x} $ 上面用於生成向量中編碼的共享 $ \mathbf{y} $ ， 在哪裡 $ k\in \mathbb{F} $ 是任何欄位元素，為相關的未經授權方提供相同的共享集，因為我們有共享 $ M \cdot (\mathbf{x} + k\mathbf{w}) = M \cdot \mathbf{x} + M \cdot k\mathbf{w} = \mathbf{y} + k M \cdot \mathbf{w} $ 對應秘密 $ \langle \mathbf{x} + k \mathbf{w} , (1,0,0) \rangle = s + k \cdot -1 $ 並且因為 $ M_U \mathbf{w} = \mathbf{0} $ , 持有的股份 $ U $ 可以同樣地共享任何秘密，我們通過改變 $ k $ 任意。因此，這些各方持有的股份無法向他們提供有關秘密是什麼的任何資訊。
計算 $ \mathbf{w} $
至少有一個 $ \mathbf{w} $ 對於每個未經授權的集合（假設 LSSS 已正確建構）。請注意，您只需要找到一個 $ \mathbf{w} $ 對於每個最大未經授權的集合（因為這個 $ \mathbf{w} $ 也適用於任何子集）。
計算實際 $ \mathbf{w} $ 如您的參考文獻中所述，涉及在 $ (M_{{A,B}})^\perp $ （稱為cokernel或left kernel $ M_{{A,B}} $ ) 在第一個分量中是非零的，並且是縮放的。如果是 $ {A,B} $ , 很容易找到 $ \mathbf{w} $ 通過檢查具有所需的屬性：我們可以看到向量 $ \mathbf{w} = (-1, 1, 1)^\top $ 滿足 $ M_{{A,B}}^\top \cdot \mathbf{w} = \mathbf{0} $ , 它認為 $ \langle (-1,1,1),(1,0,0)\rangle = -1 $ ，這是我們需要的（在轉置之後）。
對於此方案中的較大矩陣，您只需要一種計算給定子矩陣的 cokernel 的方法，然後從那裡獲取任何向量 $ \mathbf{w} $ 在那個滿足的空間裡 $ \langle \mathbf{w},(1,0,\ldots,0)\rangle = -1 $ ，即第一個組件在哪裡 $ -1 $ .