一个可公开验证的多重秘密共享门限方案

蔡兆政，瞿云云，包小敏

1. 西南大学 数学与统计学院，重庆 400715；2. 重庆市第十八中学，重庆 400020；3. 贵州师范大学 数学与计算机科学学院，贵阳 550001

秘密共享的概念最早由文献[1-2]提出． 文献[1]利用拉格朗日插值多项式构造了一个门限秘密共享方案，其主要思想是二维平面内任意t个点都可唯一确定一个t-1次多项式． 任何t个及t个以上的参与者联合可以重构多项式，得到的常数项即为分享的秘密． 反之，任何小于t个参与者的集合不能重构多项式，从而不能获得秘密． 文献[2]利用线性投影几何原理的性质构造的门限方案，t个t-1维超平面可以确定t维空间中一个点，但小于t个是无法确定的． 这两个经典的门限秘密共享方案为研究不同访问结构(access structure)上的秘密共享奠定了基础[3]． 文献[4]提出了基于中国剩余定理的门限秘密共享方案，秘密份额是秘密的同余类，满足t个同余方程的解在取值范围中是唯一的，少于t个方程，解无法确定． 文献[5]利用矩阵乘法构造了一个秘密共享方案，其原理等价于解含有t个未知数的线性方程组，每个共享份额相当于一个线性方程，任意大于等于t个份额联立可以求得t个未知数，而其中的一个未知数恰为分享的秘密，当方程个数小于未知数个数的时候无法确定方程组的解，从而不能恢复共享的秘密． 上述几种构造秘密共享方案的方法是最常用的几种方法，此外，文献[6]中指出，一个RS码对应一个秘密共享方案． 文献[7]利用纠错码巧妙构造了一个秘密共享门限方案，该方案是一个(l，t+l)门限秘密共享方案，可以共享多个秘密．

任何在实际中应用的密码方案及其算法都应该具有抵抗攻击的能力，Shamir秘密共享方案[1]和其他秘密共享方案是在秘密分发者和参与者都可信的前提假设下设计的，这样就导致了秘密共享方案在实际应用场景中存在很多安全隐患． 例如内部的参与者为了获得其他参与者的份额而提供假的份额；或者由于受信道中噪音的干扰等导致份额在通信过程中出现错误；又或者外部攻击者冒充授权的参与者进行欺诈；另外，秘密分发者也可能存在欺诈行为． 这些情况都会导致秘密无法重构或者重构的秘密错误． 为了解决这些问题，许多学者提出了可验证的秘密共享方案．

1985年，文献[8]提出了可验证秘密共享(verifiable secret sharing，VSS)的概念，其方法是在通常的秘密共享方案中添加一个验证算法，这样份额持有者就能验证自己的份额与分发者分发的份额是否一致． 验证方式有交互式和非交互式两种． 随后，其他研究者提出了一系列的可验证的秘密共享方案，文献[9]构造了一个非交互式的VSS方案． 在VSS方案的基础之上，文献[10]提出了可公开验证秘密共享(publicly verifiable secret sharing，PVSS)的思想，不仅仅内部参与者可以验证份额的有效性，非参与者也可以验证． 1999年，文献[11]设计了一个更完善的非交互的PVSS方案，方案中有两次非交互验证． 第一次是验证秘密分发者分发的加密的秘密份额，第二次是验证参与者解密后的秘密份额；前者可以预防秘密分发者的欺骗行为和通信中的错误，后者可以防止参与者之间的欺诈行为． 这样确保了秘密份额的有效性，避免了由于份额错误而产生不必要的计算． 本文也采用两次验证的思想．

在秘密共享中另外一个需要着重考虑的问题就是方案的效率，主要考虑数据传输量和计算量． 若秘密分发者和参与者之间使用一次一密的方式共享秘密，虽然安全性得以保证，但是在效率和成本上都有欠缺． 例如在Shamir门限方案中，参与者重构一次秘密之后，若要共享新的秘密，分发者就必须重新设置参数、给参与者分发秘密份额，因为该方案中参与者持有的秘密份额是一次性的，不能重复使用，方案的效率较低．

为了提高秘密共享方案的效率，文献[12-13]提出了一个多阶段秘密共享方案，方案中的每个份额可以使用l次，但是在重构过程中要求参与者提供相应顺序的秘密份额，这在实际的应用有很大的局限性． 随后，文献[14]构造了克服了上述缺点的一个方案，参与者可以用同一个子秘密共享任意多个秘密，子秘密可使用任意多次，但该方案为防止秘密分发者欺诈，每个参与者需要运行多次模指数运算来验证，计算量非常大． 同时为了防止参与者之间的相互欺诈，方案采用交互式验证方式． 针对上述缺陷，文献[15]提出一个新的方案，但在该方案中，对每一个共享秘密，秘密分发者除了要计算秘密份额外，还需要利用各参与者的子秘密计算一个验证向量，而向量的每一个分量都是模指数运算，因而秘密分发者计算压力很大． 文献[16]在门限秘密共享和RSA数字签名的基础之上，提出了门限多重秘密共享方案，但是该方案需要将子秘密通过秘密信道发送给参与者，在动态秘密共享情形下，秘密共享者的工作量较大，同时维护秘密信道增加了通信开支． 本文提出了一个安全有效的可公开验证的(t，n)多重秘密共享门限方案． 方案加密采用ElGamal公钥密码体制[17]，不需要维护秘密信道而增加通信成本；计算的验证参数可以多次利用，Dealer要想共享新的秘密，只需要在公告牌上发布新的数据即可，Dealer的计算量较小，具有广泛的适用性．

1 基础知识

定义1(拉格朗日插值多项式) 设(x0，y0)，(x1，y1)，…，(xt-1，yt-1)是二维平面上任意给定的t个点的坐标，则有且仅有一个与这t个点的坐标对应的t-1次多项式p(x)，满足p(xi)=yi，0≤i

p(x)可以通过下面的公式计算得到：

(1)

身份识别的目的是使某人的身份被确认． 下面介绍Schnorr身份认证方案，该方案需要一个可信第三方发放证书和选择系统参数．

下面的同余式成立说明Alice能够向Bob证明自己的身份

在上述的方案中需要证明者和验证者交互才能证实证明者的身份，显然满足不了本文所构造方案中非交互身份认证的需求，因此建立了一个非交互的身份认证方案．

2 方案构成

设P={P1，P2，…，Pn}是n个参与者的集合，Dealer是秘密分发者． 该方案在系统中需要一个公告牌，只有Dealer可以修改、更新公告牌上的内容，其他人只能阅读和下载．hash()是一个安全的密码学Hash函数．

2.1 秘密分发阶段

1) 秘密份额分发

Dealer保存p(x)，在公告牌上发布相关系数Ci=gαimodq，i=0，1，…，t-1．

2) 秘密份额的验证

2.2 秘密生成阶段

2.3 秘密重构阶段

1) 秘密份额解密

2) 联合解密

B可以计算

3 安全性分析

定理1攻击者无法从Yi或Sij中计算得到p(i)．

定理2若参与者数量少于门限值t则不能从Tj，mj得到共享秘密Kj．

而p(i)是一个t-1次多项式，需要t个点才能确定p(i)，所以若参与者数量少于t则无法从Tj，mj得到共享秘密Kj．

在解密的过程中，没有直接用到p(i)，也无法从解密参数中获取p(i)，可以保证p(x)安全，所以可以用设定的参数安全共享多个秘密．

4 结束语

本文构造了一个可公开验证的门限多重秘密共享方案．

该方案基于拉格朗日插值多项式，且采用两次非交互的验证协议，第一次验证是为了防止Dealer作弊或信息在传递过程中受到信道中噪音的干扰而出现错误；第二次验证是检测参与解密的参与者提供的秘密份额是否为Dealer发送． 只有通过两次验证的秘密份额才能作为重构秘密的份额．

共享多个秘密的思想是将秘密和一个随机参数作二进制加法隐藏起来，只有达到或超过门限值个数的参与者联合才能计算得到这个随机参数． 共享新的秘密只需选择新的参数，因此可以共享任意多个秘密．

本文所构造的方案是将可公开验证和可共享多个秘密这两个优点相结合，是对秘密共享作了进一步研究．