基于张成方案建立秘密分割方案

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

分配秘密$s$

假设$\hat{M}$是有$l$列的单调张成方案，庄家持有的秘密为$s$，可以按如下步骤构建秘密分割方案：
从${\mathcal{K}}^l$中生成一个随机向量$\vec{r}=(r_1,r_2,...,r_l)$，满足$\vec{r}\cdot \vec{1}={\sum }_{i=1}^l{r}_i=s$。计算向量$t\in {\mathcal{K}}^l$，$t=M\cdot \vec{r}$，并按照$\hat{M}$中的行标记对$t$进行标记。并将标记为$x_i$的元素分配给$P_i$作为$P_i$的秘密份额。

重构秘密$s$

$G\subseteq ｛P_1,P_2,...,P_n｝$是一个授权集合，$\overrightarrow{{\delta }_G}$是$G$的特征向量。由于$f({\delta }_G)=1$，$\vec{1}\in span(M_{{\delta }_G})$，即存在常数${\beta }_1,{\beta }_2,\cdots ,{\beta }_{|G|}$，${\sum }_{i=1}^{|G|}{\beta }_i{M}_i=\vec{1}$。将$G$中参与方持有的秘密份额做如下线性变换即可恢复秘密$s={\sum }_{i=1}^{|G|}{\beta }_i(M_i\cdot \vec{r})$

案例

$M=\left[\begin{array}{ccc}1& 2& 0\\ 0& 1& 3\\ 1& 0& 1\\ 0& 9& 0\end{array}\right]$，$\rho (1)=x_1,{\rho }_2(2)=x_2,{\rho }_3(3)=x_3,{\rho }_4(4)=x_4$， G = { P 1 , P 2 , P 3 } G=\{ P_1,P_2,P_3 \} G={P1​,P2​,P3​}。明显存在$\vec{1}\in span(M_{{\delta }_G})$，对应常数${\beta }_1=\frac{3}{7},{\beta }_2=\frac{1}{7},{\beta }_3=\frac{4}{7}$。 设$\vec{r}=(1,2,2),s=5$。分配给$P_1,P_2,P_3$的秘密份额分别为$5,8,3$。则秘密$s=5\ast \frac{3}{7}+8\ast \frac{1}{7}+3\ast \frac{4}{7}=5$

安全性证明

$N$是一个向量集合的矩阵表示，$\vec{v}$与这个向量集合独立的充要条件是存在向量$\vec{w}$满足$N\cdot \vec{w}=\vec{0}$且$\vec{v}\cdot \vec{w}\ne \vec{0}$
设$B$是未授权集合。因为$\vec{1}$与$M_{{\delta }_B}$独立，则存在向量${\vec{r}}^{\prime }$，使得$M_{{\delta }_B}\cdot {\vec{r}}^{\prime }=\vec{0}$但${\vec{r}}^{\prime }\cdot \vec{1}\ne 0$。
对于任意$a\in Z_p$，令$R^{\prime }=\vec{r}+a{\vec{r}}^{\prime }$，则有
$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}$，其中$\vec{c}$为$B$的秘密份额。
$\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 })$
即证。