张成方案简介参考专栏的文章张成方案。

分配秘密sss

假设M^\hat{M}M^是有lll列的单调张成方案，庄家持有的秘密为sss，可以按如下步骤构建秘密分割方案：
从Kl\mathcal{K^l}Kl中生成一个随机向量r⃗=(r1,r2,...,rl)\vec{r}=(r_1,r_2,...,r_l)r=(r1​,r2​,...,rl​)，满足r⃗⋅1⃗=∑i=1lri=s\vec{r}\cdot\vec{1}=\sum_{i=1}^l r_i=sr⋅1=∑i=1l​ri​=s。计算向量t∈Klt\in \mathcal{K^l}t∈Kl，t=M⋅r⃗t=M \cdot \vec{r}t=M⋅r，并按照M^\hat{M}M^中的行标记对ttt进行标记。并将标记为xix_ixi​的元素分配给PiP_iPi​作为PiP_iPi​的秘密份额。

重构秘密sss

G⊆｛P1,P2,...,Pn｝G\subseteq｛P_1,P_2,...,P_n｝G⊆｛P1​,P2​,...,Pn​｝是一个授权集合，δG⃗\vec{\delta_G}δG​​是GGG的特征向量。由于f(δG)=1f(\delta_G)=1f(δG​)=1，1⃗∈span(MδG)\vec{1}\in span(M_{\delta_G})1∈span(MδG​​)，即存在常数β1,β2,⋯,β∣G∣\beta_1,\beta_2,\cdots,\beta_{|G|}β1​,β2​,⋯,β∣G∣​，∑i=1∣G∣βiMi=1⃗\sum_{i=1}^{|G|} \beta_i M_i=\vec{1}∑i=1∣G∣​βi​Mi​=1。将GGG中参与方持有的秘密份额做如下线性变换即可恢复秘密s=∑i=1∣G∣βi(Mi⋅r⃗)s=\sum_{i=1}^{|G|} \beta_i (M_i\cdot \vec{r})s=∑i=1∣G∣​βi​(Mi​⋅r)

案例

M=[120013101090]M=\begin{bmatrix} 1 & 2 & 0\\ 0 & 1 & 3 \\ 1 & 0 & 1 \\ 0 & 9 & 0\end{bmatrix}M=⎣⎢⎢⎡​1010​2109​0310​⎦⎥⎥⎤​，ρ(1)=x1,ρ2(2)=x2,ρ3(3)=x3,ρ4(4)=x4\rho(1)=x_1,\rho_2(2)=x_2,\rho_3(3)=x_3,\rho_4(4)=x_4ρ(1)=x1​,ρ2​(2)=x2​,ρ3​(3)=x3​,ρ4​(4)=x4​，G={P1,P2,P3}G=\{ P_1,P_2,P_3 \}G={P1​,P2​,P3​}。明显存在1⃗∈span(MδG)\vec{1}\in span(M_{\delta_G})1∈span(MδG​​)，对应常数β1=37,β2=17,β3=47\beta_1=\frac{3}{7},\beta_2=\frac{1}{7},\beta_3=\frac{4}{7}β1​=73​,β2​=71​,β3​=74​。 设r⃗=(1,2,2),s=5\vec{r}=(1,2,2),s=5r=(1,2,2),s=5。分配给P1,P2,P3P_1,P_2,P_3P1​,P2​,P3​的秘密份额分别为5,8,35,8,35,8,3。则秘密s=5∗37+8∗17+3∗47=5s=5*\frac{3}{7}+8*\frac{1}{7}+3*\frac{4}{7}=5s=5∗73​+8∗71​+3∗74​=5

安全性证明

NNN是一个向量集合的矩阵表示，v⃗\vec{v}v与这个向量集合独立的充要条件是存在向量w⃗\vec{w}w满足N⋅w⃗=0⃗N\cdot \vec{w}=\vec{0}N⋅w=0且v⃗⋅w⃗≠0⃗\vec{v} \cdot \vec{w} \neq \vec{0}v⋅w​=0
设BBB是未授权集合。因为1⃗\vec{1}1与MδBM_{\delta_B}MδB​​独立，则存在向量r⃗′\vec{r}^{\prime}r′，使得MδB⋅r⃗′=0⃗M_{\delta_B} \cdot \vec{r}^{\prime}=\vec{0}MδB​​⋅r′=0但r⃗′⋅1⃗≠0\vec{r}^{\prime} \cdot \vec{1} \neq 0r′⋅1​=0。
对于任意a∈Zpa \in Z_pa∈Zp​，令R′=r⃗+ar⃗′R^{\prime}=\vec{r}+a\vec{r}^{\prime}R′=r+ar′，则有
MδB⋅R′=MδB⋅r⃗+a(MδB⋅r⃗′)=MδB⋅r⃗=c⃗M_{\delta_B} \cdot R^{\prime}=M_{\delta_B} \cdot \vec{r} + a(M_{\delta_B} \cdot \vec{r}^{\prime})=M_{\delta_B} \cdot \vec{r}=\vec{c}MδB​​⋅R′=MδB​​⋅r+a(MδB​​⋅r′)=MδB​​⋅r=c，其中c⃗\vec{c}c为BBB的秘密份额。
1⃗⋅R′=1⃗⋅(r⃗+ar⃗′)=1⃗⋅r⃗+a(1⃗⋅r⃗′)=s+a(1⃗⋅r⃗′)\vec{1} \cdot R^{\prime}=\vec{1} \cdot (\vec{r} + a\vec{r}^{\prime})=\vec{1} \cdot \vec{r}+a(\vec{1} \cdot \vec{r}^{\prime})=s+a(\vec{1} \cdot \vec{r}^{\prime})1⋅R′=1⋅(r+ar′)=1⋅r+a(1⋅r′)=s+a(1⋅r′)
即证。