可变门限值的多秘密共享方案

韩慧颖，刘焕平

(哈尔滨师范大学)

0 引言

秘密共享对于密钥管理来说是一个非常重要的技术.而秘密共享方案的应用其目的就是为了让密钥管理更加有效和灵活.在过去所提出的秘密共享方案都是针对同一门限值的，不同秘密的门限值一旦发生改变，那么原有的方案将无法恢复秘密，或者需要改变参与者手中的子秘密才能实现秘密的恢复，而此时参与者手中将持有多个子秘密，使得恢复秘密的成本大大提高.针对这种情况提出关于恢复可变门限的多秘密的共享方案.一个显著的特点就是当不同的秘密需要不同的门限值来恢复时，依然可以利用所提出的方案来实现秘密的恢复.该方案的优点是:在恢复不同门限值的多秘密共享时，可以让每位参与者只保存一个子秘密，并且当某些秘密被恢复后，并没有影响其他秘密的安全性，它实现了恢复不同门限值的秘密共享方案.通过成功利用离散对数的难解性和Diffie-Hellman计算问题的难解性，可以成功地防止攻击者对秘密的攻击，即使在伪秘密暴露的情况下，也不会影响其他秘密的恢复，如果秘密需要更新时，每位参与者手中持有的子秘密也不需要改变，因此这是一个针对可变门限值的多秘密共享方案.

公钥的密码系统已经广泛应用不同领域中，公钥系统中重要一点就是私钥管理，1976年Diffie和Hellman说明了离散对数问题求解是难的，考虑到现实中的可操作性，1979年，Shamir提出了(t，n)门限秘密共享方案.然而，Shamir方案并不能在门限值发生变化的时候去使用，也就是说Shamir方案只能恢复固定门限值的秘密共享，如果门限值发生改变时，则需要重新分发参与者手中的子秘密.例如，某公司要将公司内部的三个机密文件进行保存，将其放在三个不同的保险柜当中，由于机密文件的保密程度不同，将它们分为一号文件保密程度最低，只需要三个公司高管就可以恢复，二号文件保密程度较高，需要五名公司高管恢复，三号文件保密程度最高，要六名公司高管恢复.在这种情况下，如果想让公司每个高管手中仅仅只有一个子秘密，但能同时参与三个秘密文件的恢复，并且在恢复一个秘密之后并不会影响其他秘密恢复.针对这种情况，该文提出一种基于离散对数问题的难解性和Diffie-Hellman计算问题的难解性的可变门限的多秘密共享方案.在这个方案中，只需要在一个系统中去完成不同门限值的秘密恢复，让参与者手中只持有一个子秘密，但能恢复门限值不同的秘密.用到Stadler提出在线秘密共享体制，引入公告牌(NB)发布一些辅助信息的方法和田有亮提出的椭圆曲线上的可验证秘密共享方案中，利用在加法群构造多项式的方法.

1 准备知识

设G是有限加法循环群，g是G的生成元.

(1)离散对数问题是难解的:给定(g，ag)，对任意的a∈，求a是难解的.

(2)Diffie-Hellman的计算问题难解:给定(g，ag，bg)，对任意的 a，b ∈，计算(ab)g 是难解的.

2 提出的方案

假设有庄家D要在n个参与者U={U1，U2，…，Un}间共享秘密 s1，s2，…，sk∈ G1，在这里 t1个人能恢复秘密s1，t2个人能恢复秘密s2，…，tk个人能恢复秘密 sk，即对任意 i，i=1，…，k只有当ti个或ti个以上的参与者联合才能回复共享秘密si，少于ti个参与者的任何组合都无法恢复秘密，该方案分为以下三个过程:系统初始化过程，秘密分发的过程，以及秘密重构过程.

2.1 系统初始化

G1是素数阶的加法群，其阶为q，P是其生成元(比如可以令G1是某个椭圆曲线上的q阶循环子群)，G1上的离散对数和Diffie-Hellman的计算问题都是难解的.

2.2 秘密分发过程

(1)参与者Uj选择xj∈作为自己的子秘密，计算其伪秘密xjP，并将xjP发送给D，D看每个xjP是否相同，若有相同的则需要重新选择直到互不相同为止.

(2)对 i=1，2，…，k，庄家 D 任取 αi∈(要求αi互不相同，并且αiP要与参与者所公开的xiP互不相同)，并在公报牌上公开Ri，其中Ri= αiP，其中 i=1，2，…，k.

(3)庄家D收到xjP后，计算yij=xjαiP，并选取G1［x］上次数为ti-1次的多项式，其中x∈Zq，Ai∈G1，Fi(x)=si+A1x+A2x2+ …Ati-1xti-1，满足Fi(0)=si并计算Fi(j)=Sij，令Tij=Sijyij，i=1，2，…，k，j=1，2，…，n，其中 Tij∈ G1，将Tij公布在公告牌上.

2.3 秘密恢复过程

以恢复秘密si为例，任何ti个或大于ti个成员都可以恢复秘密si，现不妨设由集合{U1，U2，…，Uti}来恢复秘密si，那么参与者首先要计算yij=xjαiP，然后在公告牌上选出与自己相对应的Tij，再计算出Sij=Tij+yij，最后向其他参与者提供(Sij，j)，再利用拉格朗日插值公式来恢复秘密，恢复出

3 性能分析

(1)合理性:这个方案不论是在系统初始化阶段还是秘密恢复阶段都是简单可行的.

(2)安全性:这个方案的安全性主要基于离散对数的难解性和Diffie-Hellman计算难解的.

①秘密si的安全性:

任何一个攻击者据无法通过公开的(xjP，αiP，Tij)以及他们掌握的子秘密恢复出秘密si，这是因为攻击者要想知道si，只有Tij和yij同时知道的时候才能恢复si，但是由Diffie-Hellman计算难解性可知攻击者并不能从公开的xjP知道参与者手中的子秘密xi，所以并不能利用公开的信息恢复秘密si.

②子秘密xj的安全性:当其他参与者通过恢复秘密si而得到参与者Uj提供的yij时，由离散对数的难解性可知其他参与者是无法利用得到参与者Uj所提供的yij而得到Uj的子秘密xj.

③恢复秘密si后，秘密sj的安全性:当其他参与者通过恢复秘密si而得到yij时，他们并不恢复秘密sj，因为此时除了公开的Tjj还需要知道yjj，当秘密si被恢复后，由②可知也无法利用已知的yij去得到Uj的子秘密xj，所以也无法得到yjj.而由Diffie-Hellman计算难解性可知攻击者无法利用公开的(αjP，xjP)而求出yjj，所以秘密sj也是安全的.这也实现了秘密的安全性.

④秘密的更新:参与者Uj手中只需要持有一个子秘密xj就可以恢复秘密sj.由于每个成员的子秘密在秘密恢复后并没有被暴露，因此，一次只需为每个参与者重新选取一个(αiP，Tij)就可以利用上述方案恢复新秘密.

4 结束语

笔者给出了基于离散对数难解性和Diffie-Hellman计算问题难解性的可变门限的多秘密共享方案，它利用公开信道去恢复可变门限值的秘密共享方案，它只需参与者保存一个子秘密，但却能同时参与多个秘密的恢复，恢复后也不会影响到其他秘密的恢复.

［1］ Shamir A.How to share a secret［J］.Comm ACM，1979，22(11):612-613.

［2］ Blakey G R.Safeguarding cryptographic keys［A］.Proc AFIPS 1979 Natl Conf［C］.New York，1979.313-317.

［3］ Stadler M.Publicly verifiable secret sharing［A］.Cryptology-EUROCRYPT’96［C］.Berlin，1996.190-199.

［4］ 刘焕平，吕学琴.基于单向函数的广义秘密共享方案［J］.通信学报，2004，25:5.

［5］ 邹惠，王建东，宋超.加权门限多秘密共享方案［J］.计算机工程，2012，38:3.