基于二元非对称多项式的公平秘密共享方案1

杨文伟，邢玉清

（信息工程大学，河南 郑州450001）

1 引言

Shamir[1]和 Blakley[2]于 1979年分别提出了(t,n)门限秘密共享的概念，其主要思想是秘密分发者将一个秘密分成n份，并通过安全通道发送给用户，t个或更多的参与者可以使用他们的共享份额来重构秘密；而任何少于t个的参与者则无法恢复秘密，在完备情况下得不到任何关于秘密的信息。

虽然Shamir方案的秘密重建阶段非常简单，但这一阶段对于参与者都是合法份额拥有者的假设并不总是正确的。特别是在有m(m＞t)个参与者合作恢复秘密时，一个并无有效份额的欺骗者（外部攻击者）可能获取其他参与者的至少t个有效份额，恢复出正确的秘密。另外，拥有有效份额的欺骗者（内部攻击者）在秘密重构过程中可能会提交虚假份额，即使这种攻击行为被检测到，但并不能阻止欺骗者获得其他诚实参与者提交的真实份额并恢复出正确的秘密，而诚实的参与者利用获得的虚假份额进行重构只能得到错误的秘密，欺骗者实现独占真实秘密的意图。

针对秘密共享方案中存在的欺骗问题，研究者提出了许多防范措施。Tompa和Woll[3]于1988年最先提出公平秘密共享方案，其构造的方案通过将秘密隐藏在一个很难分辨的序列中，内部欺骗者要想独享秘密只有准确猜测出真实秘密的位置，但该方案无法抵抗异步环境下的攻击。Tian等[4]于2013年构造了一种方案，该方案利用子秘密的一致性来检测是否存在欺骗者，同样将秘密隐藏在一个很难分辨的序列中，并基于3种攻击模型（非合谋攻击、同步合谋攻击、异步合谋攻击）证明方案的公平性。然而Harn[5]指出该方案对于外部攻击者，只能适应于同步环境，而不适应异步环境。2015年，Harn等[6]提出一种公平秘密方案。该方案选择k个多项式，利用线性组合的方式将秘密隐藏在线性组合中，并将秘密隐藏在一个随机选择的秘密序列中，从而实现在异步环境下秘密重构的公平性。但是该方案在欺骗者存在的情况下只能终止协议。

遇到欺骗即终止协议的策略过于严厉，将终止协议作为对欺骗者的惩罚，但同时也使诚实参与者不能恢复秘密，这就提出了欺骗者检测识别的需求，研究者利用不同的数学工具提出了很多针对欺骗检测的方案。Rabin等[7]的方案中引入了第一个作弊者检测识别方案，文献[8,9]方案基于线性纠错码和通用散列函数构造欺骗识别秘密共享方案，Roy等[10]的欺骗识别基于成对的共享认证密钥。大多数秘密共享方案的欺骗识别是基于Shamir[1]的工作，所有的份额由t-1次多项式f(x)生成。然而，二元多项式F(x,y)也是构造功能性秘密共享方案的基本工具，但基于二元多项式的欺骗识别秘密共享方案很少。Liu等[11]提出了两种基于对称二元多项式的欺骗识别算法，欺骗识别仅基于二元多项式的对称性和插值多项式的线性。但该方案在异步环境下无法识别外部欺骗者，在同步环境中虽然可以识别出内部欺骗者，但无法阻止内部欺骗者独占真实秘密。

本文构造了基于非对称二元多项式的具有未知重构轮数的秘密共享方案，在该方案中，使用非对称多项式生成共享份额，利用非对称多项式次数比较高的变量构造多项式份额。多项式份额次数远高于t-1且不需要被重构，可以随机选择高次多项式上的点生成秘密评估点，通过简单运算即可实现对攻击者的检测和识别。并且该方案在攻击者存在时并不是选择立即终止协议，在剔除识别出的欺骗者后，不少于t个诚实参与者依旧可以继续合作完成秘密重构，有效保证诚实者的权利。而且该方案可有效防范同步及异步环境下内部及外部攻击者的欺骗，有效保证了方案的安全性和公平性。

2 预备知识

本节简要介绍 Shamir的(t,n)秘密共享方案（该方案也是基于二元多项式的(t,n)秘密共享方案的基础）以及对攻击者的定义分类及对秘密共享公平性的定义。

2.1 Shamir的(t,n)秘密共享方案

Shamir的(t,n)秘密共享方案利用拉格朗日插值公式构造，由两阶段组成：秘密分发阶段和秘密重构阶段。在秘密分发阶段，秘密分发者D分发秘密s，生成共享份额s1,s2,… ,sn，并将份额si发送给参与者Pi；在秘密重构阶段，t个及以上的参与者可以重建秘密，具体算法如下。

1) 秘密分发阶段

秘密分发者D在GF(q)中随机选择一个t-1次多项式f(x)，使秘密s=f(0)∈GF(q)。秘密分发者D生成n个秘密份额 {s1,s2,… ,sn}，其中si=f(i),i= 1,…,n，并将si发送给相应的参与者Pi。

2) 秘密重构阶段

任何m(≥t)个参与者（不妨假设为P1,P2,… ,Pm）发送他们的共享份额s1,s2,… ,sm，并使用拉格朗日插值公式计算秘密s=f(0)=

2.2 欺骗识别秘密共享方案

欺骗识别秘密共享方案的模型也包括两个阶段。

1) 秘密分发阶段

在这一阶段，秘密分发者D将秘密s划分为n个共享份额s1,s2,… ,sn，并将每个共享发送给相应的用户Pi。

2) 秘密重构阶段

在该阶段，至少有m(≥t)个用户提交自己的共享，以重构秘密。但在这m个共享份额上设计欺骗识别算法来识别作弊者。令L为使用欺骗识别算法识别为欺骗者的用户集。如果(m- |L|)≥t，则不在L中的用户继续使用共享份额重构秘密并输出(s,L)。如果(m- |L|)＜t，则中止协议，并输出(⊥,L)。

2.3 公平秘密共享

秘密重构阶段的欺骗者可以分为两类：外部攻击者和内部攻击者。

外部攻击者：该类攻击者其实并没有从秘密分发者处获取到共享份额，意图伪装成持有份额的参与者参与重构。

内部攻击者：该类攻击者本身拥有真实的份额，但会在重构的某个阶段选择发布虚假的份额，内部攻击者不是完全诚实的参与者，但也不是任意恶意的，可能只是期望除了其本人外越少人知道秘密越好的理性攻击者。

定义1一个秘密共享方案称为公平的，如果满足：

1) 无攻击者时，所有参与者都能重构秘密；

2) 存在外部攻击者时，诚实参与者能够重构秘密而外部攻击者无法重构秘密；

3) 存在内部攻击者时，诚实参与者与内部攻击者要么都恢复秘密，要么都无法恢复秘密，即内部攻击者无法获得比诚实者多的优势。

3 基于二元非对称多项式的公平秘密共享方案

本节给出了基于二元非对称多项式的具有未知重构轮数的秘密共享方案，首先给出针对外部攻击者的利用非对称二元多项式构建的方案 1，该方案能有效防范外部攻击者，但不能有效解决内部攻击者的问题。所以针对方案1进行改进，构造具有未知轮数的方案 2，同时解决外部及内部攻击者的问题。

给定一个安全参数k，假定协议使用有限域F=GF(q)中的值进行操作，其中q= 2k，即F的每个元素都可以用k个比特表示。

3.1 方案1：针对外部攻击者的方案

为了在参与者P= {P1,P2,… ,Pn}中共享秘密s，分发者D利用二元多项式F(x,y)为每个参与者Pi生成共享份额，其中变量y的次数为t-1，变量x的次数为nk，秘密s=F(0,0)，对应的多项式份额fi(x) =F(x,i)，容易看出deg(fi(x) ) =nk≫t-1，但这些多项式永远不需要被重构，因此能够给每一方提供这些多项式上的数量足够多的计算点和相应值来作为秘密评估点。

1) 秘密分发阶段

输入：秘密s

Step1秘密分发者D随机选择二元多项式F(x,y)，其中变量x的次数为nk次，变量y的最高次数为t-1次，且满足F(0,0)=s。并计算fi(x) =F(x,i) ,1≤i≤n。

Step2秘密分发者D随机选择域F上的nk次多项式ri(x) ,1≤i≤n，以及nk个不同的随机非零值αi,1,αi,2,… ,αi,k,1≤i≤n。

Step3秘密分发者D通过安全信道向Pi发送：

① 多项式份额fi(x)，以及秘密共享份额si=fi(0)；

② 多项式ri(x)；

2) 秘密重构阶段

假设有m(m≥t)个参与者（不失一般性，记为P1,P2,… ,Pm）参与重构阶段。欺骗者集合L=∅。

Step1重构参与者Pi选择域F上的随机值ci，并向其余重构参与者广播ci以及多项式gi(x) =fi( x) +ci r i(x)，必须满足deg(gi(x))=nk。

所有重构参与者使用以下规则为彼此投票：如果对于任意的l∈[1,k],aj,i,l+c jbj,i,l=gj(αi,l)都成立，则Pi投票给Pj，否则Pi不给Pj投票。

如果每个参与重构者都得到m-1票，则转入Step2；否则转到Step3以识别攻击者。

Step2所有参与重构者Pi广播多项式fi(x)，并使用秘密评估点验证接收到的多项式，若没有发现错误，则提取份额sj=fj(0)重构秘密s，输出(s,L)；若发现错误则转入Step4以识别攻击者。

Step3所有重构参与者Pi向未参与重构的n-m个用户Pm+1,… ,Pn广播ci以及多项式

每个未参与重构的Pj,j∈ [m+ 1,n]给P1,P2,… ,Pm投票，规则如下：如果 ∀l∈ [1,k],ai,j,l+cibi,j,l=gi(αj,l)都成立 ， 则Pj投 票给Pi，其 中j∈ [m+ 1,n],i∈ [1,m]；否则Pj不会投票给Pi。

设Vi为Pi在 Step1和 Step3中的票数之和。如果可被认为是一个攻击者，并将Pi归入欺骗者集合L，给欺骗者投票的用户也归入欺骗者集合L。如果剩余的重构参与者数量大于t，则转入Step2继续完成秘密重构。否则中止协议并输出(⊥,L)。

Step4所有重构参与者Pi向未参与重构的且不包含在欺骗者集合L中的用户广播多项式fi(x)。

每个不包含在欺骗者集合L中的Pi给这些重构参与者投票，规则如下：如果 ∀l∈ [ 1,k],ai,j,l=fi(αj,l)都成立，则Pj投票给Pi；否则Pj不会投票给Pi。

设Vi为Pi的票数，如果可被认为是一个攻击者，并将Pi归入欺骗者集合L，给欺骗者投票的用户也归入欺骗者集合L。 如果剩余的重构参与者数量大于t，则转入Step2继续完成秘密重构，否则中止协议并输出(⊥,L)。

可以看出方案1是一个好的(t,n)秘密共享方案。令h0(y) =F(0,y)，h0(y)是t-1次多项式，且秘密s=F(0,0) =h0(0)。此外，每个Pi都有一个秘密共享份额si=fi(0) =F(0,i),i= 1,2,… ,n。很容易看出，秘密份额si可以看成是h0(y)产生的份额，即si=F(0,i) =h0(i)，这与Shamir (t,n)秘密共享方案一致。因此，方案1是一个好的(t,n)秘密共享方案，如果参与者都诚实地发布共享份额，则可以成功地恢复秘密。

外部攻击者并没有从秘密分发者获取到共享份额，所以在重构阶段只能猜测域F上的nk次共享多项式，成功的概率远低于但需要注意的是，如果协议只执行一轮，该方案不能阻止内部攻击者取得相对于诚实者的优势，内部攻击者可以在重构的 Step1中诚实发布多项式，但在Step2时选择提交假的份额，虽然该行为依然可以被诚实者发现，但该攻击者已经获取到了足够的份额以完成秘密重构。所以在该方案的基础上，本文针对内部攻击者引入未知重构轮数的改进，以同时防止外部和内部攻击者获得相对于诚实者的优势，达到公平性。

3.2 方案2：针对外部和内部攻击者的方案

防止内部攻击者获得优势的基本思想是构造具有未知重构轮数的方案，秘密发布方在最开始时通过选择随机数的方式确定正确的秘密在秘密序列中的位置，从而将秘密s隐藏在一个长度为k的秘密序列 {v1,v2,…,vq-1,vq,vq+1,…,vk}中，其中，vq+1用来指示真实秘密位置的“标志”。发布方为所有参与者选择k个秘密（真实的和虚假的），并按照方案1产生秘密共享份额。秘密重构参与者共同工作，逐个完成秘密重构。如果过程中存在攻击者，则对攻击者进行检测并剔除。直到在没有攻击者的情况下重构出标志vq+1。当该标志被重构时，所有的重构者都已经获得了真实的秘密，秘密就是之前重构的vq。

1) 秘密分发阶段

输入：秘密s

秘密发布方随机选择q∈ [2,k- 1]以确定s在秘密序列中的位置，并随机选择域F上的k个秘密v1,v2,… ,vk， 满足v1＞v2＞ … ＞vq-1＞vq＜vq+1,s=vq。

对于每一个秘密vr， 秘密发布方利用方案1中的份额生成算法生成共享份额并发送给相应的参与者。

2) 秘密重构阶段

假设有m(m≥t)个参与者（记为P1,P2,… ,Pm）参与重构阶段。

重构参与者一起合作重构秘密 {v1,v2,…vk}，按照v1→v2→…→vq+1的顺序每次重建一个，依次执行：

① 对于每一轮秘密vr,1 ≤r≤q+1，重构参与者按照方案1秘密重构阶段的算法将其重构；

② 若成功重构秘密vr,2 ≤r≤q+1，将vr与vr-1进行比较，若vr＞vr-1，则秘密s=vr，并终止协议；否则，继续下一轮重构工作。

4 方案2的公平性与安全性分析

当所有的重构参与者每一轮都出示真实的秘密共享份额时，即攻击者总数γ=0时，由之前的分析可知方案1是一个好的(t,n)秘密共享方案，即每一轮中任何少于t个秘密共享份额的集合不会泄露关于共享秘密的信息，大于等于t个秘密共享份额的集合可以重构出共享秘密。那么在第q+1轮重构完成后经检验发现vq+1＞vq，从而确认秘密就在之前一轮，得到秘密s=vq。

如果存在攻击者，即攻击者总数γ≥1时，研究方案在同步非合谋攻击、异步非合谋攻击、同步合谋攻击及异步合谋攻击模型下的安全性与公平性。

引理1在方案2中任一重构参与者能正确猜出秘密在序列中的位置的概率是1，其中是k序列中的秘密数。

证明在方案2中，秘密s=vq在构建过程中被秘密分发者随机隐藏在序列 {v1,…,vq-1,vq,vq+1,…,vk}中，而重构参与者不知道s的确切位置，只能通过猜测，其成功的概率为

定理 1在同步非合谋攻击模型下，方案是安全公平的。

证明同步非合谋攻击模型假设所有重构参与者同时出示秘密共享份额且攻击者之间没有合作关系。

首先考虑外部攻击者，假定其希望通过伪装成PI参与到重构中，下面考虑其通过伪造共享多项式获得PJ投票的概率，由投票规则可知其获得PJ投票的概率等于

由同步条件可知，PI没有任何关于gI的先验知识，只能随意猜测一个域上的nk次多项式其正好为gI的概率远低于而当时，多项式gI与gI最多有nk个点上重合，其正好包含αJ,1的概率最多为从而可得

所以，当安全参数足够大时，攻击者伪装为PI得到PJ投票的概率是可忽略的。又攻击者之间不存在同谋，所以其得到别的攻击者投票的概率为0。可知攻击者得到别人投票的概率是可忽略的，该攻击者将被识别出来，无法进入下一轮。

下面考虑内部攻击者的情况，假设在第i轮内部攻击者PI发送伪造的共享多项式由上述分析可知，PI想要在投票阶段获得PJ投票的概率为同理，该攻击者将被识别出来，无法进入下一轮。

假设在第i轮内部攻击者PI发送真实的共享多项式通过检测，但在重构的步骤2中发送伪造欺骗别的参与者，希望能够获得独享重构秘密s的额外收益，这要求其能够准确猜中秘密s=vq所在的轮数，由引理1可知，任一重构参与者能正确猜出秘密在序列中的位置的概率是当安全参数k足够大时，可有效保证方案的安全公平。

综上所述，在同步非合谋攻击模型下，方案是安全公平的。

定理 2在异步非合谋攻击模型下，方案是安全公平的。

证明 异步非合谋攻击模型假设所有重构参与者先后出示秘密共享份额且攻击者之间没有合作关系。对于攻击者而言，最理想的攻击模式是最后出示信息，以获得先前参与者出示的信息。

对于攻击者IP（外部和内部）而言，在重构过程的步骤1中，与定理1中不同地方在于IP可以选择最后发布信息，从而获得之前所有参与者出示的多项式gJ(x),J≠I，则PI通过伪造共享多项式获得PJ投票的概率可表述为。但由于掩护多项式rJ(x),J≠I是随机选择的且相互独立的，所以gJ(x),J≠I是相互独立的，有

上式表明gJ∈[1,m],J≠I对PI构造需要发送的多项式并没有提供有用信息。如定理 1证明所示，攻击者将被识别出来，无法进入下一轮。掩护多项式rJ(x),J≠I的随机选择，同样使PI无法从gJ,J≠I中还原出共享份额fJ,J≠I，从而保证方案是安全公平的。

对于内部攻击者而言，在第i轮重构的 Step2中，可以利用后发优势，在获取到足够多的共享份额之后自行恢复本轮秘密vi，并将其与上一轮秘密vi-1进行比较，若vi＜vi-1，则发放真实的份额进入下一轮；若vi＞vi-1，则秘密s=vi-1，其选择释放假的份额。但此时所有的诚实参与者都已经获得了这个秘密s，因为秘密在前一轮已经被重建，也就是说，对于内部攻击者而言其并没有能够获得独享秘密s的额外收益，但其一旦出示假的份额将被确认为攻击者。这就保证了方案是安全公平的。

综上所述，在异步非合谋攻击模型下，方案是安全公平的。

定理3在同步合谋攻击模型下，当 γ＜ min(t,时，方案是安全公平的。

证明：同步合谋攻击模型假设此攻击模型假设所有参与者同时出示共享份额且有多个攻击者合谋攻击方。

当内部攻击者数目γ≥t时，攻击者可以通过合作掌握超过t的共享份额，从而恢复秘密s。所以为保证方案的安全公平性，首先要求攻击者数目γ＜t。

假设合谋的攻击者（内部的或者外部的）为PI,1≤I≤γ，在重构开始前，攻击者至多知道多项式 fi( x), ri( x), r + 1≤ i≤ n 上的kγ个点。由于kγ小于多项式 fi( x), ri( x)的次数 nk，从而保证了fi( x), ri( x)的安全性。攻击者没有办法搜集到足够多的 fi(0)完成秘密重构，只能出示多项式进入投票阶段。如同定理1证明所示，攻击者想要得到诚实者的投票的概率是可忽略的。所以投票阶段攻击者只能获得同谋者的γ-1票，诚实者至少可以得到别的诚实者的n-γ-1票，为将诚实者与攻击者区分开，只要保证 γ- 1 ＜ n -γ-1，即就可以保证没有外部攻击者能够进入重构阶段的Step2。

同定理一证明类似，在重构阶段的Step2中，合谋攻击者只有在准确猜测到秘密s的位置，才可能达成独享恢复秘密s的目的。

定理4在异步合谋攻击模型下，当 γ＜ min(t,方案是安全公平的。

证明异步合谋攻击模型假设此攻击模型假设所有参与者先后出示共享份额且有多个攻击者合谋攻击方。对于攻击者而言，最理想的攻击模式是最后出示信息， 他们可以获得先前诚实参与者出示的信息。

与定理3证明类似，在重构之前，外部攻击者无法伪造出合适的多项式以获得诚实者的投票。与定理2证明类似，在重构阶段的Step1中，即使攻击者掌握之前所有参与者出示的多项式，由于掩护多项式的存在，攻击既无法得到可以帮助构造多项式的有用信息，也无法从中推测出真实份额，从而阻止外部攻击者进入Step2；在重构阶段的Step2，尽管合谋的内部攻击者可以借助后发优势决定是否出示真实份额，但依然无法阻止诚实参与者获得秘密s，从而保证了方案的安全公平性。

5 方案对比

Liu等[11]提出了两种基于对称二元多项式的欺骗识别算法，该算法并不能完全抵抗异步攻击。例如，当t个或者更多个的诚实参与者先出示共享份额，外部攻击者选择之后出示份额，在出示之前他可以利用这t个真实共享份额进行拉格朗日插值计算得出正确的多项式，得到所有正确的共享份额，从而外部攻击者可以伪装成拥有真实份额的参与者通过检测，并成功得到秘密 s。同时该方案也不能完全抵抗合谋同步攻击，合谋的内部攻击者在重构协议执行时出示错误的共享份额，即使攻击行为被检测到，但也不能阻止攻击者独享秘密 s。本文的安全性与公平性证明了所提方案在4种攻击模式下的安全公平。

Harn等[6]提出了一个对抗内部和外部攻击者的秘密共享方案，但该方案能有效防范外部攻击者和内部攻击者，但该方案依赖于Hash函数是单向碰撞稳固的这一密码学假设来保证每一轮恢复的正确性，在发现有攻击者时也无法对攻击者进行有效的检测确认，一旦有攻击者存在则协议中止。本文方案能够有效对攻击者进行检测确认，而且不依赖于任何的密码学假设。

还有些方案采用其他数学工具来构造欺骗识别方案，如表 1所示。例如，文献[8]利用Reed-Solomon编码和正交测试法，可以识别的欺骗者；文献[9]利用 Reed-Solomon编码和强通用散列函数，可以识别的欺骗者;文献[10]使用成对认证密钥来识别的欺骗者，每一对用户之间需要一个安全的通信通道。所有这些方案[8,9,10]都能够识别m≥t用户参与秘密重建的情况。本文方案可以识别的欺骗者，具有更强的识别能力，并且采用的是非对称二元多项式及，计算简便。

表1 欺骗识别方案比较

6 结束语

本文提出了基于非对称二元多项式的未知重构轮数的(t,n)理性秘密共享方案，该方案可对欺骗者进行有效识别。方案使用非对称多项式中生成多项式份额，利用多项式份额不需要被重构且次数较高的性质随机生成秘密评估点，不依赖于任何密码学假设，只需要简单验算就可实现对欺骗者的检测与识别，并基于同步非合谋攻击、异步非合谋攻击、同步合谋攻击、异步合谋攻击证明了方案的安全公平。