理想型(t,k,n)紧耦合秘密共享构造

白建峰，苗付友

中国科学技术大学 计算机科学与技术学院，合肥230027

秘密共享作为密码学的一个原语（primitive），广泛应用在各种密码系统的构造，比如：安全多方计算[1-2]、组认证[3]、门限密码系统[4-5]等。最早在1979年，由Shamir[6]和Blakley[7]提出的门限秘密共享的概念。通常来说，门限秘密共享是用来保护秘密一种手段，通过将秘密分割成n份子份额（share），其中任意的t份组合在一起可以恢复出秘密。

到目前为止，提出的门限秘密共享方案，主要分为以下几类，一类是Shamir提出的用拉格朗日差值多项式实现的门限秘密共享。一类是Massey[8]提出的使用线性码来实现门限秘密共享。还有一类是Mignotte[9]和Asmuth-Bloom[10]提出的用中国剩余定理实现的门限秘密共享方案。

在门限秘密共享中，任意的t个子份额的组合能够恢复出秘密。当参与者人数为k(k ＞t)个时，实际只需要用到t个份额就可以恢复秘密。多出的子份额对恢复秘密没有任何帮助。这就会带来问题，当k(k ＞t)个参与者参与恢复秘密时，这t个子份额到底由谁出。在理想的通信模型下，k(k ＞t)个参与者同时发送子份额，就会假定k(k ＞t)个参与者会同时收到除自身以外的k-1 个子份额。在现实生活中，这显然是不现实的。现实生活中，通信模型往往是异步的，即参与者发送和接收子份额是有先后顺序的，当参与者收到的子份额数达到t时，就能恢复出秘密。如果该参与者是恶意用户，可以用恢复出的秘密再构造出一个正确的子份额发送给其他用户，且其他用户无法知道该用户是不是恶意用户。

针对上述的问题，阻止这样的非法用户恢复秘密。可以使用可验证秘密共享[11-12]，在秘密恢复过程中首先验证参与者的身份，再进行秘密的恢复。但是这样就会带来多轮的交互式通信和处理时间，以及秘密分发过程中需要额外的信息，来完成验证，带来极大的开销。为了使用一种简单的方法来解决上述问题，Harn等人[13]利用拉格朗日插值多项式的同态特性提出了一种(t,n)秘密安全恢复方案。方案使用l(l≥2)多项式生成l个子份额，即每个参与者拥有l个子份额。它需要满足kl ＞n-1，意味着所有多项式系数个数小于所有参与者的个数。换言之，门限t的个数受限于所有多项式和参与者的个数限制，不够灵活。更严重的是，在2017 年，Ahmadian 等人[14]使用线性子空间的分析方法证明只要超过t+l-1 个参与者就可以恢复出秘密，违背了需要k个参与者都参与恢复秘密的原则，Harn等人的方案是不安全的。

紧耦合秘密共享是近年来提出的另外一种解决方法，具体指的是在秘密恢复过程中，将参与秘密恢复的k(t≤k≤n)个人作为一个整体，紧紧耦合在一起，每个参与者都必须参与到秘密恢复过程中，才能将秘密给恢复出来。相较于上述提到的解决方案，其主要具有以下优点：（1）门限t没有任何的限制条件；（2）秘密分发过程不需要额外的信息；（3）方案是无条件安全的，不依赖于数学难题。其最早是从文献[15]中提出的随机化组件应用在面向组的秘密共享方案中抽象出来。安全性要求提升到攻击者得到任意的k-1 个份额也无法获取关于秘密的任何信息。现已有工作在紧耦合秘密共享的基础上提出了组认证[16]，拓展访问结构[17]等方案。

紧耦合秘密共享典型的应用场景就是用于构造组认证协议，完成对多个用户的身份认证。在实际的应用中，如果需要对多个用户即一个组的用户完成身份认证，有两种解决方案。一是将这个组的每个用户依次进行身份认证。二是将这个组作为整体，针对这个整体的进行身份验证。显然后者的效率更高。紧耦合秘密共享就可以用于构建这样的组认证协议，将多余t个用户作为一个整体，耦合在一起。当这个群组能够恢复出秘密，即对这个群组的身份验证成功，反之失败。

但现用方案中，无论是Harn 等人[13]的方案，还是提出紧耦合秘密共享方案[15，18]本身，仍然存在信息率不为1的，效率低下的特点，具体如下：

（1）紧耦合秘密共享方案[15]是在Shamir秘密共享方案基础上提出。其中秘密s是在Fq上，子份额是在Fp上，然而p、q满足关系式p ＞q+nq2。方案的信息率在区间（1/3，1/2）之间。

（2）紧耦合秘密共享方案[18]是在传统的基于整数环上的中国剩余定理的秘密共享基础上提出。构造条件十分复杂，其中秘密s是在Fp0上，子份额是在Fpi上，p0＜p1＜…＜pn满足两两互素且任意i≠j存在gcd(pi,pj)=1，其中i,j∈{0,1,…,n}。方案的信息率小于1/3。

（3）Harn 等人[13]的方案，需要每人参与者拥有l个子份额，其中kl ＞n-1。方案的信息率为1l。

将会面临这样的问题，有没有什么方法，能够构造出理想型紧耦合秘密共享。

为了解决这个问题，本文主要是通过在基于有限域多项式环上的中国剩余定理的基础上，构造出理想型紧耦合的秘密共享。其克服了文献[13，15，18]中存在的缺陷，主要具有以下几个特点：

（1）在k(t≤k≤n)参与者参与恢复秘密的过程中，任意k-1 参与者无法获取秘密s的任何信息。

（2）从信息率的角度来看，本方案信息率为1，是理想型秘密共享方案。

1 预备知识

1.1 门限秘密共享

一个门限秘密共享机制包括两个阶段，一个是子份额的分发过程Π，一个是恢复秘密的过程Π-1。假定一个秘密共享中，n个参与者的集合为{P1,P2,…,Pn}，秘密s的采样空间为K，n个自份额对应的采样空间分别为K1,K2,…,Kn，秘密s对应的n个参与者的子份额集合为{s1,s2,…,sn}。则分发过程可以描述为：

其中，映射Π:K→K1×K2×…×Kt。

恢复秘密的过程可以描述为：

其中，映射Π-1:K1×K2×…×Kt→K。

定义1（门限秘密共享）如果一个(t,n)门限秘密共享机制包含秘密分发过程和秘密恢复过程，且满足以下特性，称之为门限秘密共享。

（1）正确性

（2）完美隐私性

对于任意的参与者集合B={Pi1,Pi2,…,Pi|B|}且|B|＜t，存在一个秘密分发过程Π:K→K1×K2×…×Kt，使得对于任意给定的秘密s∈K，都有：

定义2（信息率）一个秘密共享机制的信息率定义为：

定义3（理想型秘密共享）一个秘密共享机制满足信息率ρ=1，则秘密共享称之为理想秘密共享方案。

理想型秘密共享为信息率最大的情况下的秘密共享，其可以理解成信息编码中的编码效率。Shamir秘密共享方案中，子份额和秘密的采样空间都是有限域Fp。它也是典型的理想型秘密共享方案。

1.2 中国剩余定理（CRT）

引理（CRT）若表示任意环R上互素的理想，且则 存 在 同 构 关 系R/I2×…×R/Ik。

上述引理是中国剩余定理在任意环上的一般形式。对于任意两两互素的理想，能够高效地计算出一个“CRT基”。在上述引理中，即：对于任意且属于一组CRT基。

从上述引理中的同构关系中，任意给定的向量w=能够在商环R/I上计算出唯一解

1.3 Ning等人的CRT门限秘密共享方案

Ning 等人方案[19]可以理解成Asmuth-Bloom 方案[1]在有限域多项式环上的推广。

（1）初始化

假定n个参与者的集合为{P1,P2,…,Pn}，p为一个素数。寻找n个有限域Fp上d阶首一不可约多项式，m1,m2,…,mn∈Fp[x]，秘密s是d-1阶多项式，m0=xd。其中p和n+1 个d阶多项式为公开信息。

（2）秘密分发

①可信第三方（dealer）构造出多项式F=s+α·m0，其中α是有限域Fp上的随机多项式，阶满足deg(α)=

（3）秘密恢复

①任意t个参与者参与恢复秘密，例如：集合{P1,P2,…,Pt} 。将模数m1,m2,…,mt和对应的子份额{s1,s2,…,st}发送给秘密恢复者。

②秘密恢复者根据模数m1,m2,…,mt，计算出一组CRT基c1,c2,…,ct。并执行计算再由计算出秘密s。

以上的秘密恢复过程可以看成使用中国剩余定理解以下的同余方程组：

2 方案构造

本章主要介绍构造的(t，k，n)紧耦合秘密共享方案，方案主要有三个过程构成，初始化：选择各种参数包括素数p和模数mi；秘密分发：根据n个同余方程，生成n子份额并分发给每个参与者；秘密恢复：使用中国剩余定理求解出最终秘密。

2.1 具体方案

（1）初始化

假定n个参与者的集合为{P1,P2,…,Pn}，p为一个素数。寻找n+1 个有限域Fp上d阶首一不可约多项式，m0,m1,…,mn∈Fp[x]，秘密s是d-1 阶多项式。其中p和n+1 个d阶多项式m0,m1,…,mn∈Fp[x]为公开信息。

（2）秘密分发

①可信第三方（dealer）根据选定的秘密s构造出多项式F=s+α·m0，其中α是有限域Fp上的随机多项式，阶满足deg(α)≤(t-1)d-1。

②可信第三方由si=F(modmi)生成子份额{s1,s2,…,sn}，分发给每个参与者Pi（对应模数为mi）。

（3）秘密恢复

①假定有k(k≥t) 个参与者恢复秘密，例如：{P1,P2,…,Pk}。它们的模数分别对应m1,m2,…,mk，计算出一组CRT基为c1,c2,…,ck。

②参与者Pi计算出并发送给其余k-1 个参与者。式中ri是Fp上的均匀随机分布的多项式，且满足deg(ri)=(k-1)d-1。

计算出秘密s。

2.2 具体实例

以下实例以(2,k,3)紧耦合门限秘密共享为例，具体的构造过程如下：

（1）初始化

选取素数p=17，参与者集合为{P1,P2,P3}，其对应的多项式分别为m1=x2+9x+11，m2=x2+5x+5，m3=x2+13x+1。此外，m0=x2+3x+1。

（2）秘密分发

可信第三方选取秘密s=5x+7，构造出F=s+α·m0=2x3+7x2+10x+8，其中α=2x+1。由si=Fmodmi分别计算出参与者P1,P2,P3对应的子份额为s1=2x+10，s2=15x+6，s3=10。

（3）秘密恢复

假设现在3个参与者{P1,P2,P3}参与恢复秘密。由模数m1,m2,m3得到一组CRT 基c1,c2,c3。其中c1=13x5+5x4+14x3+2x2+15x+11，c2=12x5+5x4+15x3+16x2+7，c3=9x5+7x4+5x3+16x2+2x。再由每个参与者Pi分别计算出Mi=si·ci+ri·m0。分别如下：M1=9x6+7x5+7x4+2x3+x2+15x+9，M2=10x6+12x5+13x4+2x3+14x2+15x+7，M3=5x4+15x3+5x2+3x+11，其中随机数r1=3x3+5x2+10x+1，r2=x3+10x2+15x+16，r3=12x3+x2+x+11。

3 方案分析

本章首先分析方案满足正确性和紧耦合秘密共享的安全性，接着分析方案特性，即：该方案是信息率为1的理想型秘密共享。

3.1 正确性分析

定理1 在本文的方案中，任意给定k(k≥t)个M1,M2,…,Mk，存在一个多项式时间的算法通过CRT唯一确定秘密s。

证明在秘密恢复过程中：

由引理1可知：

因此：

定理得证。

3.2 安全性分析

只需要考虑最坏情况下，方案的安全性。即：当有k(t≤k≤n)个参与者恢复秘密的时候，在给定k-1 个Mi的情况下，无法获取秘密s的任何信息。

定理2 在本文的方案中，给定任意的Mi,i∈{1,2,…,n}，无法获取到关于子份额si的任何信息，即

证明已知，其中ri是Fp上的均匀随机分布的多项式，且满足deg(ri)=(k-1)d-1。式中CRT基ci满足deg(ci)≤kd-1，秘密子份额si和公开多项式参数m0，分别满足deg(si)=d-1和deg(m0)=d。

由上述阶的大小关系，可以知道deg(ri)=(k-1)d-1，多项式ri具有(k-1)d个系数，采样空间大小为。deg(si)=d-1，多项式秘密子份额si具有d个系数，采样空间为pd。因为k≥t≥2，所以ri的采样空间远远大于si的采样空间。

命题得证。

定理3 假定k个参与者参与恢复秘密，任意给定k-1 个M1,M2,…,Mk-1，无法获取关于秘密s的任何信息。存在：

证明已知Mi=si·ci+ri·m0，其中ri是Fp上的均匀随机分布的多项式，且满足deg(ri)≤(k-1)d-1。

由引理1可知，通过k-1 个Mi，计算出结果如下：

其中{c1,c2,…,ck}是模数{m0,m1,…,mk}的CRT基。

则集合A为在知晓k-1 个Mi情况下，F′的采样空间。集合B为秘密s的采样空间，故：

命题得证。

由定理2可知，给定任意的Mi，无法获得si的任何信息。由定理3可知，k个参与者参与恢复秘密的情况下，给定任意k-1 个Mi，无法获得秘密s的任何信息。因此本文的方案是安全的。并且不依赖于任何的数学难题，属于无条件安全。

3.3 方案特性分析

定理4 本文的方案是理想的门限秘密共享方案。

证明由本文的方案可知，秘密s和子份额si满足deg(s)=deg(si)，采样空间都为pd。因此信息率：

所以定理得证。

在这里，需要提醒的是子份额属于每个参与者需要保密的信息。在本文的方案中，每个参与者持有的子份额就是si，但在实际恢复秘密过程中，每个参与者提供的是Mi。

在表1 中列举了紧耦合秘密共享方案和相关方案的比较。

表1 相关方案的比较

4 结束语

本文主要对基于中国剩余定理的紧耦合秘密共享进行推广，将CRT推广到有限域的多项式环上，构造出理想型紧耦合秘密共享方案。

下一步研究将会考虑如何将本方案和具体的应用场景结合起来，构造出认证协议等具体的应用。