基于内P-集合理论的门限秘密共享方案

吴玉杰，于秀清，李 雄

（1.德州学院数学科学学院，山东德州253023；2.湖南科技大学计算机科学与工程学院，湖南湘潭411201）

基于内P-集合理论的门限秘密共享方案

吴玉杰1，于秀清1，李 雄2

（1.德州学院数学科学学院，山东德州253023；2.湖南科技大学计算机科学与工程学院，湖南湘潭411201）

为确保密钥安全，防止密钥丢失，基于离散对数难题和内P-集合理论，提出一种新的（n，t）门限秘密共享方案。该方案将共享密钥先分成小块，然后混入构造的集合中。在密钥重构过程中，选取某个参与者作为密钥恢复者，有至少t个参与者为密钥恢复者提供秘密份额，通过构造单项映射和内P-集合的计算进行密钥恢复。由参与者自己设定子秘密，秘密分发者与参与者之间不需要维护安全信道，从而减小通信负担。实例分析结果表明，该方案实现简单，具有较高的安全性。

门限秘密；秘密共享；离散对数；内P-集合；属性集；单向映射

1 概述

秘密共享思想是把一个共享密钥S分解成n个秘密份额，并由n个参与者保管，在需要共享密钥时，由t个或t个以上参与者利用其秘密份额重构出共享密钥，而少于t个参与者利用其秘密份额得不到共享密钥的信息，t称为秘密共享门限。门限秘密共享技术可以有效保护重要信息，以防信息丢失、被破坏或被篡改等。秘密共享是现代密码学的一个重要组成部分，已被广泛应用于网络安全中。最早的秘密共享体制是由Sham ir［1］和Blakley［2］于1979年各自独立提出的。Sham ir提出的Lagrange插值法通过构造一个有限域中的（t-1）次多项式，将共享的密钥作为这个多项式的常数项，将共享密钥分成n个秘密份额分别由n个参与者保管，t个或多于t个参与者合作提供他们的秘密份额，利用Lagrange插值法恢复出共享密钥，少于t个参与者合作得不到关于共享密钥S的任何信息。Blak ley提出的几何方法把共享的密钥S看成是t维空间中的一个点，把n个秘密份额中的每个方程作为包含这个点的一个（t-1）维超平面方程，通过求解任意t个超平面的交点来确定共享的密钥S，少于t个的秘密份额不能确定其交点，从而得不到关于共享密钥S的任何信息。此后，许多学者又提出了不同的秘密共享方案，如文献［3-4］提出了基于中国剩余定理的秘密共享方案，文献［5］提出了利用矩阵乘法实现的K-G-H秘密共享方案，文献［6］提出了利用线性分组码的秘密共享方案，文献［7］提出了循环群上同态秘密共享方案等，文献［8］提出了可验证的多策略秘密共享方案，文献［9］给出了动态门限密码共享方案。目前，有很多学者还在这些方法的基础上提出了许多不同的门限秘密方案［10-12］。

在2008年，史开泉［13］提出了P-集合理论，对普通集合理论进行了动态化的研究。当前，该理论在信息图像生成、信息图像隐匿-潜藏、有效识别、信息检索等领域有着广泛应用。本文利用内P-集合理论，提出一种新的门限秘密共享方案。该方案的子秘密由参与者设定，分发者通过公共信道只公布一个集合和一个映射，秘密的恢复主要利用内P集合理论，分发者与参与者只通过公共信道进行通信，不需要安全信道，且在多秘密分享过程中，对子块的长度和个数没有限制。

2 预备知识

2.1 离散对数问题

将离散对数难解性问题描述为选取一个足够大的素数q，GF（q）是一个有限域，g是GF（q）的生成元：

（1）给出a∈GF（q），寻找唯一的整数χ，使得gχ=a mod q，该问题是难解的。

（2）给定2个元素gμ和gν，找出对应元素gμν，该问题是难解的。

（3）已知3个元素gμ，gν和gω，判定gω与gμν是否相等，该问题是难判断的。

2.2 内P-集合理论

设U是有限元素论域，X是U上的有限非空集合，X⊂U；V是有限属性论域，α是集合X的属性集合，是元素迁移函数，是元素迁移族。

定义1 给定集合X=｛χ1，χ2，…，χq｝⊂U，α=｛α1，α2，…，αK｝⊂V是X的属性集合，称XF¯是X生成的内P-集合，简称XF¯是内P-集合，而且：

其中，X-称作X的F¯-元素删除集合，而且：

如果X¯F的属性集合αF满足：

其中，β∈V，β∈¯α；f∈F把β变成f（β）=α′∈α；XF¯≠φ。上式中XF¯=｛χ1，χ2，…，χP｝，P≤q；P，q∈N+。

当不断有外来属性迁入属性集合，会得到一个内P-集合串，即：

定义4 有限属性论域V到P（U）上的单向映射为G，G（α）=X∈P（U），α∈V。

映射G满足：由α易得G（α），但是由G（α）得不到属性α。

3 本文方案

本文利用内P-集合理论提出（t，n）门限秘密共享方案。该方案假定有一个可信的秘密分发者D；n个参与者P=｛P1，P2，…，Pn｝；需要共享的密钥是S；一个公告牌，用于存放公开信息。方案中的各方均可读取公告牌上的内容，但只有秘密分发者才能更新公告牌上的内容。

3.1 系统初始化

分发者D执行下列步骤：

（1）随机生成2个大素数P，q，满足P=2P′+1，q=2q′+1，其中，P′，q′也是素数，计算N=Pq，R=P′q′，满足攻击者在知道N的情况下得到P，q在计算上是不可行的。D在有限域ZN中随机选取一个阶为R的元素g作为生成元。

（2）在ZN中选取K0，使得K0与P-1，q-1互素，计算f使得K0×f=1modφ（N），其中，φ（N）是欧拉函数。

（3）计算Y=gK0m od N。

（4）选取有限元素论域U=ZN，规定有限属性论域V的元素为属性值，不妨取V=ZN。

分发者D将f，g，Y，N公布在公告牌上，将P，q销毁。

参与者执行的步骤如下：

每个参与者Pi在有限域ZR中随机选取自己的秘密份额Ki，i=1，2，…，n，计算αi=gKim od N∈V作为其私钥属性由自己保存，计算Yi=YKimod N，通过公开信道传送给分发者D，当i≠j时D要确保Yi≠Yj，否则D将要求参与者重新选取秘密份额，直到Yi，i=1，2，…，n互不相同为止。

3.2 构造阶段介绍

3.2.1 集合选取

分发者D选取密钥S∈ZN，把S分解成m个不同的子块si，i=1，2，…，m，使得S=s1+s2+…+sm，

其中，m是保密的，记T*=｛s1，s2，…，sm｝作为内P-集合的核。选取互不相容的集合Tij⊂U，i=1，2，…，为保证少于门限t个参与者不能恢复出密钥，选取一足够大的数h，要求Tij中元素个数大于等于h。

3.2.2 集合构造

分发者D在n个参与者Pl，l=1，2，…，n中取t个参与者的组合，共计有种。若第i种组合为Pi1，Pi2，…，Pit，为这个组合中的第j个参与者Pij分配集合TiK，当K=j时，TiK=Φ（空集），K=1，2，…，t， i=1，2，…，若参与者Pij是n个参与者2，…，n中的第r个参与者Pr，然后把分配给参与者Pr的所有集合进行并运算得到Tr，计算Xr=Tr∪T*，其中，r=1，2，…，n，这样可以保证t个或t个以上的集合的交集为核T*，构造集合3.2.3 单向映射构造

由幂集的定义，有Xr∈P（U），r=1，2，…，n。

分发者D计算：

定义5 有限属性论域V到P（U）上的单向映射G：

其中，αr是Xr的属性值。然后把集合X和映射G公布在公告牌上。

3.3 密钥的恢复

在密钥恢复时，需要至少t个参与者提交自己的秘密份额，参与者利用自己的秘密份额计算出私钥属性。密钥恢复者（可以是任何人）需要收集足够多私钥属性。

3.3.1 私钥属性提交

必须有不少于t个参与者参与密钥恢复，如有t个参与者Pi1，Pi2，…，Pit做如下操作：利用自己的秘密份额计算出私钥属性αir=gKir，r=1，2，…，t，提交给密钥恢复者。

3.3.2 提交者集合计算

密钥恢复者运用公告牌上的映射G计算G（αir）=Xir，r=1，2，…，t。在这里映射G是单向的，可以保证即便破译出了Xir中的部分元素构成的子集，也不能反向计算出αir，从而得不到完整的Xir。

3.3.3 密钥计算

这里迁移函数没有具体写出，属性迁移函数的作用就是某参与者提供了属性元素αir，元素论域的迁移函数的作用就是把删除集合X-中的元素迁移出去。于是得到内P-集合的核sm｝，计算S=s1+s2+…+sm，恢复出秘密S。

3.4 方案证明

在n个参与者中必须有不少于t个参与者参与秘密恢复，不妨设t个参与者为Pj1，Pj2，…，Pjt。

计算αji=gKji，G（αji）=Xji，i=1，2，…，t。

当i=2时：

当i=t时：

若少于t个参与者参与密钥恢复，如有t-1个参与者参与密钥恢复，不妨设为Pj1，Pj2，…，Pjt-1，只能恢复出Xj1∩Xj2∩…∩Xjt-1，而不能恢复出核T*，因此，本文方案是完备的。

4 安全性与性能分析

本文方案秘密份额是参与者自己选的，而且只要求保存自己的秘密份额。所以，具有很高的安全性。

4.1 安全性分析

4.1.1 参与者的私钥属性安全性分析

若某参与者想得到其他参与者的私钥属性，需由Yi=YKimod N得到αi=gKi，这需要解决Yi=YKi=（gK0）Ki去求αi=gKi，根据离散对数的难解性，不可能求解出结果，所以，私钥属性是安全的。

4.1.2 密钥的安全性分析

密钥的安全性分析具体如下：

（1）若某个参与者通过映射G得到Xr=Tr∪T*，要想从中得到核T*，从而得到密钥，因为Xr中的元素不少于m+h，m是保密的，即要从m+h个元素中选出核中的m个元素，其概率小于只要选取的h足够大就可以保证其安全性。

（2）因为要想得到核，进而得到秘密S，必须要有至少t个参与者提供其子集，通过求交集得到核。若有少于t个参与者想恢复出密钥S，在求交集运算时不可能得到核，所得交集元素个数最少为m+ h个，若要破译出密钥S，其概率不会超过只要选取的h足够大就可以保证其安全性，所以该方案是完备的。

4.2 性能分析

本文利用内P-集合理论提出一种新的方案，该方案与Sham ir提出方案不同之处是，Sham ir提出的方案是运用Lagrange插值法，而本文方案是利用集合的运算来实现秘密的恢复，方案计算复杂性和时间的复杂性还有待于研究，但是它有以下优点：

（1）秘密S分成的子块只要求互不相同，对子块的长度和个数没有限制，甚至对秘密的类型没有限制。

（2）本文方案公共参数只有一个集合和一个映射，公开的参数是极少的。

（3）参与者只保存自己选的秘密份额，不需要安全信道，所占空间少。

（4）本文方案与Sham ir方案的不同之处是：通过选取h的大小可控制密码破译的难度。而在新个体的加入、可验证的门限秘密共享等不同方面的应用还有待于研究。

5 实例分析

若有3个参与者P1，P2，P3，n=3，门限t=2，密钥分发与秘密恢复如下：

（1）分发者D随机生成2个大素数P，q，满足P=2P′+1，q=2q′+1，其中，P′，q′也是素数，计算N=Pq，R=P′q′，满足攻击者在知道N的情况下得到P，q在计算上是不可行的。D在有限域ZN中随机选取一个阶为R的元素g作为生成元。

（2）分发者D在ZN中选取K0，使得K0与P-1，q-1互素，计算f使得K0×f=1modφ（N），其中，φ（N）是欧拉函数。

（3）分发者D计算Y=gK0mod N，选取有限元素论域U=ZN，规定有限属性论域V=ZN，分发者D将f，g，Y，N公布在公告牌上，销毁P，q。

（4）每个参与者Pi在有限域ZR中随机选取自己的秘密份额Ki，i=1，2，3，计算αi=gKimod N∈V作为其私钥属性由自己保存，计算Yi=YKimod N，通过公开信道传送给分发者D，当i≠j时，D要确保Yi≠Yj，否则D将要求参与者重新选取秘密份额，直到Yi，i=1，2，3互不相同为止。

（5）分发者D选取密钥S=11，把密钥S分解成11=2+3+6，m=3，记T*=｛2，3，6｝作为内P-集合的核。选取互不相容的集合Tij⊂U，i=1，2，3；j=1，2，要求Tij中元素个数大于等于h。为容易说明问题，选取h=3，T11=｛1，2，3｝，T12=｛4，5，6｝，T21=｛7，8，9｝，T22=｛10，11，12｝，T31=｛13，14，15｝，T32=｛16，17，18｝，分发者D在3个参与者中取2个参与者的组合，共计有种。若i=1对应的组合为P1，P2，i=2对应的组合为P1，P3，i=3对应的组合为P2，P3。运用上述方法为参与者分配集合如图1所示。

图1 参与者分配集合

计算下列公式：

（6）构造单向映射。P（U）是有限元素论域U的幂集，则有Xr⊂P（U）。

G是有限属性论域V到P（U）上的映射：

把集合X和映射G公布在公告牌上。

（7）在秘密恢复时，需要至少2个参与者提交自己的秘密份额。如2个参与者是P1，P2，对应的私钥属性分别为α1，α2，运用公告牌上的映射G计算G（αi）=Xi，i=1，2。

设XF为X的内P-集合，X-为X的XF-元素删除集合，XF=X，秘密恢复者取参与者的私钥属性做以下运算：

1）当i=1时，α=α1，X-=XF-G（α）=X-X1，XF=XF-X-，得XF=X1=T12∪T22∪T*。

2）当i=2时，α=α2，X-=XF-X2=X1-X2，XF=XF-X-=X1-（X1-X2）=X2∩X1=（T11∪T32∪T*）∩（T12∪T22∪T*）=T*。

于是得XF=T*=｛2，3，6｝。

这样构造出S=2+3+6=11。

若有少于2个参与者，如参与者P1想恢复出秘密S，其掌握的子集是：

X1=T12∪T22∪T*=｛2，3，4，5，6，10，11，12｝

里面元素的个数超过h=3，需要从中选出2，3，6，选中的概率为：

因此，只要元素的个数h选的足够大，要想得到核是非常困难的，所以，该方案是完备的。

6 结束语

基于P-集合理论，本文提出一种新的秘密共享方案。该方案通过内P-集合理论构造了一个内P-集合和一个映射函数，参与者只要提供正确的秘密份额，通过内P-集合的运算就可以恢复出秘密。实例结果表明，只要分发者选取的集合中的元素个数足够多，其破解的难度就足够大，同时该方案不需要安全信道，秘密的分发只公布一个集合、一个单向映射，在秘密的恢复阶段只运用集合运算。然而，在该方案中，分发者必须是可信的，不能防止分发者的欺骗，且不能检测分发者与参与者、参与者与参与者之间的欺骗行为。因此，研究解决分发者与参与者的欺骗问题、新个体的加入问题是今后的研究方向。

［1］ Sham ir A.How to Share a Secret［J］.Communications of the ACM，1979，22（11）：612-613.

［2］ Blakley G.Safeguarding Cryptographic Keys［C］//Proceedings of AFIPS National Computer Conference. New York，USA：AFIPS Press，1979：313-317.

［3］ Mignotte M.How to Share a Secret［C］//Proceedings of Workshop on Cryptography.Berlin，Germany：Springer-Verlag，1983：371-375.

［4］ Asmuth C A，Bloom J.A Modular Approach to Key Safeguarding［J］.IEEE Transactions on Information Theory，1983，29（2）：208-210.

［5］ Karnin E D，Greene J W，Hellman M E.On Sharing Secret System s［J］.IEEE Transactions on Information Theory，1983，29（1）：35-41.

［6］ Bertilsson M，Ingemrsson I.A Construction of Practical Secret Sharing Schemes Using Linear Block Codes［C］// Proceedings of AUSCRYPT'92.Berlin，Germany：Springer-Verlag，1992：67-79.

［7］ 刘木兰，周展飞.循环群上理想同态密钥共享体制［J］.中国科学：E辑，1998，（6）：524-533.

［8］ 王 锋，谷利泽，郑世慧，等.可验证的多策略秘密共享方案［J］.北京邮电大学学报，2010，33（6）：72-75.

［9］ 吴昊天，陈 越，谭鹏许，等.基于门限的组密钥管理方案［J］.计算机工程，2013，39（3）：167-173.

［10］ 王 锋，周由胜，谷利泽，等.一个群组验证的多策略门限数字签名方案［J］.计算机研究与发展，2012，49（3）：499-505.

［11］ 孙 华，王爱民，郑雪峰.标准模型下可证安全的基于身份的门限环签密方案［J］.计算机科学，2013，40（5）：131-135.

［12］ 付小晶，张国印，马春光.一个改进的动态门限基于属性签名方案［J］.计算机科学，2013，40（7）：93-97.

［13］ 史开泉.P-集合［J］.山东大学学报：理学版，2008，43（11）：77-84.

编辑 刘 冰

Threshold Secret Sharing Scheme Based on Internal P-sets Theory

WU Yujie1，YU X iuqing1，LIX iong2
（1.College of Mathematical Sciences，Dezhou University，Dezhou 253023，China；2.School of Computer Science and Engineering，Hunan University of Science and Technology，Xiangtan 411201，China）

In order to protect secret，a new efficient（n，t）threshold secret sharing scheme is proposed based on discrete logarithm problem and the P-sets theory in this paper.In this scheme，the sharing secret is divided into small pieces and is mixed into the structural set，in the secret reconstruction，the sharing secret is reconstructed through Computing a map and the internal P-sets by more than t secret shares by a designated participant，and the computational complexity is very low. The secret shares are chosen by the participants themselves，so there is no secure channel between the secret dealer and participants and reduces the communication costs.Example results show that the proposed scheme has high security and is easy to implement.

threshold secret；secret sharing；discrete logarithm；internal P-sets；attribute set；one-way mapping

吴玉杰，于秀清，李 雄.基于内P-集合理论的门限秘密共享方案［J］.计算机工程，2015，41（9）：159-163.

英文引用格式：Wu Yujie，Yu Xiuqing，Li Xiong.Threshold Secret Sharing Scheme Based on Internal P-sets Theory［J］. Computer Engineering，2015，41（9）：159-163.

1000-3428（2015）09-0159-05

A

TP309

10.3969/j.issn.1000-3428.2015.09.029

国家自然科学基金青年基金资助项目（61300220）；山东省自然科学基金资助项目（ZR2010AL019）。

吴玉杰（1964-），男，副教授，主研方向：门限密码学；于秀清，教授；李 雄，讲师、博士。

2014-09-01

2014-11-08 E-m ail：w yj9030@163.com