基于多项式插值的多等级秘密共享方案*

张 剑， 林昌露，5， 黄可可， 刘亚丽

1. 福建师范大学 数学与统计学院， 福州 350117

2. 福建师范大学 福建省网络安全与密码技术重点实验室， 福州 350007

3. 福建师范大学 计算机与网络空间安全学院， 福州 350117

4. 江苏师范大学 计算机科学与技术学院， 徐州 221116

5. 桂林电子科技大学 广西可信软件重点实验室， 桂林 541004

6. 桂林电子科技大学 广西密码学与信息安全重点实验室， 桂林 541004

1 引言

秘密共享能够将秘密信息共享给多个参与者， 使其中的授权集合可得到秘密信息， 而非授权集合得不到秘密信息， 是一种有效的秘钥管理方法. 1979 年， Shamir[1]和Blakley[2]分别基于不同的方法提出了门限秘密共享方案， 当达到一定数量的参与者提供子秘密时可以重构得到秘密的信息， 否则得不到秘密的任何信息. 但由于门限结构存在的局限性， 因此对秘密共享的研究推广到一般性存取结构中， 如文献[3-7]构造的秘密共享方案实现了具有一般性的存取结构. 为了提高秘密共享的效率， 提出了多秘密共享的概念，目前已有大量关于多秘密共享的研究， 如文献[8-11]. 多秘密共享可一次共享多个秘密信息， 所消耗的计算资源远小于重复多次的使用单秘密共享， 在密钥管理中可通过少量的计算操作实现多个密钥的管理. 同时， 秘密共享也是区块链、安全多方计算和隐私计算等新技术的重要组成部分， 在大量数据的计算中， 多秘密方案的使用也能够提高其使用和计算的效率.

现实当中对于某些机构而言， 机构中的人员身份存在等级关系， 等级高则具有更多的权限. 为了实现这种多等级场景中的秘密共享， Simmons 于1988 年提出了第一个多等级秘密共享方案(HSS)[12]， 将参与者集合P分为m个不相交的集合P=∪m i=1Li，Li ∩Lj=Ø(1≤i，j ≤m，i/=j)， 其中L1为最高等级，Lm为最低等级， 每一个集合中的参与者为同一个等级， 不同等级的门限值不同， 参与者个数达到门限时可恢复秘密. 当某一等级中的参与者在重构时， 参与者个数小于门限值， 此时更高等级的参与者可参与到该等级的秘密重构当中， 完成秘密重构. 如L1门限为2、L2门限为3， 则L1中2 个参与者、L2中3个参与者均可恢复秘密， 同时L1中1 个参与者和L2中2 个参与者合作也可以恢复秘密.

1989 年， Brickell[13]提出一个理想的多等级秘密共享方案， 该方案不同的等级选择不同的多项式生成子秘密， 并且该方案利用向量的线性无关性构造， 需要通过指数级的计算来确保矩阵的非奇异性， 从而保证方案的安全性， 因此实现该方案的效率过低. 1998 年， Ghodosi 等人[14]基于Shamir (t，n) 门限方案构造了一个理想的多等级秘密共享方案， 并且不产生额外的公开值. 其构造为逐级生成子秘密， 首先构造L1层的秘密分发多项式， 再根据L1中全部参与者的子秘密结合第二级门限求解方程组， 来构造第二级的秘密分发多项式， 依次下去直至生成Lm级的子秘密. 但该构造在门限的选择有一定的限制， 因此只适合门限值较小、同时参与者个数较少时使用.

2007 年， Tassa[15]利用Birkhoff插值的方法， 构造了一个理想的多等级秘密共享方案， 方案的主要思想是构造秘密分发多项式， 在不同等级中计算多项式的导数， 再根据其导函数计算和分发子秘密.Tassa 和Dyn[16]基于二元插值的思想构造了一个新的多等级秘密共享方案. 2009 年， Lin 等人[17]根据Shamir(t，n) 门限方案， 利用多项式方法构造了多等级门限秘密共享方案. 该方案从L1开始构造秘密分发多项式， 计算L1中n1个参与者的子秘密， 再根据n1与t2的大小确定L2的秘密分发多项式次数和对应公开点的个数， 使得L2中满足(t2，n2) 门限方案的条件， 同时L1中参与者可充当L2中的成员参与重构. 按照这种方式依次执行相同的操作， 直至生成所有参与者的子秘密为止. 与前面几种方案相比，该方案中参与者Pij保存的子秘密信息中包含自身的身份信息xij与多项式的函数值yij， 对xij没有进行公开， 只有当重构秘密时， 参与者Pij提供(xij，yij) 进行重构运算， 可用于一些需要对参与者身份信息保护的情景.

2014 年， Harn 和Miao[18]提出了第一个基于中国剩余定理的多等级门限秘密共享方案. 该方案中为实现高等级参与者参与低等级秘密重构， 每一级都需对更高等级的全部参与者产生对应公开值， 因此需要大量公开信息. 针对上述方案[18]存在的问题， Erosy 等人[19]在Harn 和Miao 方案[18]的基础上， 基于中国剩余定理构造了新的多等级门限方案， 通过引入hash 函数实现对信息进一步隐藏， 使得公开值中不会泄露秘密的任何信息. Shima 和Doi[20]基于生成矩阵的方法提出了新的构造多等级秘密共享的方法.

近期多位研究者给出了关于多等级多秘密共享的研究工作， 2020 年， Meriem 和Sadek 在文献[21]中基于以树结构表示的企业层次概念， 提出了一个理想的多等级单秘密共享方案， 采用多项式的构造方式实现了特殊的门限结构， 高等级的参与者所拥有的的子秘密更多， 可以充当多个低等级参与者. 2020 年， Wu等人在文献[22] 中基于多项式的门限方案提出一种多等级的图像秘密共享方案， 该方案中参与者个数需达到门限值， 且每个等级中有一个子门限， 每个等级中均也需达到对应门限值的参与者个数才能够重构出共享的图像信息. 2020 年， Zhang 等人在文献[23] 中基于区块链提出了一种分散公平的多等级门限秘密共享方案， 利用智能合约的方式实现多等级结构.

为提高多等级结构秘密共享方案的通信和存储效率， Basit 等人提出了基于多等级结构的多阶段多秘密共享方案[24]， 但该方案仅仅是将多秘密共享与文献[25] 所提出的多等级秘密共享方案进行结合， 实现了具有顺序性的多等级多秘密共享. 当某一等级的参与者恢复任一秘密时， 为实现更高等级参与者可参与重构， 需要为所有更高等级参与者生成公开值， 因此公开值个数与秘密个数成比例. Singh 等人[26，27]基于Harn 和Miao 方案[18]与多秘密共享方案[25]构造了基于CRT 的多等级多秘密共享方案. Tentu 等人[27]基于二次剩余和离散对数等方法构造了新的多等级多秘密方案.

在多等级门限秘密共享方案中， 为实现高等级参与者可参与低等级参与者集的秘密重构， 现有实现该功能的方法包括:

(1) 秘密分发时， 为高等级参与者生成对应公开值， 参与者根据子秘密与指定公开值的运算结果可参与低等级的秘密重构;

(2) 秘密分发过程由高等级开始， 低等级对应生成多项式的构造与更高等级全部参与者子秘密信息相关;

(3) 如Tassa 方案[15]中的构造， 不同等级参与者的子秘密由同一多项式不同阶的导函数计算得到.

本文提出一种新的实现多等级门限秘密共享方案， 运算量小并且方案每一等级只有一个公开的素数，参与者保存一份子秘密， 当高等级参与者参与低等级的秘密重构时， 参与者提供子秘密模对应素数后的值即可. 由于现有多等级结构中所构造的多秘密方案在秘密分发阶段需要产生大量公开值来确保实现多秘密的多等级秘密共享， 因此本文在构造单秘密的方法基础上提出了两种多秘密的多等级秘密共享方案， 通过不同的构造， 使得更少的公开值即可实现多秘密共享.

文章剩余部分结构为: 第2 节介绍相关基础内容， 第3 节提出新的多等级门限秘密共享方案的构造以及方案的分析， 第4-5 节提出两类多秘密方案的构造， 第6 节是与相关工作进行对比分析， 第7 节对文章工作进行总结.

2 预备知识

本节首先介绍了存取结构的概念和中国剩余定理的具体内容， 然后简要介绍了Shamir 门限秘密共享方案的内容以及多等级秘密共享方案的定义.

2.1 存取结构

2.2 中国剩余定理

定义2 中国剩余定理(Chinese remainder theorem， CRT)[28]是求解同余方程组的方法. 随机选择两两互素的整数m1，m2，···，mn， 对于任意的整数r1，r2，···，rn， 满足ri ∈Zmi(i=1，2，···，n)， Zmi为整数模mi的剩余类环， 则下列同余方程组

2.3 Shamir (t，n)-门限秘密共享方案

Shamir[1]用多项式的方法构造了一个(t，n)-门限秘密共享方案， 将秘密S ∈Fp(p为大素数，p ＞n)作为多项式f(x) 的常数项， 计算f(x) 在n个不同点处的函数值作为对应参与者的子秘密. 从而将秘密拆分为n份发送给n个参与者P1，P2，···，Pn， 使得任意大于等于t个参与者可以重构出秘密S， 任意少于t个参与者不能得到秘密S的任何信息. 具体过程分为下面两个阶段进行:

2.4 多等级秘密共享方案

一般的门限结构中， 所有参与者扮演地位相同的角色， 不存在等级的高低. 但是在很多机构或商业公司存在普通职员和管理人员， 职位具有上下级关系， 因此本文研究一种存在等级关系的门限结构秘密共享，即多等级秘密共享(hierarchical secret sharing， HSS)[15].

3 方案设计

本节将介绍一种新的多等级门限秘密共享方案， 其中第3.1 节介绍了多等级门限结构秘密共享方案的构造方法， 第3.2 节分析了方案的正确性和安全性.

3.1 多等级门限秘密共享方案

根据中国剩余定理的多项式形式， 结合Shamir (t，n)-门限方法构造了一种新的多等级门限共享方案.根据参与者的等级， 分发给不同等级参与者子秘密时， 通过选择不同的模数来实现多等级结构， 同时满足高等级的参与者可参与低等级的秘密重构， 而低等级参与者无法正确参与高等级的秘密重构. 方案的公开值为m个模数和每个参与者的身份信息， 减少了大量的公开值个数. 下面介绍方案的具体构造方法:

3.2 方案分析

定理2 设秘密S ∈Zq1，利用3.1 节中秘密共享方案进行秘密共享时，任意至少ti个参与者Plj(l ≤i)可重构出秘密S.

证明: 由于多项式f(x)=a0+a1x+···+at-1xt-1， 其系数构造为

因此，ri(＜ti) 个Li中的参与者和(ti-ri) 个高等级的参与者可恢复秘密S.

定理3 设秘密S ∈Zq1， 利用3.1 节中秘密共享方案进行秘密共享时， 少于ti个级别不低于i的参与者无法恢复秘密S.

证明: 由定理2 可知， 更高等级参与者可充当第i级参与者的角色， 因此这里考虑两种情况: (1) 只存在第i级参与者进行重构; (2) 存在低等级参与者参与重构的情况.

4 多秘密方案

本节对第3 节提出的单秘密HSS 方案进行扩展， 构造了两种多秘密方案. 方案一通过公开部分信息实现多秘密共享， 方案二的构造是将多个秘密通过中国剩余定理(CRT) 进行聚合， 在模不同素数时可得到不同的秘密信息.

4.1 扩展方案一

扩展方案一在构造多秘密共享时， 采用转换值和单向函数的方法计算公开值， 同时结合上述基础方案的构造方法， 以较少的公开值个数实现了多秘密共享. 每一个秘密都会为所有参与者对应生成一个公开值用于秘密重构， 同时采用单向函数来保证子秘密的安全性， 并且秘密恢复必须按照顺序Si(i=k →1) 逐个恢复. 参数选取和秘密分发、重构过程如下:

· 秘密重构阶段:

4.2 扩展方案二

本方案是将所有k个秘密通过中国剩余定理的同余方程组进行聚合， 产生一个聚合后新的秘密值， 将这个新生成的秘密值通过基础方案的方法进行共享， 再选择不同的模数进行秘密重构， 得到的计算结果可参与恢复对应的秘密， 减少了大量公开值的产生. 方案的具体构造如下:

5 多秘密方案分析

5.1 方案一分析

本节通过定理4 对方案的正确性和安全性进行说明， 定理5 分析了秘密重构过程中子秘密的安全性，定理6 说明了在秘密重构阶段， 已恢复的秘密不会泄露任何未恢复秘密的信息， 确保了多秘密的安全性.

定理4 根据扩展方案一进行秘密共享时， 任意大于等于ti个参与者Pi′j(i′≤i) 能够正确恢复秘密Sl， 少于ti个则不能得到秘密的任何信息.

5.2 方案二分析

本节对扩展方案二进行分析， 定理7 证明了方案的正确性和安全性， 定理8 分析了方案多秘密的安全性.

定理7 根据扩展方案二进行秘密共享时， 任意大于等于ti个参与者Pi′j(i′≤i) 能够正确恢复秘密Sl， 少于ti个则得不到秘密的任何信息.

证明: 根据定理2， 仅考虑第i级参与者参与重构的情况. 关于秘密Sl的分发多项式fil(x)≡fi(x)(modpl)≡f(x) (modqi) (modpl)，fil(x) 为ti-1 次多项式， 且yi′j ≡fil(xi′j) (modpl). 因此根据Shamir (t，n)-门限方案， 当至少ti个参与者Pij参与重构可恢复秘密Sl， 而少于ti个参与者不能得到秘密Sl的任何信息.

定理8 根据扩展方案二进行秘密共享， 第i级参与者恢复秘密Sα时， 不能根据秘密Sα得到未恢复的秘密Sβ(β/=α) 的任何信息.

6 方案对比

6.1 单秘密方案

文献[17] 将参与者的xij信息作为子秘密的一部分， 将秘密S进行分割S=S1||S2， 分别将S1，S2作为多项式的常数项和一次项系数进行分发. 该方案同样首先构造最高等级的t1-1 次分发多项式， 根据该级全部参与者子秘密以及秘密值通过Lagrange 插值的方式构造下一级的分发多项式， 但根据每一级的门限值和多项式次数大小进行比较， 会产生部分公开的点用于秘密重构.

文献[18] 根据中国剩余定理构造多等级门限方案， 为实现不同等级之间的关系， 在秘密分发时为高等级参与者生成大量对应的公开值， 同时该方案需要选择大量的互素整数， 使得高等级能够正确参与到低等级的秘密重构中， 但运算过程较为简单， 生成子秘密与公开值均为整数上的模运算.

本文所提出的方案， 首先构造t次多项式f(x)， 使得在模不同素数qi情况下可得到次数为ti-1 的多项式fi(x)，fi(x) 作为第i级的分发多项式， 实现了不同等级的门限结构. 方案在公开值以及计算复杂度等方面均实现了较好的性质. 表1 中对几个单秘密的多等级门限方案进行了比较， 因为秘密重构时几种方案的计算量基本持平， 表中仅考虑方案在秘密分发时的计算复杂度.

表1 多等级单秘密方案对比Table 1 Comparison with hierarchical secret sharing schemes

6.2 多秘密方案

文献[24] 中Basit 等人根据He 和Dawson[25]的多阶段多秘密方案， 结合多等级秘密共享构造了一个多等级结构中的多阶段多秘密共享方案. 该方案在构造时， 对应每个秘密在每个等级都构造一个子秘密生成多项式， 为实现等级结构之间的关系， 所有低等级都需为高等级参与者生成对应公开值， 使得高等级参与者可参与到低等级的秘密重构中. 因此该方案需要产生大量的公开信息. 文献[26] 中Singh 等人基于中国剩余定理以及文献[25] 的多秘密方法构造多秘密的多等级共享方案， 每一个秘密均应用Harn 和Miao[18]的方法进行构造， 并根据多秘密方法产生公开值， 因此具有和文献[24] 相同的公开值个数. 多等级多秘密共享方案对比如表2 中所示， 其中k为共享秘密的个数.

表2 多等级多秘密方案对比Table 2 Comparison of hierarchical multi-secret sharing schemes

本文所构造的多秘密方案一利用多秘密方案的构造方式， 每个参与者对应不同的秘密有一个公开值作为参与该秘密重构的子秘密， 同时利用单向函数的构造， 确定秘密恢复时的顺序性， 当按照这个顺序进行重构时， 可以确保还未恢复秘密的安全性. 多秘密方案二根据中国剩余定理的思想， 将多个秘密的信息隐藏在同一个多项式中， 从而只公开模数以及参与者的身份信息即可.

7 结论

本文提出了一种新的构造多等级门限结构上的秘密共享方案， 方案基于多项式构造， 计算简单并且公开值个数较少. 分发子秘密时根据参与者等级选择不同的模数， 同时参与者在重构秘密时根据对应等级进行模运算， 并发送参与重构以此可实现多等级结构并且高等级参与者可参与到低等级的秘密重构当中. 在此基础上构造了两种新的多秘密方案， 相比其他相关方案而言， 本文构造的多秘密方案运算简单， 同时所产生的公开值个数少， 具有更好的性质.