下载:
-
开放科学（资源服务）标识码（OSID）：
-
密钥管理作为网络系统安全的基石，其可靠性直接影响整个系统的安全架构。当前主流的对称加密与非对称加密技术均采用单一实体集中保管密钥的模式，这种架构不仅存在密钥泄露的风险，还会因为管理节点被攻破而引发系统性安全崩塌。为应对这一挑战，门限密码学应运而生[1-2]。该技术通过将密钥分割为多个份额并分发给不同参与者，要求超过预设门限值的参与者协作方可恢复密钥，从根本上杜绝了单点失效风险。研究表明，门限方案在区块链[3]、物联网[4]、隐私计算等领域展现出独特优势，其安全性提升效果已在分布式存储、多方安全计算等场景中得到验证。
1979年，文献[1]提出了一种基于多项式插值的门限方案，该方案基于以下定理：给定二维平面的n个点(x1，y1)，…，(xn，yn)，这些点的x坐标都不相同，即xi≠xj。如果i≠j，1≤i，j≤n，那么有且只有一个t-1阶多项式q(x)满足q(xi)=yi，1≤i≤n[5]。对于秘密信息K，随机选取t-1阶多项式q(x)=a0+a1x+a2x2+，…+at-1xt-1，使得a0=K，然后计算D1=q(1)，D2=q(2)，…，Dn=q(n)。只要知道D1，…，Dn中的t个，即可通过插值法找出多项式q(x)的系数，进而计算出q(0)，得到K=q(0)。如果只知道D1，…，Dn中的t-1个或更少，则不能求出多项式q(x)的系数，因此不能计算出正确的秘密信息K。为突破传统门限方案的性能瓶颈，文献[6]提出基于向量空间的创新性门限方案。该方案通过线性代数框架重构秘密管理：首先构建d维向量空间，将原始秘密信息编码为特定向量；随后为每个参与者生成与该向量空间正交的子空间投影向量作为秘密份额，其数学本质是通过线性变换实现秘密信息的分割。当t个及以上参与者协作时，其持有的投影向量可通过线性组合重构原始向量空间，从而解码出初始秘密信息。相较于传统多项式插值方法，该方案依托向量空间的正交性特征，将秘密信息的恢复过程转化为高效的矩阵运算，其计算复杂度降低至O(t2)量级。这种方案的优势在于其数学结构清晰，计算效率高，在分布式安全计算中具有重要应用。
1983年，文献[7]提出了一种基于中国剩余定理的方案(CRT)。该方案首先选择一个大整数N作为模数，并将其分解为互质的数n1，n2，…，nk，满足N=n1×n2×…×nk。对于秘密信息SE，计算SEi≡SE mod ni，并将SEi分发给第i个参与者。当至少t个参与者提供各自的SEi时，利用CRT可以唯一确定SE mod N，从而恢复秘密信息。该方案具有高安全性和计算效率，广泛应用于分布式系统中的安全计算和密钥管理。
在基础理论体系不断完备的同时，门限方案的设计范式逐步向多元化演进。从数学工具维度看，研究者相继提出了基于矩阵乘法的分布式验证架构[8]、依托多维向量投影的轻量化方案[9]，以及采用矢量空间线性组合的高效方法[10]。在新型计算模型方面，细胞自动机方案[11]展现了离散动力学系统的独特优势，而多级秘密共享机制[12-13]通过多项式插值扩展实现了细粒度权限控制。值得关注的是，单调跨度程序[14]与有理正态曲线[15]等代数几何工具的引入，进一步丰富了方案的理论边界。2019年后，随着量子计算技术的快速发展，传统的公钥密码体系面临着被量子算法破解的风险。因此，抗量子密码学(Post-Quantum Cryptography，PQC)成为密码学研究的核心攻关方向之一。在这一背景下，基于格密码(Lattice-based Cryptography)的方案[16]因其在理论上的安全性和实际应用中的潜力，受到了广泛关注。近5年的研究更呈现出跨学科融合态势：2021年，文献[17]将Shamir阈值机制与区块链智能合约结合，通过STCChain方案实现密钥分片的防篡改存证；2023年，文献[18]构建的线性哈希阈值协议，首次在离散对数与RSA双重假设下达成两轮通信安全认证；2024年，文献[19]基于类群同态加密的创新设计解决了动态门限调整中的密钥更新难题，文献[20]提出的分层量子密钥共享方案通过引入理性参与者博弈模型并使用量子相移运算来分发和重构密钥，使方案能够抵御一系列典型的外部攻击，并能够检测参与者的伪造和串通攻击。
尽管已有研究取得显著进展，但现有方案在资源受限场景的适用性仍存在关键瓶颈，例如Shamir方案虽然具有信息论的安全特性，但是其O(t2)的插值复杂度难以满足实时性要求；Blakley方案的高维矩阵运算产生了O(t3)的计算开销，制约其在边缘设备的部署；中国剩余定理方案在动态门限调整时面临模数重构难题。更本质地，现有方法普遍依赖连续数学空间操作，这种范式性特征导致算法复杂度与安全强度呈正相关，尚未出现能同时满足轻量化与强安全需求的新型理论框架。基于此，本文提出基于集合分配的安全门限方案STSA(Secure Threshold Scheme based on ASC)，主要贡献包括：
1) 提出一种简单、易理解、易实现的基于集合分配的安全(t，n)门限方案。STSA使用集合分配替代复杂数学结构，通过离散集合的逻辑划分替代多项式、超平面或向量空间，避免高次插值、矩阵运算等复杂操作。利用集合交集运算恢复秘密，复杂度可降至O(t)。
2) 在数学上证明了提出的STSA门限方案的正确性和安全性，同时通过程序验证了该方案的正确性和可行性。
3) 提出的STSA方案为该领域引入了新的思路，是相关研究的补充和拓展。STSA采用轻量化设计减少模数运算与浮点计算需求，适用于物联网终端、边缘设备等资源受限场景。集合分配机制可无缝集成至多方计算协议与零知识证明框架，为隐私计算生态提供基础工具。
4) 使用Python实现了STSA，同时也复现了其他一些门限方案。实现的源代码都进行了公开(
https://gitee.com/Tinff/stsa )，供其他学者对我们的工作进行验证，并希望激起更多的研究和创新。
全文HTML
-
(t，n)门限方案是一种在n个参与者之间分配密钥的方法，任何t(门限值，t＞1)个或多于t个的参与者都可以合作重构密钥，如果少于t个则不能进行重构。
定义1 参与者(Participant)
参与者是指参与门限方案的个人或其他实体(例如计算机、通信节点等)。
定义2 秘密信息(Secret Information，SI)
(t，n)门限方案的秘密信息是需要私密传输的数据。可以通过一些方法将原始数据或在原始数据基础上计算出的派生信息分割为n个部分，分配给n个参与者。系统的密钥是一种秘密信息。
定义3 分配密钥(Key Assigned，KA)
指(t，n)门限方案将密钥分配给各个参与者，任何不少于t个的参与者，将其持有的分配密钥KA组合在一起，可以恢复出秘密信息SI。
-
为了实现(t，n)门限方案，可以选定一些元素ei构成一个集合全集U={ei}，i=1、2…，使集合中的元素两两不同。集合的全体元素共同用于生成秘密信息。将集合中的元素ei分配给n个参与者(p1，p2，…，pn)，分得的集合分别为S1、S2、…、Sn。n个参与者组成的集合为
$ S=\bigcup\limits_{j}^{{}}{{{S}_{j}}}$ ，1≤j≤n，每个元素ei可以多次分配给不同的参与者。只需保证分配后t个或更多的参与者将各自持有的集合合并在一起，去除重复的元素后，能够恢复出全集U。因此，可以考虑将集合U中的元素ei只分配给其中的t-1个参与者，这样就保证在少于t个参与者的情况下，不能恢复出全集U。而t个或更多参与者合作，能够恢复出全集U。
-
步骤1 随机选取两两不同的N=Cnt-1个元素组成集合U={ei}，1≤i≤N。
步骤2 记录N=Cnt-1种组合的排列C=[Ci]，
步骤3 将元素ei分配给pj，当且仅当有序集合Ci中ci，j=0，即pj分配到的元素组成的集合为Sj。
示例：构造基于集合划分的(2，3)门限方案
步骤1 选取两两不同的N=C31=3个元素组成全集U={7，11，23}。
步骤2 记录N=Cnt-1=3种组合的有序排列：
步骤3 将元素ei分配给pi，当且仅当有序集合Ci中ci=0，1≤i≤3。
得到表 1所示的分配方案。
分配的结果为：
如果少于两个参与者则不能恢复出集合U。
当不少于2时给出自己的集合，
-
定理1 ASC方法能成功恢复全集U。
证明 按照分配方法，集合U中的任意元素ei分配给了n个参与者中的n-t+1个参与者，1≤i≤N。当不少于t个参与者给出所持有的集合时，至少其中有一个参与者具有元素ei。从而在它们组合的集合U′中会存在该元素。
因为以上元素ei具有任意性，因此在集合U′中包含所有的元素ei，1≤i≤N。故U′=U。
定理2 ASC构造的门限方案是所用元素最少的方案。
证明 用反证法证明。
一方面，如果将全集U中的元素ek整体去掉，得到集合U′=U-{ek}。
假设使用ASC方法分配元素后，去掉集合U中的一个元素ek，仍能满足(t，n)门限方案。
选取其中的t个参与者，其中只有一个参与者具有元素ek。不失一般性，设该参与者为pv，1≤v≤n。
因为t个参与者所持有的集合，可以组合为集合U，所以除去pv持有的集合，其他t-1个参与者中，必定可以组合出除了元素ek之外的其他元素，即这t-1个参与者能够组合出U′=U-{ek}。此时其门限值不再是t，这与假设矛盾。
另一方面，如果从ASC方法产生的参与者原始集合S中将某一个元素ei去掉，那么S中将存在n-t个元素ei，有t个参与者没有分配到元素ei。如果刚好选中了没有分配到元素ei的这t个参与者，则会因为缺少元素ei，从而无法计算出秘密信息。
综合以上两方面可见ASC方法是所用元素最少的。
例如，用ASC方法构造的(5，6)门限方案如表 2所示，其中“√”表示分配，“×”表示未分配。
若去除元素e2，U′=U-{e2}={e1，e3，…，e15}。若选择p1、p2、p3、p5，则S1∪S2∪S3∪S5={e1，e3，…，e15}=U′。因此只要4个参与者给出所持的集合即可恢复出密钥集合U′。这时不满足门限值为5的条件，故不能去除元素e2。同理也不能去除其他的元素。
推论 构造(t，n)门限方案至少需要Cnt-1个元素。
证明 ASC方法将最少的元素个数分配给各个参与者。由定理1知，不能再缩减元素。因此，构造(t，n)门限方案至少需要Cnt-1个元素。
-
ASC方法在已知t和n的情况下，选取Cnt-1个元素来构造分配方案。有时为了增强安全性，可以使用d×Cnt-1个元素来构建加密方案。d为安全系数，d∈I+，d越大所需元素越多，整体安全性越好。
步骤1 使用ASC方法生成前1、…、Cnt-1个元素的分配方案。
步骤2 对于第Cnt-1+1、…、2Cnt-1个元素，可以将这些元素编号。对于编号为u的元素eu，按照元素eu mod (N+1)的分配方案进行分配。
步骤3 对于第2Cnt-1+1、…、3Cnt-1个元素，也采用步骤2操作进行分配，直到所有的元素分配完毕。
例如，d=3即安全系数为3时，用ASC-2方法构造的(5，6)门限方案如表 3所示，其中“√”表示分配，“×”表示未分配。
ASC-2的正确性证明如下。
定理3 ASC-2方法能成功恢复全集U。
证明 对于第1、…、Cnt-1个元素，采用ASC方法进行分配，因此能恢复出包含这些元素的集合U1。对于第Cnt-1+1、…、2Cnt-1个元素，对于编号为u的元素eu，按照元素eu mod (N+1)的分配方案进行分配Cnt-1+1≤u≤2Cnt-1。因此，这些元素将一一对应到1、…、Cnt-1各个元素的分配方法。也相当于采用ASC方法进行分配，因此能恢复出包含这些元素的集合U2。
同理，可以恢复出U3、…、Ud，进而可以得到全集U=
$ \bigcup\limits_{i=1}^{d}{{{U}_{i}}}$ 。
1.1. 设计思路
1.1.1. ASC(Allocation Scheme based on Combination)方法
1.1.2. 正确性证明
1.2. ASC-2方法
-
步骤1 输入门限值t，参与者数量n和安全系数d。
步骤2 选取两两不同的N(N=d*Cnt-1，d∈I+)个大质数组成全集U={ei}。通过元素相乘来生成秘密信息，Pkey=hash(∏{e|e∈U})。hash()为哈希函数(如SHA-256[21]等)。利用秘密信息Pkey对信息进行加密。
步骤3 按照ASC-2方法生成参与者原始集合S={Sj}，1≤j≤n。
步骤4 将参与者的原始集合Sj分配给参与者pj。
-
步骤1 对于参与者pj，利用自己的参与者原始集合Sj，将元素相乘得到生成信息Ij，Ij=
$ \prod\limits_{i}^{{}}{\{s|s\in {{S}_{j}}\}}$ ，1≤j≤n。步骤2 在计算秘密信息时，对于愿意参与的参与者，检查是否有参与者公开了生成信息，若没有，则公开自己的生成信息；若已有其他参与者公开了生成信息，则获取该信息。如果获取到多个生成信息，则选择数值最大的一个，记为I′。
步骤3 对自己的参与者原始集合中每个元素做除法，生成信息I′，如果余数不为零，则把这个元素值乘以生成信息，得到新的生成信息。如果余数为零，则忽略重新选取I′。对每一个元素都进行这样的处理，得到处理后的生成信息I″。若I″≠I′则公开I″。
步骤4 所有参与者都经过步骤1到步骤3的处理后，可以得到一个最大的生成信息Imax。如果有不少于t个参与者参与了以上过程，则Imax将是唯一的，可用于生成秘密信息Pkey=hash(Imax)。
-
定理4 RecoverProcess能正确地计算出Pkey。
证明 使用ASC-2方法生成各个参与者的原始集合Sj，1≤j≤n，当不少于t个参与者将自身Sj组合在一起时，可以得到全集U。
对于有t个参与者的秘密信息恢复，分别记为p1、p2、…、pt，1≤t≤n。它们一起进行RecoverProcess操作。
第1个参与者p1计算出生成信息I1，并公开给下一个参与者：
第2个参与者p2收到生成信息I1，计算出生成信息I2，并公开给下一个参与者：
第3个参与者p3收到生成信息I2，计算I3，并公开给下一个参与者：
重复以上过程，最后得到：
可见Pkey=hash(It)。
有多于t个参与者参与秘密信息的恢复时，计算出的秘密信息也将是Pkey。
因此RecoverProcess能正确地计算出Pkey。
-
在恢复秘密信息的过程中，参与者会给出一些信息，这些信息如果设计不当，可能会泄露自己的参与者原始集合。进而导致身份的泄露。此处，作者证明STSA的安全性，保证不会导致泄露这些信息。
因为选择的元素个数N=d*Cnt-1，d∈I+。可以保证分配给各个参与者的原始集合，两两之间至少有两个元素是不相同的。
每个参与者公开出去的是元素的乘积信息。如果想要通过该信息恢复参与者的原始集合，则要进行大数分解。因为选择的是大质数，要分解至少两个大质数的乘积，是一个困难问题[22-23]。RSA算法也是基于分解大素数的困难性进行设计的[24]。在当前计算能力条件下，STSA具有安全性。所以其他参与者都不能将公开的生成信息还原为参与者的原始集合S。
最后，得到的秘密信息是一个经过哈希运算后的秘密信息Pkey，Pkey也不能反向计算出全集U。
因此，从STSA协议公开的生成信息不能恢复参与者原始集合，也不能找出参与者的身份。
2.1. STSA方案
2.1.1. 集合划分和计算秘密信息Pkey
2.1.2. 参与者合作计算秘密信息的恢复过程RecoverProcess
2.2. 恢复过程RecoverProcess的正确性证明
2.3. STSA的安全性证明
-
本节通过程序验证第1节提出的ASC方法和第2节提出的STSA安全门限方案的正确性和可行性。程序主要包括秘密信息分配、恢复过程以及安全性分析，确保在不少于t个参与者的情况下能够正确恢复秘密信息，并在少于t个参与者的情况下无法恢复。
-
本节使用Python实现STSA安全门限方案，针对这样一个应用场景：在控制系统中存在多个控制器，对于一些关键操作，需要得到不低于门限值个数的控制器允许，才能执行某些关键操作，即使用STSA安全(t，n)门限方案，当有不少于t个控制器允许执行时，系统才执行关键操作。同时保证控制器隐私安全。不能暴露有哪些控制器参与，也不能暴露参与控制器所持有的分配密钥。
-
设控制器个数为n，门限值为t，安全系数为d。为了安全性可以把质数选得更大。更大的质数需要更多的时间来完成计算。元素分配并计算秘密信息的伪代码如下。
step 1： input(t，n，d) #输入参数门限值t，参与者数量n，安全系数d
step2： N=CalCombiNum(n，t-1) #计算组合数量
step3： PrimeNumbers=GenPrimeNumbers(d*N) #选择d*N个大质数
step4： pAssignedElements=ASC-2(PrimeNumbers) #将d*N个大质数按照ASC-2方法分配给n个参与者
step5： Pkey=1
step6： for i in range(0，len(PrimeNumbers)，1)：
step7： Pkey *=PrimeNumbers[i]
step8： Pkey=hashlib.sha256(str(Pkey).encode(‘utf8’).hexdigest() #step5-8计算加密秘密信息，并用于对信息的加密
-
在具有至少t个参与者进行秘密信息恢复时，恢复秘密信息的伪代码如下。
step1： defRecoverSI(listParticipants)：#定义恢复秘密信息的函数，listParticipants变量是参与者的列表
step2：
I=1
step3： for i in range(0，len(pAssignedElements[0])，1)：
step4： I *=pAssignedElements[listParticipants[0]][i] #计算出第1个参与者的生成信息，并存储到I中
step5： for j in range(1，len(listParticipants)，1)：#参与者
step6： for i in range(0，len(pAssignedElements[0])，1)：#参与者原始集合
step7： tmp=pAssignedElements[listParticipants[j]][i]
step8： if I % tmp！=0：
step9： I*=tmp
step10： I=hashlib.sha256(str(I).encode(‘utf8’).herdigest() #step5-10其他的参与者根据接收到的生成信息进行操作，最后计算出来总的生成信息，并更新I
step11： output(I) #输出恢复后的秘密信息I
step12： return(I==Pkey) #返回恢复是否成功的结果
-
正确性验证分为两个部分，第一部分验证任何不少于t个参与者分配密钥均能够恢复出秘密信息，第二部分验证任何少于t个参与者分配密钥均不能恢复出秘密信息。其伪代码如下。
step1： listPall=list(range(0，n) #列出所有的参与者
step2： listPnotLessThanT=[]
step3： for j in range(0，n-t+1，1)：
step4： for listTmp in itertools.combinations(list1，t+j)：
step5： listPnotLessThanT.append (list(listTmp)) #step2-5找出所有不少于t个参与者的组合，保存在listParticipants中
step6：
forlistP in listPnotLessThanT：
step7： rst=RecoverSI(listP)
step8： assert(rst) #step 6-8验证不少于t个参与者时，恢复秘密信息。失败则触断言
step9： listPLessThanT=[]
step10： for j in range(1，t，1)：
step11： for listTmp in itertools.combinations(list1，t-j) #step9-12找出所有少于t个参与者的组合，保存在ElistPLessThanT中
step12： listPLessThanT.append (list(listTmp))
step13： for listP in listPLessThanT：
step14： rst=RecoverSI(listP)
step15： assert(not rst)
程序运行可验证如下结论：
1) 任何不少于t个参与者分配密钥能够恢复出秘密信息；
2) 任何少于t个参与者分配密钥不能恢复出秘密信息。
因此STSA方案能够实现(t，n)门限方案。
完整的代码见
https://gitee.com/Tinff/stsa 。 -
在t=5，n=9，d=8和random.seed(8)条件下，所有元素设置为质数，并通过random.randint(2×109，1×1012)随机选取。通过全集计算出的生成信息为：2890598305722666517047028717…610659266369935568447466787931154490249772448835511389518428177466854885371913775108342128188841193082564964107609119955768334887946319783756928805770191458773836148493443(共有7030十进制位)，这是一个非常大的整数。SHA256计算后的加密秘密信息和恢复秘密信息都为：3d974c5fba1201295d1aac36cdf5c938a78a910e4e23a467cb05f2e10736c618。
在安全系数大于1(d＞1)的条件下，参与者给出的生成信息为多个质数的乘积。质数的大小是可以选择的。如果选择大质数，其他参与者就很难分解出该乘积。因此其他参与者很难恢复出参与者的原始集合。如果要求的安全性更高可以设置更大的安全系数d或选择更大的质数来形成全集U。
可见能够实现(t，n)门限方案的秘密信息计算和恢复。经过程序验证，并能够保证安全性。
-
计算机配置为英特尔Core i7-7700 @ 3.60 GHz四核、内存8 GB (DDR42400 MHz)。在t=5，n=9时，不同质数取值范围和设置不同安全系数(d=2，4，6，8)的运行性能如图 1所示。在安全系数d=2，质数取值范围设置为(2×108，1×1010)时，不同门限值(t=4，5，6，7，8，9)和参与者数量(n=9，10，11，12，13，14)下的运行性能如图 2所示。
图 1展示了STSA方案在t=5，n=9参数配置下的性能特征，重点分析安全系数d=2、4、6、8与质数取值范围对运算时间的双重影响。实验结果表明，当质数取值范围为(2×1010，1×1012)，安全系数d从2递增至8时，运算时间呈现近似指数增长的趋势，这是因为本方法中元素数量随d值增大而增加，导致集合划分、秘密计算及恢复等环节的计算复杂度显著提升。同时，质数范围的扩展也会加剧运算耗时，因为大质数在模乘、取余等运算中需要更多计算资源。实验结论表明：提升安全系数d或采用更大的质数范围虽然可以增强安全性，但是会导致运算效率的下降，实际部署需根据应用场景在安全性与性能之间寻求平衡。
图 2呈现了STSA方案在安全系数d=2、质数范围(2×108，1×1010)的条件下，运算时间随门限值t和参与方数量n的动态关系。实验表明：运算时长与参与方数量n呈显著正相关，当n由9增至14时，ASC-2方法的运算时间增长较快，同时秘密恢复阶段需处理更多参与方的信息交互，导致计算量急剧升高。相较而言，门限值t从4提升至9时运算时长增幅较缓，主要因为t值增加仅线性扩展了恢复阶段的验证步骤。该结论揭示了在此参数框架下，系统效率对参与方规模更为敏感。实际部署于多控制器系统时，须通过n与t的协同配置实现安全门限与运算效能的动态平衡。
3.1. 程序实现
3.1.1. 分配秘密信息
3.1.2. 恢复秘密信息
3.2. 正确性验证
3.3. 安全性分析
3.4. 仿真实验
-
针对当前一些(t，n)门限方案的设计和实现复杂性的问题，本文提出一种简单、易理解、易实现的门限方案。首先使用ASC集合分配方法分配N=Cnt-1个元素给n个参与者，进而设计ASC-2方法将安全系数为d的全集元素分配给各个参与者，在数学上证明了ASC和ASC-2方法的正确性。在ASC-2基础上提出了STSA安全(t，n)门限方案，也在数学上证明了STSA方案的正确性和安全性。相较于传统门限方案，STSA避免了高次插值和矩阵运算等复杂操作，降低了计算资源消耗，具有较强的理论意义。此外，STSA方案还为物联网终端、边缘设备等资源受限的场景提供了新的思路和实践路径，拓展了门限方案在隐私保护和多方计算中的应用潜力。
针对多控制器执行关键操作的应用场景，使用Python实现了STSA(t，n)门限方案。实现的STSA安全(t，n)门限方案，可以实现只有不少于t个控制器允许执行时，系统才执行关键操作；少于t个时则不能执行关键操作。同时该方案可保证控制器隐私安全，未暴露参与控制器及所持有的分配密钥。通过程序验证的方式，确认了STSA方案的正确性和安全性，同时也实现了其他学者提出的一些门限方案。
开展了多个STSA方案的性能实验并进行了分析。STSA运算时间随安全系数d，质数选取范围的增大而增加；随参与者数量n增大而急速增加；随门限值t的增大而缓慢增加。本文主要提出并验证了STSA的可行性。接下来的工作包括：增强在抗量子攻击方面的能力；对算法进行进一步优化，提升时间效率；在分配密钥复用方面探讨STSA方案与其他密码学协议的结合，特别是零知识证明和同态加密等技术，以增强其在更广泛场景下的应用能力。