基于矩阵特征值的可验证无可信中心门限方案

Verifiable Threshold Scheme without Trusted Center Based on Matrix Eigenvalue

摘要

传统的门限（秘密共享）方案大多存在一个可信中心，可信中心负责秘密份额的产生、分配以及秘密的恢复，这会影响系统的安全性、鲁棒性和可用性，本文利用矩阵特征值的特点，设计了一个可验证无可信中心门限方案。在本文方案中，所有参与者提供相同秘密份额的值给黑盒子，构成一个2n维的可逆方阵 P，该可逆方阵 P 和对角矩阵 L 生成一个矩阵 A，将矩阵 A 的特征向量标准正交化，作为子密钥分发给各参与者。每个参与者各分得两个子密钥，这两个子密钥满足两个条件：正交和所对应的特征值相同。在子密钥生成和主密钥恢复的过程中，均可以利用这两个条件保证方案安全实施。分析表明，该方案是正确且安全的，信息率为1/2。通过实例说明了方案的可行性。

Abstract

Mostly,there is a trusted center in traditional secret sharing （threshold） schemes，and the trusted center is responsible for the generation and distribution of secret shares and the recovery of secrets, which may affect the security, robustness and usability of the system. In this paper, we use the eigenvalues of matrices to design a verifiable untrusted central threshold scheme. In this scheme, all participants provide the same value of secret share equally to the black box, forming a 2n-dimensional matrix P of invertible matrix. A matrix A is generated for the reversible matrix P and the diagonal matrix L, and the standard orthogonalization of the eigenvector of the matrix A is distributed as a sub-key to each participant. Each participant is divided into two subkeys, which satisfies two conditions: orthogonality and the corresponding eigenvalues are the same. In the process of subkey generation and master key recovery, these two conditions can be used to ensure the security implementation of the scheme. The analysis results show that the scheme is correct and safe, and the information rate is 1/2. At the end of the article, examples are used to illustrate the feasibility of the implementation of the program.

关键词

门限 / 秘密共享 / 可信 / 可验证 / 黑盒子 / 特征向量

Key words

threshold / secret sharing / credible / verifiable / black box / eigenvector

0　 引 言

门限(秘密共享)方案常被作为密码学协议中的一种工具。Shamir^[1]和Blakley^[2]最先提出了两种(t,n)门限方案。随后，各类门限方案便被应用于不同场景，如机器间通信技术（machine-to-machine,M2M）中应用的效率扩展(t,n)门限方案^[3]，应用于公共信息频繁更新场景的基于格和Ajtai的单向函数的门限方案^[4]、多秘密共享^[5]、多级多秘密共享^[6]的门限方案，以及基于量子加密的多方量子秘密共享方案^[7]。上所述方案都需要一个秘密分发方，即可信中心的存在方能成立。

然而，可信中心的存在会导致“权威欺骗”问题，成为系统单点失败源，其任何安全失误或故障会暴露秘密或使系统崩溃。因此，“无可信中心”这一概念被提出^[8,9]，并在此基础上发展出不同的应用。例如基于无可信中心的全分布式密钥管理方案^[10]；无可信中心的动态门限签名方案^[11]；无共享分布式中心（SDC）的秘密共享方案^[12]；成员可协同交互的无可信中心秘密共享方案^[13]。

2018年，文献[14]首次借助于特征值提出一种无可信中心的门限秘密共享方案,是无可信中心概念下的又一次创新性研究。但该方案没有提供验证功能。因此，本文从矩阵特征值的角度设计了一种可验证的无可信中心的门限方案。所有的参与者均提供相同的秘密份额即列向量给黑盒子，协商生成子密钥，每个参与者均得到两个子密钥，且子密钥满足以下特征：子密钥的范数均为1；任意两个子密钥都是正交的；同一个参与者得到的子密钥所对应的特征值是相同的。根据以上特征，利用黑盒子可以进行欺诈检测。

1　 准备知识

1.1　数学相关基础知识

1.1.1　矩阵的特征值和特征向量

定义1^[15] 设 A 是n阶矩阵，如果数\lambda和n维非零列向量 x 使关系式

\mathit{A}\mathit{x}=\lambda \mathit{x}(1)

成立，那么，这样的数\lambda称为矩阵 A 的特征值，非零向量 x 称为 A 的对应于特征值\lambda的特征向量。

1.1.2　相似矩阵

定义2^[15] 设矩阵 A 、 B 都是n阶矩阵，若有可逆矩阵 P，使

{\mathit{P}}^{-\mathrm{1}}\mathit{A}\mathit{P}=\mathit{B}(2)

则称 B 是 A 的相似矩阵，可逆矩阵 P 称为把 A 变成 B 的相似变换矩阵。

推论1 若n阶矩阵 A 与对角矩阵\mathit{\Lambda }相似，则存在可逆矩阵 P，使

{\mathit{P}}^{-\mathrm{1}}\mathit{A}\mathit{P}=\mathit{\Lambda }=\left(\begin{array}{cccc}{\lambda }_{\mathrm{1}}& & & \\ & {\lambda }_{\mathrm{2}}& & \\ & & \ddots & \\ & & & {\lambda }_n\end{array}\right)

{\lambda }_{\mathrm{1}},{\lambda }_{\mathrm{2}},\cdots ,{\lambda }_n即是 A 的n个特征值。 P 用其列向量表示为\mathit{P}=({\mathit{p}}_{\mathrm{1}},{\mathit{p}}_{\mathrm{2}},\cdots ,{\mathit{p}}_n)，于是有

\mathit{A}{\mathit{p}}_i={\mathit{p}}_i{\lambda }_i,i=\mathrm{1,2}\cdots n(3)

P 的列向量{\mathit{p}}_i就是 A 的对应于{\lambda }_i的特征向量。

定理1n阶矩阵 A 与对角阵\mathit{\Lambda }相似（即 A 能对角化）的充分必要条件是 A 有n个线性无关的特征向量。

定理2 若n阶矩阵 A 与 B 相似，则 A 与 B 的特征值相同。

1.1.3　向量组的线性相关性

定义3^[15] 给定向量组\mathit{A}:a_{\mathrm{1}},a_{\mathrm{2}},\cdots ,a_n，如果存在不全为零的数k_{\mathrm{1}},k_{\mathrm{2}},\cdots ,k_n，使

k_{\mathrm{1}}{a}_{\mathrm{1}}+k_{\mathrm{2}}{a}_{\mathrm{2}}+\cdots +k_m{a}_m=\mathrm{0}(4)

则称向量组 A 是线性相关的，否则称它线性无关。

1.1.4　标准正交化

定义4 设a_{\mathrm{1}},a_{\mathrm{2}},\cdots ,a_n是向量空间 V 的一个基，求\mathit{V}的一个标准正交基，即要找一组两两正交的单位向量e_{\mathrm{1}},e_{\mathrm{2}},\cdots ,e_n，使得e_{\mathrm{1}},e_{\mathrm{2}},\cdots ,e_n与a_{\mathrm{1}},a_{\mathrm{2}},\cdots ,a_n等价。这一过程称为将基a_{\mathrm{1}},a_{\mathrm{2}},\cdots ,a_n标准正交化。

标准正交化包括两个步骤，即施密特正交化和单位化。施密特正交化过程了如下

b_{\mathrm{1}}=a_{\mathrm{1}}

b_{\mathrm{2}}=a_{\mathrm{2}}-\frac{[b_{\mathrm{1}},a_{\mathrm{2}}]}{[b_{\mathrm{1}},b_{\mathrm{1}}]}{b}_{\mathrm{1}}

⋮

b_n=a_n-\frac{[b_{\mathrm{1}},a_n]}{[b_{\mathrm{1}},b_{\mathrm{1}}]}{b}_{\mathrm{1}}-\frac{[b_{\mathrm{2}},a_n]}{[b_{\mathrm{2}},b_{\mathrm{2}}]}{b}_{\mathrm{2}}-\cdots -\frac{[b_{n-\mathrm{1}},a_n]}{[b_{n-\mathrm{1}},b_{n-\mathrm{1}}]}{b}_{n-\mathrm{1}}(5)

容易验证b_{\mathrm{1}},b_{\mathrm{2}},\cdots ,b_n两两正交，且b_{\mathrm{1}},b_{\mathrm{2}},\cdots ,b_n与a_{\mathrm{1}},a_{\mathrm{2}},\cdots ,a_n等价。

单位化步骤如下

e_{\mathrm{1}}=\frac{\mathrm{1}}{‖b_{\mathrm{1}}‖}{b}_{\mathrm{1}}，

e_{\mathrm{2}}=\frac{\mathrm{1}}{‖b_{\mathrm{2}}‖}{b}_{\mathrm{2}}，

⋮

e_n=\frac{\mathrm{1}}{‖b_n‖}{b}_n(6)

e_{\mathrm{1}},e_{\mathrm{2}},\cdots ,e_n就是 V 的一个标准正交基。

1.2　黑盒子

1.2.1　黑盒子的定义

定义5 所谓“黑盒子”，是指对于一个器件或产品，用户并不知其内部构造和原理，而只知它的功能及如何使用这些功能^[16]。

1.2.2　黑盒子的功能

本方案中的黑盒子需要满足以下功能：

1) 输入一个列向量，黑盒子可以判断该列向量和存储在黑盒子中向量组的线性相关性。本功能的实现根据公式(4)设计的，即

k_{\mathrm{1}}{\mathit{p}}_{\mathrm{1}}+k_{\mathrm{2}}{\mathit{p}}_{\mathrm{2}}+\cdots +k_m{\mathit{p}}_m=\mathrm{0}

其中，{\mathit{p}}_{\mathrm{1}},{\mathit{p}}_{\mathrm{2}},\cdots ,{\mathit{p}}_m是每次参与者输入的列向量。当新输入的列向量和存储在黑盒子中的向量组线性相关时，黑盒子要求参与者继续输入列向量，直到满足线性无关的条件为止。

2) 输入一个线性无关的向量组，可以将该向量组构成一个可逆的矩阵 P，根据(2)式求出对角矩阵\mathit{\Lambda }的相似矩阵 A。求出矩阵 A 的特征向量，并将其标准正交化，得到n个正交的单位向量，作为子密钥分发给参与者。

3) 输入一个特征向量，黑盒子输出该特征向量对应的特征值。

本功能的实现是根据(3)式设计的，即

\mathit{A}{\mathit{q}}_{ij}={\mathit{q}}_{ij}{\lambda }_i

其中，{\mathit{q}}_{ij}是参与者输入的子密钥，输出的是该子密钥所应用的特征值。

2　 本文方案

本方案可分为三个步骤：参数选取、秘密生成以及秘密恢复。

2.1　参数选取

本门限系统包含n个参与者。n个参与者构成集合B，将B划分为几个不相交的集合，

B=\stackrel{t}{\underset{i=\mathrm{1}}{\cup }}{B}_i

其中:\left|B_i\right|=n_i(\mathrm{1}\le i\le t,n_{\mathrm{1}}+n_{\mathrm{2}}+\cdots +n_t=n)。

首先，每个集合的参与者通过Diffie-Hellman密钥交换协议获得会话密钥{\lambda }_i值(\mathrm{1}\le i\le t)，并将{\lambda }_i值发送给黑盒子。黑盒子根据得到的{\lambda }_i值，生成一个对角矩阵

=\left(\begin{array}{cccccccccc}{\lambda }_{\mathrm{1}}& & & & & & & & & \\ & \ddots & & & & & & & & \\ & & {\lambda }_{\mathrm{1}}& & & & & & & \\ & & & {\lambda }_{\mathrm{2}}& & & & & & \\ & & & & \ddots & & & & & \\ & & & & & {\lambda }_{\mathrm{2}}& & & & \\ & & & & & & \ddots & & & \\ & & & & & & & {\lambda }_t& & \\ & & & & & & & & \ddots & \\ & & & & & & & & & {\lambda }_t\end{array}\right)\begin{array}{l}\left.\begin{array}{l}\\ \\ \end{array}\right\}\mathrm{2}{n}_{\mathrm{1}}\\ \left.\begin{array}{l}\\ \\ \end{array}\right\}\mathrm{2}{n}_{\mathrm{2}}\\ \\ \left.\begin{array}{l}\\ \\ \end{array}\right\}\mathrm{2}{n}_t\end{array}

其中，{\lambda }_{\mathrm{1}}有\mathrm{2}{n}_{\mathrm{1}}个，{\lambda }_{\mathrm{2}}有\mathrm{2}{n}_{\mathrm{2}}个，…，{\lambda }_t有\mathrm{2}{n}_t个。本文方案中，各集合的参与者利用了密钥交换协议得到会话密钥，而不知道会话密钥的内容。

然后，选定一个素数p，选定t个小于p的两两不相同整数x_{\mathrm{1}},x_{\mathrm{2}},\cdots ,x_t(如选择1,2,…,t)和参与者提供的初始信息{\lambda }_i组合成t个数对（x_i,{\lambda }_i）。假设主秘密为k=a_{\mathrm{0}}，选取x_{\mathrm{0}}=\mathrm{0}组成秘密数对（x_{\mathrm{0}},k）。（x_{\mathrm{0}},k）和t个数对（x_i,{\lambda }_i）经过Lagrange Interpolation 公式生成一个t次多项式

s(x)=a_{\mathrm{0}}+a_{\mathrm{1}}x+\cdots +a_t{x}^t(\mathrm{m}\mathrm{o}\mathrm{d}p)(7)

此时的主秘密为k=a_{\mathrm{0}}。

2.2　秘密生成

首先，集合B₁中的参与者B₁₁生成一个2n维的列向量{\mathit{p}}_{\mathrm{11}}给黑盒子，黑盒子将其存储在 P 中，此时\mathit{P}:{\mathit{p}}_{\mathrm{11}}，其构成的矩阵{\mathit{P}}_{\mathrm{2}n\times \mathrm{1}}=({\mathit{p}}_{\mathrm{11}})。

接着，参与者B₁₁又生成一个2n维的列向量{\mathit{p}}_{\mathrm{12}}给黑盒子，黑盒子验证{\mathit{p}}_{\mathrm{12}}与 P 是否线性相关。若相关，参与者B₁₁继续提供列向量给黑盒子，否则，将该列向量存储在 P 中，此时\mathit{P}:{\mathit{p}}_{\mathrm{11}},{\mathit{p}}_{\mathrm{12}}，其构成的矩阵

{\mathit{P}}_{\mathrm{2}n\times \mathrm{2}}=({\mathit{p}}_{\mathrm{11}},{\mathit{p}}_{\mathrm{12}})

以此类推，集合B₁中的每个参与者均提供两个列向量协商生成子密钥，得到

\mathit{P}:{\mathit{p}}_{\mathrm{11}},{\mathit{p}}_{\mathrm{12}},\cdots ,{\mathit{p}}_{\mathrm{1,2}{n}_{\mathrm{1}}-\mathrm{1}},{\mathit{p}}_{\mathrm{1,2}{n}_{\mathrm{1}}}，

其构成的矩阵

{\mathit{P}}_{\mathrm{2}{n}_{\mathrm{1}}\times \mathrm{2}{n}_{\mathrm{1}}}=({\mathit{p}}_{\mathrm{11}},{\mathit{p}}_{\mathrm{12}},\cdots ,{\mathit{p}}_{\mathrm{1,2}{n}_{\mathrm{1}}-\mathrm{1}},{\mathit{p}}_{\mathrm{1,2}{n}_{\mathrm{1}}})

同理，其他集合的参与者也按照集合B₁中参与者的方式提供2n维的列向量给黑盒子。最后，所有参与者提供的

\mathit{P}:{\mathit{p}}_{\mathrm{11}},{\mathit{p}}_{\mathrm{12}},\cdots ,{\mathit{p}}_{n_t\mathrm{1}},{\mathit{p}}_{n_t\mathrm{2}},{\mathit{p}}_{n_t,\mathrm{2}{n}_t-\mathrm{1}},{\mathit{p}}_{n_t,\mathrm{2}{n}_t}

其构成的矩阵

{\mathit{P}}_{\mathrm{2}n\times \mathrm{2}n}=({\mathit{p}}_{\mathrm{11}},{\mathit{p}}_{\mathrm{12}},\cdots ,{\mathit{p}}_{\mathrm{1,2}{n}_{\mathrm{1}}-\mathrm{1}},{\mathit{p}}_{\mathrm{1,2}{n}_{\mathrm{1}}},\cdots ,

{\mathit{p}}_{n_t\mathrm{1}},{\mathit{p}}_{n_t\mathrm{2}},\cdots ,{\mathit{p}}_{n_t,\mathrm{2}{n}_t-\mathrm{1}},{\mathit{p}}_{n_t,\mathrm{2}{n}_t})

然后，黑盒子利用推论1计算出

\mathit{A}=\mathit{P}\mathit{\Lambda }{\mathit{P}}^{-\mathrm{1}}=({\mathit{p}}_{\mathrm{11}},{\mathit{p}}_{\mathrm{12}},\cdots ,{\mathit{p}}_{n_t,\mathrm{2}{n}_t-\mathrm{1}},{\mathit{p}}_{n_t,\mathrm{2}{n}_t})·

\begin{array}{l}\left(\begin{array}{cccccccccc}{\lambda }_{\mathrm{1}}& & & & & & & & & \\ & \ddots & & & & & & & & \\ & & {\lambda }_{\mathrm{1}}& & & & & & & \\ & & & {\lambda }_{\mathrm{2}}& & & & & & \\ & & & & \ddots & & & & & \\ & & & & & {\lambda }_{\mathrm{2}}& & & & \\ & & & & & & \ddots & & & \\ & & & & & & & {\lambda }_t& & \\ & & & & & & & & \ddots & \\ & & & & & & & & & {\lambda }_t\end{array}\right)\\ ({\mathit{p}}_{\mathrm{11}},{\mathit{p}}_{\mathrm{12}},\cdots ,{\mathit{p}}_{n_t,\mathrm{2}{n}_t-\mathrm{1}},{\mathit{p}}_{n_t,\mathrm{2}{n}_t}{)}^{-\mathrm{1}}\end{array}·

求出该相似矩阵的特征向量，将其标准正交化，得到

{\mathit{E}}_{\mathrm{2}n\times \mathrm{2}n}=(e_{\mathrm{11}},e_{\mathrm{12}},\cdots ,e_{\mathrm{1,2}{n}_{\mathrm{1}}-\mathrm{1}},e_{\mathrm{1,2}{n}_{\mathrm{1}}},\cdots ,e_{n_t\mathrm{1}},e_{n_t\mathrm{2}},\cdots ,e_{n_t,\mathrm{2}{n}_t-\mathrm{1}},e_{n_t,\mathrm{2}{n}_t})

将其作为子密钥分发给各参与者。

最后，黑盒子将(x_i,e_{ij})和(x_i,e_{ij+\mathrm{1}})(\mathrm{1}\le i\le t,\mathrm{1}\le j\le \mathrm{2}{n}_i)作为子密钥分发给各集合的参与者，同时也将(x_{-\mathrm{1}},s(x_{-\mathrm{1}}))发送给每个参与者，其中x_{-\mathrm{1}}\in {\mathbb{Z}}_p，且与x_{\mathrm{1}},x_{\mathrm{2}},\cdots ,x_t均不相同。

2.3　秘密恢复

由于门限的特殊性，要求恢复秘密的参与者数目不少于门限值t，也就是每个参与者集合必须至少出一个人(不失一般性)。

首先，假设集合B₁中参与者B₁₁提供两个子密钥对(x_{\mathrm{1}},e_{\mathrm{11}})和(x_{\mathrm{1}},e_{\mathrm{12}})，集合B₂中参与者B₂₁提供两个子密钥对(x_{\mathrm{2}},e_{\mathrm{21}})和(x_{\mathrm{2}},e_{\mathrm{22}})，…，集合B_t中参与者B_{t\mathrm{1}}提供两个子密钥(x_t,e_{t\mathrm{1}})和(x_t,e_{t\mathrm{2}})。在恢复密钥之前，他们需要将自己手中两个子密钥输入黑盒子进行验证：

① e_{i\mathrm{1}}和e_{i\mathrm{2}}正交；

② e_{i\mathrm{1}}和e_{i\mathrm{2}}对应的特征值相等；

只有同时满足以上两个条件才进行下一步操作，否则，停止密钥恢复工作。

然后，他们均将自己的子密钥输入到黑盒子中去，根据(2)式，可以得到{\lambda }_{\mathrm{1}},{\lambda }_{\mathrm{2}},\cdots ,{\lambda }_t。

最后，将(x_{-\mathrm{1}},{\lambda }_{-\mathrm{1}})和t个数对(x_i,{\lambda }_i)一起代入Lagrange Interpolation 公式，得到共享主密钥k。

3　 方案分析

3.1　参数选取

命题1 在参与者诚实而正确地执行协议的情况下，任意授权子集都可以恢复秘密k。

证 设Q是一个最小授权子集，

Q=\{e_{\mathrm{11}}\bigcup e_{\mathrm{12}},e_{\mathrm{21}}\bigcup e_{\mathrm{22}},\cdots ,e_{t\mathrm{1}}\bigcup e_{t\mathrm{2}}\}

在黑盒子中输入子密钥e_{ij}后即可得到集合H=\{{\lambda }_{\mathrm{1}},{\lambda }_{\mathrm{2}},\cdots ,{\lambda }_t\}。将(x_{-\mathrm{1}},{\lambda }_{-\mathrm{1}})和t个数对(x_i,{\lambda }_i)代入(7)式，从而得到方程组

\left\{\begin{array}{l}s(x_{-\mathrm{1}})=a_{\mathrm{0}}+a_{\mathrm{1}}\cdot x_{-\mathrm{1}}+\cdots +a_t\cdot x_{\mathrm{1}}^t={\lambda }_{-\mathrm{1}}\\ s(x_{\mathrm{1}})=a_{\mathrm{0}}+a_{\mathrm{1}}\cdot x_{\mathrm{1}}+\cdots +a_t\cdot x_{\mathrm{1}}^t={\lambda }_{\mathrm{1}}\\ ⋮\\ s(x_t)=a_{\mathrm{0}}+a_{\mathrm{1}}\cdot x_t+\cdots +a_t\cdot x_{\mathrm{1}}^t={\lambda }_t\end{array}\right.

则系数矩阵为

\mathit{N}=\left(\begin{array}{cccc}\mathrm{1}& x_{-\mathrm{1}}& \cdots & x_{-\mathrm{1}}^t\\ \mathrm{1}& x_{\mathrm{1}}& \cdots & x_{\mathrm{1}}^t\\ ⋮& ⋮& ⋮& ⋮\\ \mathrm{1}& x_t& \cdots & x_t^t\end{array}\right)

N 可以看成一个的(t+\mathrm{1})\times (t+\mathrm{1})范德蒙矩阵，那么它的行列式D=\prod _{(t+\mathrm{1})\ge m>n\ge \mathrm{1}}(x_m-x_n)。因为x_{-\mathrm{1}},x_{\mathrm{1}},x_{\mathrm{2}},\cdots ,x_t互不相等，所以D\ne \mathrm{0}。由线性方程组的卡莱姆法则，知方程组有唯一解，从而可以求出s(x)。证毕。

3.2　安全性

为了防止系统内部不诚信成员的欺骗和系统外部伪成员的攻击，本方案可以通过(3)~(6)式对成员的子秘密份额进行信息认证，具体确认方法如下。

在子密钥生成阶段，分发给各参与者的子密钥均满足以下特点：

1) 子密钥的范数为1；

2) 同一集合参与者得到的任意两个子密钥都是正交的；

3) 同一集合参与者所得到的子密钥对应的特征值是相同的。

当所有集合的参与者得到的子密钥满足以上所有条件时，说明子密钥生成阶段是诚实的；否则，说明存在欺诈行为。

在主密钥恢复阶段，参与主密钥恢复的参与者的子密钥均满足以下特点：

1) 子密钥的范数为1；

2) 任意两个不同集合参与者得到的子密钥都是正交的；

3) 参与主密钥恢复的参与者的两个子密钥所对应的特征值是相同的。

当参与秘密恢复的所有参与者满足以上所有条件时，说明参与者是诚实的；否则，说明参与秘密恢复的参与者中存在伪成员。

通过以上分析，说明该方案是正确的、安全的，同时还具有防欺诈检测的功能。门限方案的参与者每人需提供2个随机2n维列向量参与秘密生成，由此得出，该方案的信息率为1/2。在预防欺诈方面是无条件安全的。

3.3　创新性

本方案首次从特征值的角度，设计了一个门限方案。该门限方案无需可信中心，从而避免了可信中心的欺诈。所有参与者均提供两个n维列向量作为子密钥生成的原始信息，体现了参与者的公平性。在子密钥生成和主密钥恢复的过程中，都可以利用两个子密钥的特征，检测活动的真实性，有效避免了可信中心欺诈和参与成员的诈骗行为。

4　 方案的具体实例

下面用一个例子说明方案的可行性。

设有B₁、B₂两个集合，集合B₁中有1个参与者B₁₁，集合B₂中有1个参与者B₂₁。试为这2个集合的2个参与者分配密钥，并分析重构密钥k的过程。

4.1　安全性参数选取

首先，利用密钥协商协议，集合B₁和集合B₂中的参与者分别得到协商的结果{\lambda }_{\mathrm{1}}=\mathrm{2}和{\lambda }_{\mathrm{2}}=\mathrm{1}。将{\lambda }_{\mathrm{1}}和{\lambda }_{\mathrm{2}}加密传输到黑盒中去，生成对角矩阵

\mathit{\Lambda }=\left(\begin{array}{cccc}\mathrm{2}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{2}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}\end{array}\right)

假设共享秘密k=\mathrm{4}。然后，选取(x_{\mathrm{0}},k)=(\mathrm{0,4})，(x_{\mathrm{1}},{\lambda }_{\mathrm{1}})=(\mathrm{1,2})和(x_{\mathrm{2}},{\lambda }_{\mathrm{2}})=(\mathrm{2,1})，经过Lagrange Interpolation，得到

s(x)\equiv \mathrm{6}{x}^{\mathrm{2}}+\mathrm{3}x+\mathrm{4}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{11})

此时的共享主密钥是k=\mathrm{4}。

4.2　秘密生成

首先，集合B₁中的参与者生成一个4维的列向量{\mathit{p}}_{\mathrm{11}}={(\begin{array}{cccc}\mathrm{0}& \mathrm{0}& -\mathrm{1}& \mathrm{1}\end{array})}^{\mathrm{T}}给黑盒子，黑盒子将其存储到 P 中，此时\mathit{P}=({\mathit{p}}_{\mathrm{11}}{)}^{\mathrm{T}}=({\begin{array}{cccc}\mathrm{0}& \mathrm{0}& -\mathrm{1}& \mathrm{1})\end{array}}^{\mathrm{T}}。接着，参与者又生成了一个4维的列向量{\mathit{p}}_{\mathrm{12}}给黑盒子，并验证{\mathit{p}}_{\mathrm{12}}和向量组 P 之间的线性相关性。当二者线性相关时，该参与者继续提供列向量给黑盒子，否则，将{\mathit{p}}_{\mathrm{12}}存储到向量组 P 中，此时的{\mathit{p}}_{\mathrm{12}}={(\begin{array}{cccc}\mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}\end{array})}^{\mathrm{T}}。将其加入到向量组 P 中，得到\mathit{P}=({\mathit{p}}_{\mathrm{11}},{\mathit{p}}_{\mathrm{12}})={\left(\begin{array}{cccc}\mathrm{0}& \mathrm{0}& -\mathrm{1}& \mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}\end{array}\right)}^{\mathrm{T}}。

集合B₁中的参与者也按同样的方式提供两个线性无关的列向量{\mathit{p}}_{\mathrm{21}}={(\begin{array}{cccc}\mathrm{1}& \mathrm{0}& \mathrm{0}& -\mathrm{1}\end{array})}^{\mathrm{T}},{\mathit{p}}_{\mathrm{22}}={(\begin{array}{cccc}\mathrm{0}& \mathrm{1}& \mathrm{1}& -\mathrm{1}\end{array})}^{\mathrm{T}}给黑盒子，验证通过后分别存储到向量组 P 中，得到:\mathit{P}=(\begin{array}{cccc}{\mathit{p}}_{\mathrm{11}}& {\mathit{p}}_{\mathrm{12}}& {\mathit{p}}_{\mathrm{21}}& {\mathit{p}}_{\mathrm{22}}\end{array})={\left(\begin{array}{rrrr}\mathrm{0}& \mathrm{0}& -\mathrm{1}& \mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}\\ \mathrm{1}& \mathrm{0}& \mathrm{0}& -\mathrm{1}\\ \mathrm{0}& \mathrm{1}& \mathrm{1}& -\mathrm{1}\end{array}\right)}^{\mathrm{T}}。

由推论1可得矩阵

=\mathit{P}\mathit{\Lambda }{\mathit{P}}^{-\mathrm{1}}=\left(\begin{array}{cccc}\mathrm{1}& \mathrm{0}& \mathrm{1}& \mathrm{1}\\ \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{2}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{2}\end{array}\right)

求出矩阵\mathit{A}的特征向量并将其标准正交化，得到向量组\mathit{E}=(e_{\mathrm{11}},e_{\mathrm{12}},e_{\mathrm{21}},e_{\mathrm{22}})，其所构成的矩阵为

\mathit{E}=(e_{\mathrm{11}},e_{\mathrm{12}},e_{\mathrm{21}},e_{\mathrm{22}})(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{11})=\left(\begin{array}{cccc}\mathrm{0}& \mathrm{3}& \mathrm{4}& \mathrm{0}\\ \mathrm{0}& \mathrm{3}& \mathrm{0}& \mathrm{5}\\ \mathrm{0}& \mathrm{7}& \mathrm{0}& \mathrm{5}\\ \mathrm{1}& \mathrm{0}& \mathrm{4}& \mathrm{6}\end{array}\right)

黑盒子将 E 中的列向量作为子密钥分发给参与者，得到两组密钥：k_{\mathrm{1}}=(x_{\mathrm{1}},e_{\mathrm{11}})\bigcup (x_{\mathrm{1}},e_{\mathrm{12}})；k_{\mathrm{2}}=(x_{\mathrm{2}},e_{\mathrm{21}})\bigcup (x_{\mathrm{2}},e_{\mathrm{22}})。将k_{\mathrm{1}}和k_{\mathrm{2}}分发给集合B₁中参与者和集合B₂中的参与者，同时将(-1，7)发送给所有参与者。

4.3　秘密恢复

首先，集合B₁中参与者和集合B₂中的参与者将提供的正确的子密钥输入到黑盒中，分别得到{\lambda }_{\mathrm{1}}=\mathrm{2}，{\lambda }_{\mathrm{2}}=\mathrm{1}。

然后，将(-1，7)、(1，2)和(2，1)代入Lagrange Interpolation 公式得到

\mathrm{7}\frac{(x-\mathrm{1})(x-\mathrm{2})}{(-\mathrm{1}-\mathrm{1})(-\mathrm{1}-\mathrm{2})}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{11})=

\mathrm{14}(x-\mathrm{1})(x-\mathrm{2})

\mathrm{2}\frac{(x-(-\mathrm{1}))(x-\mathrm{2})}{(\mathrm{1}-(-\mathrm{1}))(\mathrm{1}-\mathrm{2})}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{11})=

\mathrm{10}(x+\mathrm{1})(x-\mathrm{2})

\mathrm{1}\frac{(x-(-\mathrm{1}))(x-\mathrm{1})}{(\mathrm{2}-(-\mathrm{1}))(\mathrm{2}-\mathrm{1})}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{11})=

\mathrm{4}(x+\mathrm{1})(x-\mathrm{1})

所以

f(x)=[\mathrm{14}(x-\mathrm{1})(x-\mathrm{2})+\mathrm{10}(x+\mathrm{1})(x-\mathrm{2})+\mathrm{4}(x+\mathrm{1})(x-\mathrm{1})](\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{11})\equiv \mathrm{6}{x}^{\mathrm{2}}+\mathrm{3}x+\mathrm{4}

从而获得共享密钥k=\mathrm{4}。

5　 结 语

利用矩阵特征值的特性，设计了一个可验证无可信中心的门限方案。所有的参与者均提供相同秘密份额的值给黑盒子，协助子密钥的生成，每个参与者得到两个子密钥。通过分析参与者提供的子密钥的数值特征，可以进行防欺诈检测。该方案的信息率为1/2。

参考文献

[1] SHAMIR A. How to share a secret[J]. Communications of the ACM,1979,22(11):612-613. DOI:10.1145/359168.359176 .

[2] BLAKLEY G R. Safeguarding Cryptographic Keys[DB/OL].[2019-01-30].article/afips/1979/50870313/12OmNCeK2a1.

[3] SHEN J, ZHOU T Q, LIU X G, et al. A novel Latin⁃ square-based secret sharing for M2M communications [J]. IEEE Transactions on Industrial Informatics, 2018, 14(8):3659-3668. DOI：10.1109/TII.2018.2810840 .

[4] PILARAM H, EGHLIDOS T. An efficient lattice based multi-stage secret sharing scheme[J]. IEEE Transactions on Dependable and Secure Computing, 2015,14(1):2-8.DOI：10.1109/TDSC.2015.2432800 .

[5] HSU C F, HARN L, CUI G H. An ideal multi-secret sharing scheme based on connectivity of graphs [J]. Wireless Personal Communications, 2014,77(1):383-394. DOI：10.1007/s11277-013-1511-3 .

[6] SINGH N, TENTU A N, BASIT A, et al. Sequential Secret Sharing Scheme Based on Chinese Remainder Theorem[DB/OL]. [2019-02-20].

[7] AIN N U. A Novel Approach for Secure Multi-party Secret Sharing Scheme via Quantum Cryptography [DB/OL] [2019-02-22].

[8] PEDERSEN T P. A threshold cryptosystem without a trusted party[C]//Advances in Cryptology—EUROCRYPT’91. Berlin:Springer-Verlag, 1991:522-526.DOI:10.1007/3-540-46416-6_47 .

[9] LAIH C S, HARN L. Generalized Threshold Cryptosystems[DB/OL]. [2019-02-21].

[10] LUO H, KONG J, ZERFOS P, et al. URSA: Ubiquitous and robust access control for mobile ad hoc networks[J]. IEEE/ACM Transactions on Networking, 2004, 12(6):1049-1063. DOI:10.1109/TNET.2004.838598 .

[11] 张毅, 侯整风, 胡东辉. 一种动态的无可信中心(t,n)门限签名认证方案[J]. 合肥工业大学学报(自然科学版), 2011, 34(9):1341-1344. DOI:1003-5060(2011)09-1341-04 .

[12] ZHANG Y, HOU Z F, HU D H. A dynamic (t,n) threshold signature authentication scheme without a trusted party [J]. Journal of Hefei University of Technology(Natural Science), 2011, 34(9):1341-1344. DOI:1003-5060(2011)09-1341-04(Ch).

[13] XUE Y S, WU S L, CHEN H D. A Blakley Secret Sharing Scheme without Trusted Share Distributed Center[DB/OL]. [2019-02-21].

[14] 何二庆, 侯整风, 朱晓玲. 一种无可信中心动态秘密共享方案[J]. 计算机应用研究, 2013, 30(2):491-493.

[15] HE E Q, HOU Z F, ZHU X L. Proactive secret sharing scheme without trusted party [J]. Application Research of Computers, 2013, 30(2): 491-493 (Ch).

[16] 张艳硕, 李文敬, 陈雷,等. 基于特征值的可验证特殊门限秘密共享方案[J]. 通信学报, 2018,39(8):169-175. DOI:10.11959/j.issn.1000-436x.2018143 .

[17] ZHANG Y S, LI W J, CHEN L,et al. Verifiable special threshold secret sharing scheme based on eigenvalue[J]. Journal on Communications, 2018,39(8):169-175. DOI:10.11959/j.issn.1000-436x.2018143(Ch).

[18] 同济大学数学系编.工程数学线性代数[M].北京：高等教育出版社,2014.

[19] Department of Mathematics of Tongji University. Linear Algebra of Engineering Mathematics [M]. Beijing:Heigher Education Press,2014（Ch).

[20] 曹尔强, 张沂, 曹晔, 等. “软件黑盒子”文件加锁和加密的一个方法[J].长春邮电学院学报,1991,9(3):11-14.

[21] CAO E Q, ZHANG Y, CAO Y,et al. A technique of locking a disk and secreting a whole disk[J]. Journal of Changchun Post and Telecommunication Institute, 1991,9(3): 11-14 （Ch).

基金资助

国家重点研发计划(2018YFB1004101)

中央高校基本科研业务费项目(328201902)