基于CRT和RSA的指定参与者的门限秘密共享方案

Threshold Secret Sharing Scheme with Designated Participants Based on CRT and RSA

摘要: 针对医院间共享数据的实际需求，本文基于中国剩余定理结合RSA公钥加密分别设计了指定一个参与者和指定多个参与者的门限秘密共享方案，以实现医疗数据的安全共享。在秘密分发阶段，指定参与者可自主选择秘密份额，且无需在分发者与参与者之间建立安全信道；在秘密重构阶段，必须有特定的参与者参与才能成功恢复原始秘密。对方案的安全性与性能分析表明，所提出方案在效率和安全性上均优于现有方案。

Abstract: In order to meet the practical needs of sharing data between hospitals, this paper proposes a threshold secret sharing scheme for designating one participant and designating multiple participants based on the Chinese remainder theorem combined with RSA public key encryption, so as to realize the secure sharing of medical data. In the secret distribution phase, the designated participants can choose their own secret shares, and there is no need to establish a secure channel between the distributor and the participants; in the secret reconstruction phase, a designated participant must be involved in order to successfully recover the original secret. The analysis of the security and performance of the scheme shows that the proposed scheme is better than the existing scheme in terms of efficiency and security.

1. 引言

在如今的信息时代，数据安全尤为重要，秘密共享能够将某个秘密信息分成多个秘密份额共享给方案中的参与者，使得只有达到特定数量的秘密份额才能够恢复出原始的秘密信息，是保护数据隐私性的重要密码技术之一。Shamir [1]和Blakley [2]分别基于不同的工具提出了门限秘密共享方案，只有重构阶段的参与者提供的秘密份额数量等于或大于门限值时，可以重构得到秘密信息，否则这些参与者得不到关于秘密的任何信息。为了防止方案中的某些欺骗行为，1985年，Chor等人[3]提出了可验证秘密共享的概念。1987年，Feldman [4]设计了一种非交互的可验证秘密共享方案，该方案基于循环群上的离散对数困难假设。1983年，Asmuth和Bloom [5]提出了在整数环上基于中国剩余定理的门限秘密共享方案。在此基础上，Iftene [6]和Qiong等[7]基于中国剩余定理分别提出了一种可验证的秘密共享方案，但是这两种方案都无法阻止腐败的分发者分发不一致的份额给参与者。2010年，Harn和Lin [8]提出了强的t-一致性和强可验证秘密共享的定义并构造了强可验证秘密共享方案。2007年，唐韶华[9]从电子招标系统的实际需求出发，采用多重门限的方法设计了指定人必须参与的秘密共享、以组为单位的秘密共享、指定组必须参与的秘密共享等算法解决了实际问题。2014年，Subba等[10]提出了基于中国剩余定理的多秘密共享方案，该方案是将多个秘密分发给不同的组，这样每个组都接收到为其准备的秘密，同时每个参与者的秘密份额可以重复使用。Harn和Miao [11]提出了基于中国剩余定理的带权重的秘密共享方案，该方案是一个门限秘密共享方案，同时每个参与者具有不同的权重，当参与重构的参与者的权重大于等于门限值才可以恢复秘密，小于门限值则无法恢复秘密，该方案通过对每个参与者的模数进行处理使得每个参与者的模数与其权重数相关。此外，Harn和Miao [12]提出了一种基于中国剩余定理的分层门限秘密共享方案，但是这个方案不是完备的，并且生成满足特定要求的素数成本较高。2015年，Dong [13]利用中国剩余定理和RSA加密构造了秘密共享方案，该方案基于离散对数问题假设，不需要分发者和参与者的安全信道，同时参与者可以自行选择自己的秘密份额。2018年，Ning等[14]首次提出了基于多项式环的中国剩余定理的秘密共享方案，方案利用素性检测来查找两两互素的多项式作为参与者的模数，并且该方案是理想和完备的，该方案指出了Shamir的秘密共享方案是其方案的一个特例，将基于中国剩余定理的秘密共享方案和Shamir的秘密共享方案联系起来了。2022年，Wu等[15]指出Ning等[14]方案产生互素多项式非常耗时，导致效率低下。因此，Wu等在不检查多项式不可约性的情况下，通过直接生成互素多项式构造了基于多项式环上的中国剩余定理的秘密共享方案，并利用公因子构建对称的安全信道并且实现消息验证，确保收到的消息是正确的。

另一方面，随着互联网 + 智慧医院的建设，医院业务架构愈加复杂，业务对接众多外部数据使用单位，存在有众多对外数据服务接口。由于医院数据中包含大量高价值、高敏感的个人隐私信息，例如某些病人的个人信息，病人的病历档案数据等。因此医院数据安全治理工作任务重、难度大。Health Level Seven International (HL7)定义了快速医疗保健互操作性资源(FHIR, Fast Healthcare Interoperability Resources)标准，以有效地交换和集成各种医疗机构(如诊所、初级保健医生、保险公司、医院等)之间的电子医疗保健数据[16]。2023年，Yang等[17]为解决在多医院环境中使用FHIR的安全性问题，分别提出了基于群组的秘密共享方案(GSS, Group-Based Secret Sharing)和基于指数的群组秘密共享方案(EGSS, Exponential-Based Group Secret Sharing Scheme)，方案基于多项式和ElGamal密码系统，在区块链上进行验证。但是该方案存在安全漏洞：在所提出的指定一个参与者的方案中，不需要指定的参与者，其他大于门限值的参与者可以合谋恢复原始秘密，无法达到声称的安全性。

因此，本文基于中国剩余定理与RSA加密方案，设计了两个指定参与者的秘密共享方案，其中方案一是指定一个参与者的秘密共享方案；方案二是指定多个参与者的秘密共享方案。本文提出的方案可以用于下面场景：假设有一位病人甲，他因病到医院A就诊，完成诊疗后其病历数据由A医院保管并储存在A的病历数据库。但A医院A的医疗条件无法治愈甲的疾病，此时甲要去医院B和C进一步就诊治疗，由于甲先前在医院A就诊过，那么医院B和C可以将其在医院A就诊时的病历作为参考，即医院B和C需要访问医院A的数据库以获取甲的病历数据。当医院B和C想要访问甲的病历数据时医院A的授权，可以用秘密共享方案实现医院B和C对甲的病例数据的访问，但是为保护数据的隐私性，在共享时需要医院A的授权，也就是说，在秘密共享的重构阶段一定需要医院A的参与才可以使医院B和C得到甲的病例数据，即在重构阶段一定需要医院A的秘密份额才可以确保医院B和C恢复秘密。这是指定一个参与者(医院A)的秘密共享方案的场景，当医院B和C获取了甲的病历数据时，当新的医院D想要获取甲的病历数据，在秘密共享方案的重构阶段就一定需要A、B和C的秘密份额才可以恢复秘密。因此，指定一个参与者的情况可以推广到指定多个参与者。

本文主要贡献如下所示：

1) 通过利用RSA加密算法，基于中国剩余定理分别构造了指定一个参与者和指定多个参与者的门限秘密共享方案，其中指定的参与者可自行选择值作为自己的私钥，不需要在分发者和参与者之间建立安全信道，并且在重构阶段其他参与者可以验证指定参与者的份额的正确性。

2) 通过对方案安全性与性能分析表明，该方案是安全的，能够同时具备可验证性、指定参与者参与重构的功能。

2. 预备知识

本节主要介绍中国剩余定理和Asmuth-Bloom的秘密共享方案。

2.1. 中国剩余定理(CRT, Chinses Remainder Theorem)

定义1 (中国剩余定理[18]) 随机选择两两互素的整数$m_1,m_2,\cdots ,m_n$ ，对于任意的整数$a_1,a_2,\cdots ,a_n$ ，满足$a_i\in {\mathbb{Z}}_{m_i}$ ($i=1,2,\cdots ,n$ )，${\mathbb{Z}}_{m_i}$ 为整数模$m_i$ 的剩余类环，则下列同余方程组

$\{\begin{array}{c}X\equiv a_1\left(\mathrm{mod}{m}_1\right),\\ X\equiv a_2\left(\mathrm{mod}{m}_2\right),\\ ⋮\\ X\equiv a_n\left(\mathrm{mod}{m}_n\right).\end{array}$

在模$M=m_1\cdot m_2\cdot \cdots \cdot m_n$ 下有唯一解，解为$X={\displaystyle \sum _{i=1}^n{a}_i{M}_i}{y}_i\left(\mathrm{mod}M\right)$ ，其中$M_i=M/m_i$ ，$y_i=M_i^{-1}\left(\mathrm{mod}{m}_i\right)$ ，

$X=CRT\left(a_1,a_2,\cdots ,a_n\right)$ 。

2.2. Asmuth-Bloom的秘密共享方案

本小节介绍Asmuth-Bloom的$\left(t,n\right)$ 门限秘密共享方案，具体过程分为以下两个阶段：

• 秘密分发阶段

• D选择两两互素的正整数$m_0,m_1<m_2<\cdots <m_n$ 并且满足${\displaystyle \prod _{i=0}^t{m}_i}>m_0{\displaystyle \prod _{i=1}^{t-1}{m}_{n-i+1}}$ 。

• D选取秘密$s\in \left(0,m_0-1\right)$ ，并选取随机的整数p使得$s+p{m}_0\in \left({\displaystyle \prod _{i=n-t+2}^n{m}_i},{\displaystyle \prod _{i=1}^t{m}_i}\right)$ 。

• D计算$s_i=s+p{m}_0\left(\mathrm{mod}{m}_i\right)$ 作为参与者$P_i\left(i=1,2,\cdots ,n\right)$ 的秘密份额，并通过安全信道发送给对应的参与者。

• 秘密重构阶段

• 假设进行重构的参与者为$P_1,P_2,\cdots ,P_t$ ，他们将各自的秘密份额集中起来可以得到下面的同余方程组

$\{\begin{array}{c}X\equiv s_1\left(\mathrm{mod}{m}_1\right),\\ X\equiv s_2\left(\mathrm{mod}{m}_2\right),\\ ⋮\\ X\equiv s_t\left(\mathrm{mod}{m}_t\right).\end{array}$

• 利用中国剩余定理可以得到在区间$\left[0,{\displaystyle \prod _{i=1}^t{m}_i-1}\right]$ 内有唯一解，记为$x_0$ ，又因为$s+p{m}_0$ 同样满足上述的同余方程并且$s+p{m}_0$ 也在区间$\left[0,{\displaystyle \prod _{i=1}^t{m}_i-1}\right]$ 内，由解的唯一性可以得到$s+p{m}_0$ $=x_0$ ，并可以通过$s=x_0\left(\mathrm{mod}{m}_0\right)$ 恢复出秘密。

3. Yang等的方案和安全性分析

本节分析Yang等[17]的指定一个参与者的秘密共享方案，其中3.1节介绍具体方案，3.2节对Yang等的指定一个参与者的秘密共享方案的安全性漏洞给出一个具体示例分析。

3.1. Yang等方案回顾

Yang等[17]方案中的指定一个参与者的秘密共享方案是一个$\left(t,n\right)$ 门限秘密共享方案，有n个参与者$\left\{P_1,P_2,\cdots ,P_n\right\}$ ，该方案在重构阶段需要指定参与者$P_{ID}$ 的参与才能够恢复秘密，否则就算多于t个参与者也无法恢复秘密，下面介绍方案的细节：

• 秘密分发阶段

• D随机选取一个$t-1$ 次多项式

$f\left(x\right)=a_0+a_{1}x+a_2{x}^2+\cdots +a_{t-1}{x}^{t-1}\left(\mathrm{mod}p\right)$ ，

其中秘密$s=a_0$ 且$a_1,a_2,\cdots ,a_{t-1}\in {\mathbb{F}}_p$ ，p为一个素数。

• 对于$1\le i\le n$ ，当$i=ID$ 时，D计算秘密份额$s_i=f\left(ID\right)$ ，当$i\ne ID$ 时，D计算秘密份额 $s_i=f\left(i\right)+f\left(ID\right)\left(\mathrm{mod}p\right)$ ，将$s_i$ 通过安全信道发给对应的参与者。

• 秘密重构阶段

• 在参与者收到对应的份额后，参与者$P_{ID}$ 和其他任意$t-1$ 个参与者共同合作可以恢复秘密。$P_{ID}$ 向其他参与重构的参与者发送秘密份额$s_i=f\left(ID\right)$ ，其他参与者可以通过$f\left(ID\right)$ 得到对应的$f\left(i\right)$ 。

• 参与者将得到的$f\left(i\right)$ 集中起来利用拉格朗日插值公式(1)计算得到

$f\left(x\right)={\displaystyle \sum _{i=1}^t{s}_i}{\displaystyle \prod _{j=1,j\ne i}^t\left(x-j\right)/\left(i-j\right)}\left(\mathrm{mod}p\right)$ ，

从而得到秘密$s=f\left(0\right)=a_0$ 。

3.2. Yang等方案安全性分析

本节用一个简单的(2,3)门限秘密共享方案来说明Yang等[17]指定一个参与者的秘密共享方案的安全性漏洞。

假设有三个参与者，记为A、B和C，并且假设C是指定的参与者，即重构时需要C的参与，否则A和B合谋无法恢复秘密，为说明Yang等[17]方案的安全隐患，给出A、B合谋而不需要C参与的情况下，成功恢复秘密的示例：

• 选取素数p，假设生成的多项式为$f\left(x\right)=a_0+a_{1}x\left(\mathrm{mod}p\right)$ ，C作为指定参与者拿到的秘密份额为$t_{ID}=f\left(3\right)=a_0+3a_1\left(\mathrm{mod}p\right)$ ，A拿到的秘密份额为$s_1=t_1+t_{ID}=f\left(1\right)+f\left(3\right)=2a_0+4a_1\left(\mathrm{mod}p\right)$ ，B拿到的秘密份额为$s_2=t_2+t_{ID}=f\left(2\right)+f\left(3\right)=2a_0+5a_1\left(\mathrm{mod}p\right)$ 。

• A和B将他们的秘密份额集中起来，可以得到一个方程组

$\{\begin{array}{l}2a_0+4a_1\left(\mathrm{mod}p\right)=s_1,\\ 2a_0+5a_1\left(\mathrm{mod}p\right)=s_2.\end{array}$

将$s_2-s_1$ 就可以得到多项式的系数$a_1$ 再代入原方程组就可以得到秘密$a_0$ ，重构过程不需要C的参与。即该方案无法达到所声明的安全性，无法满足指定参与者参与重构过程才能恢复原始秘密，因此Yang等[17]所构造的指定一个参与者的秘密共享方案存在安全隐患。

4. 方案设计

本节提出两个方案，方案一是指定一个参与者的秘密共享方案；方案二是指定多个参与者的秘密共享方案，两个方案都是$\left(t,n\right)$ 门限秘密共享，在初始化阶段，利用RSA公钥加密，由指定参与者选取自己的私钥并保管，计算公钥发送给分发者后由分发者公开相关参数，利用公开值，参与重构的参与者可以验证指定参与者的份额的正确性。

4.1. 方案一：指定一个参与者的秘密共享方案

• 初始化阶段

• 有n个参与者$\left\{P_1,P_2,\cdots ,P_n\right\}$ ，假设指定参与重构的参与者记为$P_{\Delta }$ ，$\Delta \in \left(1,2,\cdots ,n\right)$ ，将$P_{\Delta }$ 的份额记为$S_{\Delta }$ 。

• D选取两个大素数$p=2m+1$ ，$q=2n+1$ ，其中m和n也都为素数，且任何人都不能有效地分解因式$N=pq$ ，然后D选择整数g使得$1<g<N$ ，$\left(g,N\right)=1$ 且$\left(g\pm 1,N\right)=1$ ，$P_{\Delta }$ 从$\left[2,N\right]$ 中随机选取整数$s_{\Delta }$ ，计算$R_{\Delta }=g^{s_{\Delta }}\left(\mathrm{mod}N\right)$ 发送给D。

• D选取整数e满足$1<e<\phi \left(N\right)=\left(p-1\right)\left(q-1\right)$ ，使得$\left(e,\phi \left(N\right)\right)$ $=1$ ，D计算$S_0=g^e\left(\mathrm{mod}N\right)$ ，再用拓展的欧几里得算法计算唯一的整数h，其中$1<h<\phi \left(N\right)$ ，使得$eh\equiv 1\left(\mathrm{mod}\phi \left(N\right)\right)$ ，最后D公开g，N，$S_0$ ，h，$R_{\Delta }$ 。

• 秘密分发阶段

• D选择两两互素的正整数$m_0,m_1<m_2<\cdots <m_n$ 并且满足${\displaystyle \prod _{\text{i}=1}^t{m}_i}>m_0{\displaystyle \prod _{i=1}^{t-1}{m}_{n-i+1}}$ 。

• D选择秘密$s\in \left(0,m_0-1\right)$ ，并选取随机的整数p使得$s+p{m}_0\in \left({\displaystyle \prod _{i=n-t+2}^n{m}_i},{\displaystyle \prod _{i=1}^t{m}_i}\right)$ 。

• 对于$1\le i\le n$ ，当$i=\Delta$ 时，D计算份额${S^{\prime }}_{\Delta }=\left(s+p{m}_0\right)\left(\mathrm{mod}{m}_{\Delta }\right)\oplus R_{\Delta }^e\left(\mathrm{mod}N\right)$ ，当$i\ne \Delta$ 时，D计算份额${S^{\prime }}_i=\left(s+p{m}_0\right)\left(\mathrm{mod}{m}_i\right)\oplus R_{\Delta }^e\left(\mathrm{mod}N\right)$ ，其中$\oplus$ 表示异或运算。将${S^{\prime }}_i$ 发给对应的参与者。

注意，由于指定参与者$P_{\Delta }$ 与分发者D在初始化阶段利用RSA加密使得方案的原始秘密份额$S_i$ 和$S_i$ 被隐藏在秘密份额${S^{\prime }}_i$ 和${S^{\prime }}_{\Delta }$ ，所以此方案在秘密分发阶段不需要安全信道。

• 秘密重构阶段

• 假设参与者$P_1,P_2,\cdots ,P_{t-1},P_{\Delta }$ 参与重构阶段想要恢复秘密，$P_{\Delta }$ 利用公开值$S_0$ 和自己的私钥$s_{\Delta }$ 计算$R_{\Delta }^e=S_0^{s_{\Delta }}$ 向其他参与者公开值$R_{\Delta }^e$ 。

• 验证阶段：其他参与者收到值$R_{\Delta }^e$ 后可以验证式子$R_{\Delta }^{eh}\equiv R_{\Delta }\left(\mathrm{mod}N\right)$ 是否成立，若成立，则进行下一步，若不成立，则停止重构。

• 所有参与者验证通过后，将份额${S^{\prime }}_i$ 与公开值$R_{\Delta }^e$ 做异或运算并将t个参与者的份额集中起来可以得到下面的同余方程组

$\{\begin{array}{c}x\equiv {S^{\prime }}_1\oplus R_{\Delta }^e\left(\mathrm{mod}N\right)\left(\mathrm{mod}{m}_1\right),\\ x\equiv {S^{\prime }}_2\oplus R_{\Delta }^e\left(\mathrm{mod}N\right)\left(\mathrm{mod}{m}_2\right),\\ ⋮\\ x\equiv {S^{\prime }}_{\Delta }\oplus R_{\Delta }^e\left(\mathrm{mod}N\right)\left(\mathrm{mod}{m}_{\Delta }\right).\end{array}$

• 利用中国剩余定理可以得到在区间$\left[0,{\displaystyle \prod _{i=1}^t{m}_i-1}\right]$ 内有唯一解，记为$x_0$ ，又因为$s+k{m}_0$ 同样满足上述的同余方程并且$s+k{m}_0$ 也在区间$\left[0,{\displaystyle \prod _{i=1}^t{m}_i-1}\right]$ 内，由解的唯一性可以得到$s+k{m}_0$ $=x_0$ ，并可以通过$s=x_0\left(\mathrm{mod}{m}_0\right)$ 恢复出秘密。

4.2. 方案二：指定个参与者的秘密共享方案

下面将指定一个参与者的方案推广到指定$k\left(2\le k\le t-1\right)$ 个参与者，具体过程如下：

• 初始化阶段

• 有n个参与者$\left\{P_1,P_2,\cdots ,P_n\right\}$ ，假设指定参与重构的参与者记为$P_{{\Delta }_1},P_{{\Delta }_2},\cdots ,P_{{\Delta }_k}$ ，${\Delta }_i\in \left(1,2,\cdots ,n\right),\left(i=1,2,\cdots ,t\right)$ ，将$P_{{\Delta }_i}$ 的份额记为$S_{{\Delta }_i}$ 。

• D选取两个大素数$p=2m+1$ ，$q=2n+1$ ，其中m和n也都为素数，且任何人都不能有效地分解因式$N=pq$ ，然后D选择整数g使得$1<g<N$ ，$\left(g,N\right)=1$ 且$\left(g\pm 1,N\right)=1$ ，$P_{\Delta }$ 从$\left[2,N\right]$ 中随机选取

整数$s_{{\Delta }_i}$ ，计算$R_{{\Delta }_i}=g^{s_{{\Delta }_i}}\left(\mathrm{mod}N\right)$ 发送给D，D在收到$R_{{\Delta }_i}$ 后要确保对于$i\ne j$ 时，$R_{{\Delta }_i}\ne R_{{\Delta }_j}$ ，否则需要指定参与者重新选择直到$R_{{\Delta }_i}\ne R_{{\Delta }_j}$ 为止。

• D选取整数e满足$1<e<\phi \left(N\right)=\left(p-1\right)\left(q-1\right)$ ，使得$\left(e,\phi \left(N\right)\right)$ $=1$ ，D计算$S_0=g^e\left(\mathrm{mod}N\right)$ ，再用拓展的欧几里得算法计算唯一的整数h，其中$1<h<\phi \left(N\right)$ ，使得$eh\equiv 1\left(\mathrm{mod}\phi \left(N\right)\right)$ ，最后D公开g，N，$S_0$ ，h，$R_{\Delta }$ 。

• 秘密分发阶段

• D选择两两互素的正整数$m_0,m_1<m_2<\cdots <m_n$ 并且满足${\displaystyle \prod _{\text{i}=1}^t{m}_i}>m_0{\displaystyle \prod _{i=1}^{t-1}{m}_{n-i+1}}$ 。

• D选择秘密$s\in \left(0,m_0-1\right)$ ，并选取随机的整数p使得$s+p{m}_0\in \left({\displaystyle \prod _{i=n-t+2}^n{m}_i},{\displaystyle \prod _{i=1}^t{m}_i}\right)$ 。

• 对于指定参与者$P_{{\Delta }_1},P_{{\Delta }_2},\cdots ,P_{{\Delta }_k}$ ，${\Delta }_i\in \left(1,2,\cdots ,n\right),\left(i=1,2,\cdots ,t\right)$ ，D计算秘密份额${S^{\prime }}_{{\Delta }_i}=\left(s+p\cdot m_0\right)\left(\mathrm{mod}{m}_{{\Delta }_i}\right)\oplus R_{{\Delta }_1}^e\oplus R_{{\Delta }_2}^e\oplus \cdots \oplus R_{{\Delta }_k}^e\left(\mathrm{mod}N\right)$ ，对于剩下的参与者，D计算秘密份额${S^{\prime }}_i=\left(s+p\cdot m_0\right)\left(\mathrm{mod}{m}_i\right)\oplus R_{{\Delta }_1}^e\oplus R_{{\Delta }_2}^e\oplus \cdots \oplus R_{{\Delta }_k}^e\left(\mathrm{mod}N\right)$ ，其中$\oplus$ 表示异或运算。将${S^{\prime }}_{{\Delta }_i}$ 和${S^{\prime }}_i$ 发给对应的参与者。

注意，由于指定参与者$P_{{\Delta }_i}$ 与分发者D在初始化阶段利用RSA加密使得方案的原始秘密份额$S_i$ 和$S_{\Delta }$ 被隐藏在秘密份额${S^{\prime }}_i$ 和${S^{\prime }}_{{\Delta }_i}$ 中，所以此方案在秘密分发阶段不需要安全信道。

• 秘密重构阶段

• 假设指定的k个参与者$P_{{\Delta }_1},P_{{\Delta }_2},\cdots ,P_{{\Delta }_k}$ 和剩下的任意$t-k$ 个参与者一起参与重构。每个指定参与者利用公开值$S_0$ 和各自的私钥$s_{{\Delta }_i}$ ，分别计算$R_{{\Delta }_i}^e=S_0^{s_{{\Delta }_i}}$ ，并向其他参与者公开值$R_{{\Delta }_i}^e$ 。

• 验证阶段：其他参与者收到值$R_{{\Delta }_i}^e$ 后，通过验证$R_{{\Delta }_i}^{eh}\equiv R_{{\Delta }_i}\left(\mathrm{mod}N\right)$ 是否成立，若成立，则进行下一步；若不成立，则停止重构。

• 所有参与者通过验证后，将份额${S^{\prime }}_i$ 与所有公开值$R_{{\Delta }_i}^e$ 作异或运算并将t个参与者的份额集中起来可以得到同余方程组

$\{\begin{array}{c}x\equiv {S^{\prime }}_{{\Delta }_1}\oplus R_{{\Delta }_1}^e\oplus R_{{\Delta }_2}^e\oplus \cdots \oplus R_{{\Delta }_k}^e\left(\mathrm{mod}N\right)\left(\mathrm{mod}{m}_{{\Delta }_1}\right),\\ x\equiv {S^{\prime }}_{{\Delta }_2}\oplus R_{{\Delta }_1}^e\oplus R_{{\Delta }_2}^e\oplus \cdots \oplus R_{{\Delta }_k}^e\left(\mathrm{mod}N\right)\left(\mathrm{mod}{m}_{{\Delta }_2}\right),\\ ⋮\\ x\equiv {S^{\prime }}_{{\Delta }_k}\oplus R_{{\Delta }_1}^e\oplus R_{{\Delta }_2}^e\oplus \cdots \oplus R_{{\Delta }_k}^e\left(\mathrm{mod}N\right)\left(\mathrm{mod}{m}_{{\Delta }_k}\right),\\ x\equiv {S^{\prime }}_{i_1}\oplus R_{{\Delta }_1}^e\oplus R_{{\Delta }_2}^e\oplus \cdots \oplus R_{{\Delta }_k}^e\left(\mathrm{mod}N\right)\left(\mathrm{mod}{m}_{i_1}\right),\\ x\equiv {S^{\prime }}_{i_2}\oplus R_{{\Delta }_1}^e\oplus R_{{\Delta }_2}^e\oplus \cdots \oplus R_{{\Delta }_k}^e\left(\mathrm{mod}N\right)\left(\mathrm{mod}{m}_{i_2}\right),\\ ⋮\\ x\equiv {S^{\prime }}_{i_{t-k}}\oplus R_{{\Delta }_1}^e\oplus R_{{\Delta }_2}^e\oplus \cdots \oplus R_{{\Delta }_k}^e\left(\mathrm{mod}N\right)\left(\mathrm{mod}{m}_{i_{t-k}}\right).\end{array}$

• 利用中国剩余定理可以得到在区间$\left[0,{\displaystyle \prod _{i=1}^t{m}_i-1}\right]$ 内有唯一解，记为$x_0$ ，又因为$s+k{m}_0$ 同样满足上述的同余方程并且$s+k{m}_0$ 也在区间$\left[0,{\displaystyle \prod _{i=1}^t{m}_i-1}\right]$ 内，由解的唯一性可以得到$s+k{m}_0$ $=x_0$ ，并可以通过$s=x_0\left(\mathrm{mod}{m}_0\right)$ 恢复出秘密。

5. 方案分析

本节对第4节提出的方案进行安全性分析，由于方案二可以看作是方案一的一般情况，所以只对方案二进行安全性分析。

定理1 若方案二中参与重构的参与者数量大于等于t并且包含指定的k个参与者$P_{{\Delta }_i}$ ，则参与重构的参与者按照重构阶段步骤可以恢复秘密。

证明：该方案的秘密重构过程主要分为两个步骤，第一步由指定参与者$P_{{\Delta }_i}$ 向其他参与重构的参与者公开值$R_{{\Delta }_i}^e$ ，其他参与重构的参与者收到公开值后，验证式子$R_{{\Delta }_i}^{eh}\equiv R_{{\Delta }_i}\left(\mathrm{mod}N\right)$ 是否成立来确保$P_{{\Delta }_i}$ 没有欺骗行为，所有重构的参与者通过验证后，进行重构的第二步，参与者将自己的秘密份额${S^{\prime }}_i$ 与所有的公开值$R_{{\Delta }_i}^e$ 做异或运算后，可以得到原始的秘密份额，得到原始秘密份额后，大于等于t个参与者将他们的秘

密份额集中起来，基于Asmuth-Bloom的门限秘密共享方案和中国剩余定理可以恢复出秘密s。

定理2 若方案二中参与重构的参与者数量大于等于t，但不全包含指定的k个参与者$P_{{\Delta }_i}$ ，则参与重构的参与者无法恢复秘密。

证明：不妨假设有$k-1$ 个指定参与者属于参与重构的参与者子集中，则剩下的参与者数量大于等于$t-k+1$ ，也大于等于$t-k$ ，这里不妨假设第k个指定的参与者$P_{{\Delta }_k}$ 不属于参与重构的参与者子集中，由

于$P_{{\Delta }_k}$ 没有参与重构，则其他参与者无法得到公开值$R_{{\Delta }_k}^e$ ，另一方面，又因为大整数的素因子分解是困难的，所以参与者无法从公开值N中得到系统参数e，从而也无法得到公开值$R_{{\Delta }_k}^e$ ，而得不到公开值$R_{{\Delta }_k}^e$ 就无法计算得到每个参与者的原始秘密份额，也就无法恢复秘密s。

定理3 若方案二中重构阶段参与者数量小于t，则参与重构的参与者无法恢复秘密。

证明：记参与者重构的参与者子集为$\Gamma$ ，考虑两种情况：

• 情况1：指定参与者$P_{{\Delta }_1},P_{{\Delta }_2},\cdots ,P_{{\Delta }_k}\in \Gamma$ ，由于指定的k个参与者都参与重构，从而参与重构的参与者可以利用公开值$R_{{\Delta }_i}^e$ 计算出原始的秘密份额，但由于参与重构的参与者数量小于t，不妨假设由$t-1$ 个参与者参与重构，则他们在得到原始秘密份额后，利用中国剩余定理可以得到在模$t-1$ 个模数$m_i$ 下的唯一解，记为$x_0$ ，但是根据${\displaystyle \prod _{\text{i}=1}^t{m}_i}>m_0{\displaystyle \prod _{i=1}^{t-1}{m}_{n-i+1}}$ ，可以得到秘密s为$x_0$ 的正整数倍并且这$t-1$ 个参与者恢复秘密的概率为$\frac{1}{m_0}$ 。

• 情况2：指定参与者$P_{{\Delta }_1},P_{{\Delta }_2},\cdots ,P_{{\Delta }_k}$ 不全属于$\Gamma$ 不妨假设有$k-1$ 个指定参与者属于参与重构的参与者子集中，则根据定理2，参与重构的参与者无法恢复秘密s。

综上所述，少于t个参与者参与重构无法恢复秘密。

6. 方案对比

本节将本文方案二与文献[9]方案和文献[17]方案进行对比，后者两个方案都是基于多项式构造，方案二基于中国剩余定理构造。文献[9]方案对指定k个参与者和剩下的$n-k$ 个参与者分别构造$\left(k,k\right)$ 和$\left(t-k,n-k\right)$ 门限方案，通过将两个方案的秘密相关联达到指定参与者的目的。文献[17]方案利用秘密共享方案的同态性，让每个参与者作为分发者向其他参与者分发秘密份额，其他参与者的秘密份额中包含指定参与者的秘密份额，以达到指定参与者的目的，份额的验证在区块链上进行。但文献[9]方案和文献[17]方案都需要分发者和参与者间的安全信道。

表1给出了三个方案的安全属性对比，本文方案二利用RSA公钥加密验证指定参与者的份额，在分发阶段指定参与者与分发者交互生成私钥，所以在分发阶段不需要参与者和分发者的安全信道，并且可以满足安全性。

Table 1. Security property comparisons among the secret sharing with the designed multiple participants

表1. 指定多个参与者的秘密共享方案的安全属性比较

方案	可验证	安全信道	安全性
唐韶华方案[9]	×	需要	√
Yang等方案[17]	√	需要	×
本文方案二	√	不需要	√

符号说明：√表示具备性质；×表示不具备性质。

表2给出了三个方案的效率对比，由于在重构阶段要解同余方程组，所以方案二的计算复杂度为$O\left(t{m}^2\right)$ ，其中m为每个参与者模数的大小。但方案二的公开值个数比文献[9]方案和文献[17]方案的公开值更少。

Table 2. Efficiency comparisons among the secret sharing with the designed multiple participants

表2. 指定多个参与者的秘密共享方案的效率比较

方案	公开值个数	计算复杂度
唐韶华方案[9]	$2n+4$	$O\left(t^2\right)$
Yang等方案[17]	$nk-n$	$O\left(t^2\right)$
本文方案二	$n+k+5$	$O\left(t{m}^2\right)$

符号说明：t为方案门限值；m为每个参与者模数的大小。

7. 总结

本文基于中国剩余定理和RSA公钥密码系统，提出了两个指定参与者必须参与重构的秘密共享方案。方案一是指定一个参与者的秘密共享方案，方案二是指定多个参与者的秘密共享方案。与其他方案相比，本文方案利用RSA公钥加密实现在分发阶段不需要参与者和分发者间的安全信道和在重构阶段可验证参与者份额的功能。本文方案能满足病人病历在医院间数据库安全共享的实际应用需求。

基金项目

福建省高校产学合作科技计划项目(2023H6012)。

NOTES

^*通讯作者。