公开可验证

公开可验证（精选8篇）

公开可验证 篇1

0 引言

签密由Zheng1997年提出,它是一种公钥密码原型,其设计思想是在一个逻辑步骤内同时完成数字签名和公钥加密两项功能,从而其计算量和通信成本都要低于传统的“先签名后加密”方式。因此,签密特别适用于能量受限的(如低能移动元件,灵通卡和新兴传感器等),既需保密性又需认证性的消息传输环境中。签密技术已经得到广泛应用,如电子现金支付等。

1 新方案及其安全性与效率

1.1 新方案的描述

Setup:设G1为由p生成的循环加群,阶为q,G2为具有相同阶q的循环乘法群,e:G1×G1→G2为一个双线性映射。定义四个安全的Hash函数,H1:{0,1}*→G1,H2:{0,1}*→Zq,H 3:G1→Z q和H4:G2→{0,1}n+|G1|。PKG随机选择一个主密钥s∈Zq*,计算Ppub=sP。PKG公开系统参数{G1,G2,n,e,P,Ppub,H 1,H 2,H 3,H 4}保密主密钥s。

Keygen:给定一个用户U的身份IDU,PKG计算该用户的私钥SU=sQU,其中QU=H 1(IDU)为该用户的公钥。在这里,记发送者Alice的身份为IDA,公钥为Q A,私钥为S A,接收者Bob的身份为IDB,公钥为QB,私钥为S B。

Signcrypt:为了发送一个消息给Bob,Alice执行以下步骤:

(1)随机选取k∈Zq*;

(2)计算W=kP和V=k-1(H2(m)Ppub+H 3(W)SA);

(3)计算w=e(Ppub,QB)k和c=H4(w)⊕(m||V);

(4)发送密文σ=(c,W)给Bob;

Unsigncrypt:当收到密文σ时,Bob计算w=e(W,SB),恢复消息m||V=c⊕H4(w);

Verify:如果等式e(W,V)=e(P,Ppub)H2(m)e(Ppub,QA)H 3(W)成立,Bob接受这个消息m,否则认为σ不合法。

1.2 安全性

定理1在随机预言模型中,若存在一个IND-IBSC-CCIA敌手Malice能够在t时间内,以ε的优势赢得游戏(他最多能进行qi次H i询问q(i=1,2,3,4)),q s次Signcrypt询问,qu次Unsigncrypt询问,则存在一个区分者C,能够在t'

证明:设区分者C收到一个随机的BDH问题实例(P,aP,b P,cP),他的目标是计算出e(P,P)abc。C把Malice作为子程序并扮演IND-IBSC-CCIA游戏中的Malice的挑战者。游戏一开始,C将系统参数发送给Malice,其中Ppub=cP。C在接受挑战的过程中,维护六张表:L1,L2,L3,L4,LS和LU。这些表初始为空。其中L1,L2,L3和L4分别记录Malice对随机预言机H1,H2,H 3和H 4的询问,而LS用于记录C模拟签密预言机,LU用于记录C模拟解密预言机。详情如下:

H1询问:C首先从1,2,...,q1中选取一个随机数ib:这里假设Malice不做重复的询问。

对于Malice的第i次H 1询问,如果i=ib,回答H1(IDU)=bP并设置IDb=IDU,否则,从Zq*中随机选取x,计算QU=xP,SU=xP pub,并将(IDU,QU,SU,x)添加到L1中,回答H1(IDU)=QU。

H 2询问:如果(m,h2)在表L2中,返回h2,否则从Zq*中随机选取h2,将(m,h2)添加到L2中,返回h2。

H 3询问:如果(W,h3)在表L3中,返回h3,否则从Zq*中随机选取h3,将(W,h3)添加到L3中,返回h3。

H 4询问:如果(w,h4)在表L4中,返回h4,否则从中随机选取h4,将(w,h4)添加到L4中,返回h4。

Keygen询问:假设Malice在执行Keygen询问之前已经执行过H 1询问。如果IDU=IDb,终止模拟;否则在表L1中查找IDU对应的条目(IDU,QU,SU,x),返回SU。

Signcrypt询问:假设Malice在对ID1和ID2执行Signcrypt询问前已经执行过H 1询问。在这里,我们分两种情况考虑。

在表L1中查找到条目(ID1,Q1,S1,x)。从Zq*中随机选取k并计算W=kP。计算h2=H2(m)(H2(m)可以从上述的H2询问获得)。计算h3=H3(W)(H3(W)可以从上述的H3询问获得)。计算V=k-1(h2Ppub+h3 S1)。计算Q2=H1(ID2)。计算w=e(Ppub,Q2)k。计算c=H4(w)⊕(m||V)(H4(w)可以从上述的H 4询问获得)。返回(c,W)。

从Zq*中随机选取k并计算W=kP pub。计算h2=H2(m)(H2(m)可以从上述的H 2询问获得)。计算h3=H3(W)(H3(W)可以从上述的H 3询问获得。计算V=k-1(h2P+h3 b P)。

在表L1中查找到条目(ID2,Q2,S2,x)。计算w=e(W,S2)。计算c=H4(w)⊕(m||V)(H4(w)可以从上述的H 4询问获得。返回(c,W)。

Unsigncrypt询问(c,W):假设Malice在对ID2执行Unsigncrypt询问前已经执行过H 1询问。在这里,我们分两种情况考虑。

在表L1中查找到条目(ID2,Q2,S2,x)。算w=e(W,S2)。如果w∉L4,返回符号"⊥";否则计算m||V=c⊕H4(w)。如果ID1=ID2或ID1∉L1,返回符号"⊥";否则计算Q1=H1(ID1)。如果m∉L2,返回符号"⊥";否则计算h2=H2(m)。如果W∉L3,返回符号"⊥";否则计算h3=H3(W)。如果e(W,V)≠e(P,Ppub)h2e(Ppub,Q1)h3,回符号"⊥";否则返回m。

按以下的步骤遍历表L4中的条目(w,h4)。如果ID1=IDb,移到表L4中的下一个条目并且重新开始。计算m||V=c⊕H4(w)。如果ID1∈L1,找到L1中的Q1和S1;否则移到表L4中的下一个条目且重新开始。如果m∈L2,计算h2=H2(m);否则移到表L4中的下一条目且重新开始。如果W∉L3,计算h3=H3(W);否则移到表L4中的下一条目且重新开始。如果等式e(W,V)=e(P,Ppub)h2e(Ppub,Q1)h3成立,返回消息m,否则移到表L4中的下一条目且重新开始。如果遍历完表L4中所有的条目还是没有消息返回,则返回符号"⊥"。

在经过多项式有界次上述询问后,Malice输出两个希望挑战的身份ID A,IDB和两个消息m0,m1。如果IDB≠IDb,C终止这个模拟;否则随机选取V*∈G1,d∈{0,1},令W*=aP,w=h(h就是BDH问题的候选答案),计算c*=(md|V*)⊕H 4(w),然后提交挑战密文σ*=(c*,W*)给Malice。

Malice经过第二轮询问,这些询问同第一轮相同。在模拟结束时,Malice输出一个d'作为对d的猜测。如果d'=d,C输出h=e(W*,SB)=e(P,P)abc作为BDH问题的答案;否则C没有解决BDH问题。

不可伪造性:由于Paterson方案在适应性选择消息攻击下能抗存在性伪造,所以我们的方案也同样能抗存在性伪造。因为新方案解签密后就是Paterson方案。

公开验证性:解签密后,提交(m,W,V)给第三方验证者,验证者检验等式e(W,V)=e(P,Ppub)H 2(m)e(Ppub,QA)H 3(W)是否成立即可。此过程不需要接收者Bob的私钥S B,因此是可公开验证的。

不可否认性:既然我们的方案是不可伪造的,又是可公开验证的,如果Alice确实签密过一个消息,她就不能够否认。

前向安全性:即使Alice的私钥被意外泄露或偷走,第三方也不能计算会话密钥w=e(W,SB)。因此,新方案满足前向安全性。

1.3 效率

从计算量和通信成本来评价新方案。表1给出了我们的新方案与几个基于身份的签密方案的性能比较。为了简便,我们用Ex,Mu,Pa分别表示G2中的指数运算次数、G1中的标量乘运算次数和双线性对运算次数,x(+y)表示需要x次双线性对运算,y次双线性对预计算。Chen和Malone-Lee在文献中宣称他们的方案在可证明安全方案中是效率最高的,只需3次对运算,而我们方案仅需2次对运算。

2 对李发根方案的分析

2.1 方案描述

Setup设G1为由P生成的循环加群,阶为q,G2为具有相同阶q的循环乘法群,e:G1×G1→G2为一个双线性映射。定义四个安全的Hash函数,H1:{0,1}*→G1,H2:{0,1}*→Z q,H 3:G1→Z q和H 4:G2→{0,1}n。PKG随机选择一个主密钥s∈Zq*,计算Ppub=sP。PKG公开系统参数{G 1,G2,n,e,P,Ppub,H 1,H 2,H 3,H 4}保密主密钥s。

Keygen给定一个用户U的身份IDU,PKG计算该用户的私钥SU=sQ U,其中QU=H 1(IDU)为该用户的公钥。在这里,记发送者Alice的身份为ID A,公钥为Q A,私钥为S A,接收者Bob的身份为IDB,公钥为QB,私钥为S B。

Signcrypt为了发送一个消息给Bob,Alice执行以下步骤:(1)随机选取k∈Zq*;

(2)计算R=kP和S=k-1(H 2(m)Ppub+H 3(R)SA);

(3)计算w=e(Ppub,QB)k和c=H4(w)⊕m;

(4)发送密文σ=(c,R,S)给Bob。

Unsigncrypt当收到密文σ时,Bob计算w=e(R,SB),恢复消息m=c⊕H4(w);

Verify如果等式e(R,S)=e(P,Ppub)H2(m)e(Ppub,QA)H 3(R)成立,Bob接受这个消息m,否则认为σ不合法。

2.2 安全性分析

事实上,该方案不是IND-IBSC-CPA安全的,因而更不是IND-IBSC-CCIA安全的。设Malice是敌手,攻击方法如下:

(1)挑战者C输入安全参数k,运行Setup算法,并将系统参数params发送给敌手Malice。

(2)Malice选择两个相同长度的明文m0,m1和希望挑战的两个身份ID A,IDB发送给C。C随机选择d∈{0,1}计算σ=Signcrypt(md,S A,IDB)并将结果σ发送给Malice。

(3)Malice计算Q A=H 1(ID A)得到发送者的公钥,选取明文m0(或m1)和收到挑战密文σ=(c,R,S),直接应用验证算法验证等式是否成立。如果成立,则输出d'=0(或d'=1)作为对d的猜测;否则,输出d'=1(或d'=0)作为对d的猜测。

注意到验证算法中,除消息m外,其它的参数对于敌手Malice来说都是已知的(其中P,Ppub,e,H 2,H 3是系统公开参数,Q A是攻击者选取的发送者ID A的公钥,由系统公开的Hash函数H 1直接计算得到,R和S是Malice收到的挑战密文σ=(c,R,S)中的公开信息),因而,验证过程能够有效进行。由于签密验证算法的有效性,敌手Malice将以压倒性优势猜测到d的值。因此,该方案不是IND-IBSC-CPA安全的。

3 结束语

高安全高效率的签密方案的设计一直是签密技术研究的焦点。可公开验证性和不可伪造性蕴含着不可否认性,没有可公开验证性的方案要解决不可否认性通常是困难和低效的(例如,使用交互式零知识证明技术)。签密又具有保密性,在敌手攻击能力异样强大的开放网络环境中,基于身份的签密方案应具有IND-IBSC-CCIA安全,EUF-IBSC-ACMIA安全以及前向安全和其它一切安全属性。本文基于Paterson的签名方案设计出一个高效的签密方案,并在随机预言机模型下,证明方案是IND-IBSC-CCIA安全和EUF-IBSC-ACMIA安全的。

摘要：本文基于Paterson的签名方案,设计出一个新的可公开验证的签密方案,仅需要两次对运算,是目前已知的基于身份的签密方案中效率最高的。在随机预言机模型下,新方案被证明是存在性不可伪造抗适应性选择消息攻击和身份攻击安全。此外,对李发根等人所设计的一个签密方案进行密码学分析,指出该方案不是语义安全的。

关键词：签密,公开验证,基于身份,语义安全

参考文献

[1]Zheng Yuliang,Digital signcryption or how to achieve cost(signature&encryption<<cost(signature)+cost(encryption).In:Kaliski Jr B.S.ed.,Advances in Cryptology-CRYPTO'97.Lecture Notes in Computer Science1294.Berlin:Springer-Verlag.1997.

[2]Yang Cuomin,S.Wong Duncan and Deng Xiaotie.Analysis and Improvement of a Sign-cryption Scheme with Key Privacy[A].Proceeding of PKC'04[C].LNCS3650.Berlin:Springer-verlag.2005.

公开可验证 篇2

云计算作为一种新兴的网络计算商业服务模式，使得用户可以随时在远端的云服务器存储数据和运行程序.但这种新兴的计算模式在给用户带来诸多便利性的同时，也带来了一些新的安全挑战.用户可能担心云计算平台本身的安全性，比如云平台漏洞和错误配置、管理员的恶意行为等等，而这都可能直接导致用户数据的完整性和隐私性受到危害，导致用户应用程序无法正确执行.这就产生了一个问题：用户如何相信云提供商执行的程序结果是正确的?如何确保存储在远端的数据的完整性和私密性?检测远程服务器返回的结果是否正确的传统解决方案有以下几种：

(1)采用审计的方法，即随机选取服务器执行的一小部分程序进行验证，这就可能发生错误执行的程序没有被服务器验证的情况，所以说这种方法必须假设错误执行的程序的发生频率是很小的;

(2)利用可信硬件和远程证明来保证远程服务器运行的程序是正确的，但是这种方法必须假设云提供商是完全可信的，由于硬件基础设施是在云提供商的控制之下，如果云提供商内部人员恶意控制了可信硬件(如CPU、TPM)，就无法保障云提供商运行的程序的机密性和可验证性.而且还需要假设存在一个可信链，而运行时可信链的建立在可信计算领域依然是一个难题.事实上，在实际的云计算应用场景中这两个假设通常是无法满足的.在云计算场景中，用户无法完全相信云提供商，即使用户出于声誉的考虑相信云提供商本身，也无法相信其内部管理人员;

(3)采用冗余计算的方法，用户可以让多个远程服务器把相同的程序执行多次，然后检测他们返回的结果是否一致.但这在云计算中也是行不通的，云计算中的软硬件平台配置通常是相同的，而这违背了冗余计算中错误必须是不相关的假设，且远程服务器很容易窜通，合谋返回一个错误的程序执行结果.而可证明数据持有(Provable Data Possession，PDP)方法和可恢复证明(Proof of Retrievability，POR)方法可以用来确保存储在远端的数据的完整性，避免云提供商删除和篡改数据.相比PDP方法，POR除了能确保数据的完整性之外，还能确保数据的可恢复性，但是PDP和POR无法确保在云提供商端执行的程序的正确性.另一方面，基于复杂性理论的交互式证明系统(Interactive Proof system，IPs)和概率可验证证明系统(Probabilistically Checkable Proof system，PCPs)以及密码学理论构造的可验证计算协议能以很高的正确率检测出远程服务器返回的程序执行结果是否正确并且不需要对远程服务器(云提供商)做任何假设.可验证计算协议致力于设计验证者与证明者之间的协议，协议允许在计算能力上相对较弱的验证者(如云计算中的用户)将其程序发送到一个计算能力强大的，但不可信的证明者(例如云提供商)，并要求证明者执行其发送的程序.所设计的协议应确保证明者不但返回程序的执行结果给验证者，并且使得验证者相信这个程序执行结果是正确的.其主要目标是使得服务器在发送程序执行结果的同时提供程序正确执行的证据，而用户验证证据的过程必须要比用户自己执行程序的开销小(当然有时由于资源比如存储的限制，用户根本无法自己执行程序，在这种情况下是指和假设用户有足够的资源执行程序时的开销相比要小)。问题描述和协议设计原则问题描述：

验证者V把程序f和输入变量x发送给证明者P，P计算f(x)，并把f(x)赋值给变量y，返回y给V，然后V 和P 以如下方式进行交互：

(1)如果y=f(x)，那么P 应该能向V 证明y的正确性，即使得V 接受y.其中，证明可以通过回答V 提出的一些问题完成，也可以通过给V 提供一个证书完成.(2)如果y≠f(x)，V 能以很高的概率拒绝接受y.可验证计算协议的设计必须满足3个基本原则：(1)协议应该使得验证者的开销比其在本地执行程序f(x)的开销要低，但可以允许证明者为达到协议的目标产生合理的开销，因为提供运行程序的正确性保障本身就需要用户付出一定的代价，在云计算实际场景中，表现为云提供商可能会对需要提供程序正确执行证据的用户收取额外的费用;

(2)不能假设证明者完全遵守协议，也就是说证明者可能是恶意的，这和云计算中不能假设云提供商是完全可信的实际场景也是十分吻合的;

(3)f 应该是通用程序，然而在具体的协议设计中，可能需要对f 表示的程序做一些假设，从而通过限制可验证计算协议适用的应用程序种类使得协议的性能达到实际应用场景的要求，但是可验证计算协议的设计原则依然是尽量能表示通用程序.通常的安全保障工具比如说病毒检测关注的都是不正确的行为的识别和防范，可验证计算协议则有所不同，其不关心证明者可能的不正确行为，比如犯了什么错误，出现了什么故障等等，而只关心其执行程序的结果是否是正确的，却无法推测程序错误执行的原因.这和云计算中用户对于程序执行的要求也是相符的.协议流程和关键

3.1 可验证计算协议流程

可验证计算协议的流程主要包括编译处理和证明系统，具体流程如图1所示.首先是编译处理阶段，验证者V 和证明者P 将高级语言(比如C 语言)编写的程序转换成一组布尔电路集(根据协议的不同，也可以是其他计算模型比如算术电路集或者约束集等).接下来，P 和V 进行一系列协议交互，不失一般性，这里用布尔电路集C表示程序f.V 把输入变量x传输给P，P 计算C，输出程序执行结果y和C正确执行的一组轨迹{C，x，y｝给V，{C，x，y｝也称为C的一个可满足性赋值z.其中，C正确执行的一组轨迹是指C的输入线路被赋值为x，输出线路被赋值为f(x)时，电路集中所有电路门的赋值集合.在程序执行的过程中，证明者P 获得了正确计算电路的执行轨迹{C，x，y｝.如果P 声称的输出y是不正确的，即y不等于f(x)，那么对于{C，x，y｝，就不可能存在一个有效的执行轨迹(电路C正确计算的一个证明).因此，如果P 能够对{C，x，y｝构建一个有效的执行轨迹，那么就一定能使得验证者V 相信它返回的结果是正确的.显然，电路正确计算过程中的各个门的赋值本身就能说明存在有效的执行轨迹.但是，如果需要V 依次验证所有电路门在计算电路过程中的值，进而确定程序是否正确执行，这个工作量和V 本地执行f 是相当的，这就违背了可验证计算协议设计的基本原则.所以，图中第步就需要证明者对程序执行轨迹编码，生成一个很长的字符串，并使得不同的执行轨迹生成的编码在所有不同的位置的取值是不相同的.这样，验证者就可以通过检查随机选择的编码的特定的位置的取值，来验证执行轨迹的有效性，进而对返回的结果采取特定的测试来确定证明者返回的结果是否正确.3.2 可验证计算协议的理论依据

理解可验证计算协议的原理和流程关键在于理解两个等价关系，如3.1节所述，可验证计算协议的流程主要包括编译处理和证明系统.其中，编译处理阶段，编译器完成高级语言程序到电路集或者约束集(可以看做方程组)等计算模型的转化，其实现的理论依据在于等价关系：程序执行的正确性等价于电路集或者约束集可满足问题.计算模型生成原理流程

为了应用IPs和PCPs理论构造可验证计算协议，必须先把高级语言程序转换成IPs和PCPs 判定器可以接受的计算模型，比如说电路集和约束集.Cook-Levin 理论表明这种转换理论上是可以的，因为任何程序f 都可以用图灵机来模拟，同时图灵机可以转换成布尔电路，且不会超过程序的步骤.目前可验证计算协议中编译器都是基于Fairplay和Benjamin 编译器设计的，常用的计算模型主要有电路集和约束集两种.Fairplay编译器和通常的硬件编译器不同，不能使用寄存器，没有时序逻辑，通过Fairplay Web 网站可以获取该编译器.Fairplay 可以用来把高级语言编写的程序编译成一组布尔电路集，但这种高级语言并不是通常所说的高级语言，而是一种类似Pascal或者C 语言的子集的程序语言，称为(安全函数定义)SFDL 语言.Benjamin 提出的编译器继承并改进了Fairplay 编译器，用于把高级语言表示的程序编译成一组约束集.这种编译器也引入了一种类似SFDL 的高级程序语言，称为扩展函数描述BFDL.不失一般性，本文以Benjamin 编译器为例说明从高级语言程序(C 语言为例)转化成约束集的原理和工作流程.BFDL 的语法很容易理解，很多地方都是从C和Pascal语言继承的.BFDL 语言使用C 风格的语法，是一种静态类型语言，支持类型引用：第一部分是类型声明，定义将要使用的数据类型、支持布尔型、整型、结构体和数组.可验证计算协议分类

5.1 依据编译器复杂程度分类

由第3节所述，可验证计算协议主要流程包括编译处理和证明系统两个阶段，所以下文将依据协议流程对不同协议分类，并说明每种分类的特点和典型协议.本文提到的协议中的编译处理都是直接使用Fairplay和Benjamin编译器或者对其改进后使用，生成证明系统可以接受的计算模型.依据可验证计算协议使用的编译器的复杂程度，可以分为简单编译器的可验证计算协议和复杂编译器的可验证计算协议.简单的编译器是指不支持内存随机存取的编译器，即不考虑内存概念，假设程序的输入都来源于验证者.简单编译器的可验证计算协议包括GKR、CMT、Thaler、Allspice、Pepper、Ginger、Zaatar和Pinocchio等，其中Pinocchio是第一个直接接受C语言程序的协议，而其他协议则需要先将C语言程序转化为另一种指定的高级语言比如BFDL语言，然后再转化成证明系统可以接受的计算模型.GKR使用算术电路作为计算模型，相比较之前协议使用的布尔电路减少了程序编译的开销.CMT、Thaler、Allspice、Pepper基本沿用了GKR 中的编译器，且Pepper对算术电路进行了简化，Ginger扩展了算术电路模型表示的程序种类，使得模型包含浮点数类型，不等测试，逻辑表达式，条件语句等等，因而使得模型能表示的程序更加接近于通用程序.Allspice编译器通过增加了一个静态分析器来自动确定并运行Zaatar或GKR两个协议中效率较高的一个，增加了协议的可扩展性.复杂编译器的可验证计算协议包括Pantry和BCGTV.复杂的编译器支持内存操作，这更符合实际应用场景.Pantry中的编译器改进了Zaatar和Pinocchio使用的编译器，结合了不可信存储中使用的技术，使用Merkle-hash树来支持内存随机存取.通过构建一个二叉树来表示内存，二叉树的每个叶节点存储相应内存地址的值，每个内部节点存储作用于其子节点的抗冲突哈希函数的值.每当验证者通过(根节点值、内存地址)二元组访问一个内存地址(叶节点)时，证明者可以通过提供沿叶节点到根节点“证明路径”的所有值来“证明”其返回值是正确的.证明者欺骗验证者的唯一方法是通过找到哈希函数中的冲突.由于Pantry使用的抗冲突哈希函数的计算函数可以有效地表示成约束集，从而使得内存操作也可以有效的表示成约束集.如果把内存操作也看作普通的程序，就可以实现包含内存操作的程序的可验证计算了.更重要的是，Pantry支持“远程输入”，这使其能更好的支持MapReduce程序，且在MapReduce程序中为了降低开销定义了GetBlock和PutBlock两种元操作来代替构造Merklehash树6 基于交互式证明系统的可验证计算协议 本文首先说明交互式证明系统是如何使验证者V确信它接收到的程序执行结果是正确的，.假设要执行的程序是计算输入为x 的函数f.首先，验证者在把输入x 和f传输给证明者，同时随机选取关于输入的低阶多项式扩展函数的值(比如加权和)作为秘密s，s不依赖于要执行的程序，因此无需在输入要执行的程序之前选取秘密s.接下来，P和V 进行一系列交互(d 轮，d 为电路层数)，这些交互的目的在于V 控制并引导P从生成V0(0，0，…，0)=R0递归到Vd(Zd)=Rd(从一层的电路门的值的低阶多项式扩展函数的某个点的值递归到下一层的电路门的值的低阶多项式扩展函数的某个点的值，其中低阶多项式扩展函数是每层的线性组合，如加权和)，Vd是输入x的低阶多项式扩展函数，V 此时的任务就是计算Vd在特定点Zd的函数值，并检测和P 的回复是否一致.在这个过程中，V 发送给P 询问向量Zi=(z1，z2，…，zm)，P 计算Ri=Vi(Zi)，用Ri回复V 的询问.这些询问向量(一共d个)都是相关的，V 递归检测P 对所有询问向量的回复是否一致.V 随机生成的询问向量使得P 对第一个询问向量的回复包含所执行的程序f的结果的声称值.同样的，P 对最后一个询问的回复包含一个关于V 的输入变量的低阶多项式扩展函数的某个点的值的声称Rd.如果P 对所有向量的回复都是一致的，且声称的值Rd和Rd的真实值相匹配，然后P 使得V 确信其遵守了协议，即正确的执行了程序，因此接受结果.否则，V 知道P 在某个点欺骗它，因此拒绝接受.问题与展望

目前可验证计算协议还只是“玩具”系统，由于性能开销过大，仍无法真正用于通用应用程序和云计算的实际场景中.本文说这些协议接近实际场景，是因为相对于相关理论的直接实现所产生的开销来说，这些协议已经有了质的飞跃.在特定构造的程序中，这些协议还是有意义的.而且，在某些需要牺牲性能来换得安全性的场景下，比如在高确保计算场景中，为了掌握部署在远端的机器的运行是否正常，通常愿意花费比较大的代价.更幸运的是，现有可验证计算协议基于性能的考虑要求证明者有大量空闲的CPU周期，验证的程序有多个不同的实例(同一程序、不同输入)，这些和数据并行的云计算场景十分吻合，因而研究可验证计算协议，对于解决引言中提出的云计算中的程序执行的可信问题从而构建可信的云计算是有意义的.然而，可验证计算协议领域以及其构建可信云计算领域在以下几个方面还有待进一步的研究：

(1)相关的理论工具还有待于进一步改进.一方面需要通过理论工具的研究和改进来降低验证者和证明者的开销，尤其是要把证明者的开销降低到一个合理的范围，使得协议真正能用于实际的场景中.验证者的开销可以分为固定的开销(可以分摊，通常指每个程序或者每次批处理的初始阶段的开销)和可变的开销(程序的每个实例的验证开销).研究如何降低验证者的可变开销，研究能否使用密码学操作和复杂的理论工具来降低或取消验证者初始阶段的开销.改进基于无预处理的论证系统的可验证计算协议，使得其能用于实际场景.另一方面，研究利用理论工具来建立更加合理的计算模型，用于高效的表示通用程序，从而提高协议的效率.目前的系统要不不能很好的处理循环结构，要不就是编译的代价太高无法实用.BCGTV协议可以处理独立于数据的循环的程序，但是其对于程序转化成特殊的电路模型引入了过大的开销.BCGTV和Pantry协议可以处理包含RAM 的程序，但是Pantry协议对内存操作转换成约束集也引入了过大的开销(目前，在T 机器运行的一些计算机程序原本需要T 步，转换成由电路计算远远超过T 步).有必要改进这两种计算模型使得其既可以很好的处理循环结构和RAM，又不至于引入过大的开销.或者设计新的更加高效的计算模型来表示通用计算.(2)在系统和编程语言方面值得研究.针对已有的电路和约束计算模型，设计定制的高级程序语言，降低程序到计算模型的转化开销.目前，一些可验证计算协议编译处理和证明系统的工作已经有所交叉，而且很多协议在并行计算中性能更优，由于计算模型的高效转化，可以使得验证的效率提高.所以设计一整套相应的高级语言程序、计算模型、验证机器十分必要.目前还没有协议在真实的云计算场景中测试，开发适用于云计算实际场景的支持并发、访问控制、合理结构的数据库应用的可验证计算，使得协议支持多用户数据库，才能更好的构建可信的云计算.(3)改变协议的目标和原则，减少可验证计算

协议的限制条件，比如可验证计算协议的无条件假设，即除了密码学假设之外不做任何其他假设.如果假设多个证明者之间不能相互交互、合谋，那么多证明协议相对单证明者的开销则降低很多.实际上，如果假设两个证明者至少有一个是计算正确的，就可以使得很多协议能用于特定构造的场景中.(4)增加安全相关的属性用于构建可信的云计算

公开可验证 篇3

一、方案描述

在本方案中设D为秘密分发者,P1,P2,…,Pn是n个参与者,共享的m个秘密为K1,K2,…,Km. 本文所提出的公开可验证多秘密共享方案包括方案初始化、方案的构造和秘密的重构三个部分.

1. 方案初始化

设G1是阶为q( q为素数) 的加法循环群( 这里是椭圆曲线群) ,G2为阶为q的乘法循环群,并且它们之间存在双线性映射e: G1×G1→G2,分发者D独立地选择G1的生成元P和Q,并公布{ q,e,P,Q} .

分发者D随机选取d∈Z*q作为系统主密钥,计算R =d Q. 每个参与者Pi随机选择si∈Z*q作为他的秘密份额及公开身份信息ui∈[m,q - 1],并计算Ri= siQ,Pi将( ui,Ri)发送给分发者D,D要确保ui≠uj( i≠j) 和Ri≠Rj( i≠j) 且Ri≠R. D公布( R,R1,R2,…,Rn) .

2. 方案构造

分发者D按以下步骤执行:

yi) ,i = 1,2,…,n,并根据Lagrange插值多项式构造一个唯一的次数最多为n + m - 1的多项式

( 3) 计算并公布其相关承诺Ci= aiP,( 0≤i≤n + m - 1) .

( 4) 从[m,q - 1]- { uii = 1,2,…,n} 中依次选择n +m - t个最小的整数d1,d2,…,dn + m - t,并计算f( di) ,i = 1,2,…,n + m - t.

由于每个参与者自己选择他的秘密份额,所以分发者不可能成为骗子.

3. 秘密的重构

( 1) 共享验证阶段

参与者Pi用他们的秘密份额si来计算Bi= siR = ( xi,yi) ,然后计算并公布Mi= yiQ. 任何一方都可以通过等式

来检验参与者Pi提供信息Bi的正确性.( 2) 秘密恢复阶段

假设至少t个参与者P1,P2,… ,Pt提供了正确的信息Bi= ( xi,yi) ,则秘密重构者就可以利用点( ui,yi) ( i = 1,2,…,t) 及公开值( di,f( di) ) ,( i = 1,2,…,n + m - t) ,构造一

f( i - 1) ,( i = 1,2,…,m) ,可以得到这m个秘密.

二、方案分析1. 正确性分析

下面我们来验证等式( 1) 的正确性.

2. 安全性分析

任何t - 1个参与者提供他们的共享不能恢复出秘密.

不妨假设t - 1参与者P1,P2,…,Pt -1提供了他们的共享来恢复秘密,由他们的共享只能得到t - 1个点( ui,yi) ( i= 1,2,…,t - 1) ,并且在离散对数问题是困难的和计算Diffie-Hellman问题是难解的条件下,由这t - 1个共享不能计算出其他参与者的共享,然后再结合公开值( di,f( di) ) ,( i = 1,2,…,n + m - t) ,此时只有n + m - 1个点,不能由Lagrange插值多项式得到n + m - 1次多项式f( x) ,不能恢复出秘密K1,K2,…,Km,所以该方案是完善的门限方案.

3. 性能分析

参与者的秘密份额si可以重复使用.

本节的方案中参与者Pi在恢复过程中提供了他们的共享Bi= ( xi,yi) ,而不是Pi的秘密份额为si. 若根据等式Bi= siR0来求si等价于求解椭圆曲线上的离散对数问题,而这是困难的,因此si没有被泄露,重复使用是安全的.

三、结论

本文提出了一个性能更优良的公开可验证的多秘密共享方案,方案除了具有公开可验证性外,还实现了参与者的秘密份额是由自己选取,可以用于下一次加密过程. 并且方案没有使用加密算法,减少了通信代价.

摘要：基于椭圆曲线上的双线性对提出了一个新的公开可验证的多秘密共享方案.该方案不但具有公开可验证性和一次秘密共享过程可以共享多个秘密,而且实现了参与者的秘密份额是由自己选取以及秘密份额可以重复使用.方案的安全性等价于Diffie-Hellman假设及椭圆曲线上的离散对数问题困难性.

基于VMM构建可重用验证平台 篇4

随着SoC设计复杂度的持续增加,验证成为当前SoC以及可重用IP模块设计中面临的最大挑战。虽然有新的验证技术产生[1],但是设计能力与验证能力之间的差距仍然巨大。特别是在芯片开发过程中,通常集成了不同厂商的多个IP模块。一方面需要将使用不同验证策略的测试案例集成到一起,另一方面需要在同一个验证环境中,将不同级别的IP组件进行扩展或者组合,这样必然造成验证周期的延长[2]。为了解决上述问题,需要开发统一的验证平台,对不同设计的不同级别进行功能验证。同时,该验证平台还能够对验证过程进行有效的控制,确保功能验证的完整性。利用SystemVerilog支持的VMM验证方法学,能够建立层次化的可重用验证平台[3]。同时,Synopsys 公司的VCS仿真验证工具完全支持SystemVerilog描述的结构功能,能够实现随机激励的自动生成[4]、覆盖率统计和断言检查,从而有效完成整个设计的验证过程。

1 SystemVerilog语言和VMM验证方法学

1.1 SystemVerilog语言

面向对象的类结构支持继承机制,利用类结构建立事务和事务处理器,具有代码模块的独立性、动态连接性和易于维护性等特点。允许使用者进行代码复用,舍去许多麻烦的设计验证细节,降低验证的复杂度。

SystemVerilog硬件设计验证语言融合了面向对象的编程技术[5,6],与以往的过程性设计语言(Verilog或VHDL)相比,更易于建立验证平台。利用基于面向对象的类结构,对需要处理的数据进行抽象和包装,利用基于事务的工作机制代替基于引脚的信号变化,从而可以在事务上进行验证,提高验证效率。

1.2 VMM验证方法学

VMM是Synopsys公司推出的基于SystemVerilog的验证方法学,推荐层次化的验证架构[7,8]。标准的验证平台共分五个层次实现,每个层次又包含多个验证组件,结构如图1所示。

类(Class)是构成VMM验证平台的核心,每个层次的验证组件都是基于类结构实现。信号层为最低层次,用于实现验证平台与设计电路(DUT)之间的信号连接。命令层中的驱动器执行上一层次送来的命令,然后产生相应的驱动信号送入DUT。监视器对DUT的输出信号进行监视,并生成相应的控制命令。功能层则由场景层的生成器驱动,并为命令层提供事务命令,同时将转换后的事务命令送入到记分板。检查器则对来自于记分板和监测器的结果进行对比。场景层中包含生成器,主要是生成带约束的随机激励。测试层为测试台的顶层,是用户自定义的测试案例,包含对激励的约束。该层的行为确定其他层次的作用,启动和控制整个测试平台的运行。在验证过程中,利用功能覆盖率评估测试进度,用于指导修改随机激励的约束条件,最终达到覆盖率要求。

在建立测试平台时,并不要求建立所有的测试层次,需要根据实际情况进行适当改进[9]。当DUT含有多层协议时,则可能需要多个层次。当场景层比较简单时,可以将场景层与功能层进行合并。

2 可重用验证平台

2.1 验证环境

通用异步收发器(UART)主要用于控制设备间的串行通行,在SoC的设计中的应用比较广泛。特别是在SoC的设计中复用UART IP核,能够提高SoC设计效率,降低成本。因此,必须保证UART IP核功能的正确性,需要对其进行充分的功能验证。

利用VMM验证方法学建立的UART验证环境主要由4部分组成[10],如图2所示。

在顶层模块(rs232_top.sv)中,利用时钟生成器生成与DUT和测试台连接的时钟信号,并分别将接口(rs232_if.sv)、测试台模块(rs232_test.sv)和DUT(rs232.v)进行实例化。通过接口将测试台与设计模块进行连接,避免了其他外部电路与设计之间的操作,同时降低了错误发生的几率,缩短了调试测试台代码和设计代码的时间。

2.2 验证平台的建立

利用层次化的类结构建立UART的验证平台,组成结构如图3所示。利用SystemVerilog的面向对象特征,所有的验证组件都在单独的类中实现,包括配置和数据事务,生成器、驱动器等,以便于其他类进行调用,并且易于复用和扩展。

(1) 事务类。

根据UART功能验证需求,在一种工作模式下,需要发送或接收多个数据。因此,在该测试台中,通过两个事务类完成UART的随机化配置和数据生成。在配置类中,定义带约束的随机化的UART可配置选项和验证环境的可配置选项,使得在测试环境建立前,确定UART的工作模式和收发数据的次数。在数据类中,定义带约束的随机化的接收发送数据。

(2) 事务处理器类。

事务处理器主要完成接收事务的处理,并传递至下一个事务处理器。事务处理器的生命周期相对于验证环境是静态的,在仿真起始时创建,存在于整个仿真过程。在该验证平台中的事务处理器同样利用类结构实现,包括生成器类、驱动器类、监视器类和环境类。

生成器类提高了激励生成的层次,使得激励的生成与实际的驱动器和监视器等测试台组件分离,从而易于对事务进行修改。该类调用事务描述符,并生成相应的随机事务,同时将事务传递给驱动器。驱动器类则产生UART工作的控制信号,并将配置数据和接收发送数据写入到相应的寄存器中。监视器类则完成对中间事务的检测,并适时将事务输出。环境类中包含生成器类、驱动器类、监视器类等的实例化。在该类中完成验证的整个控制过程,确保所有的验证步骤按照正确的顺序执行。

(3) 回调方法的应用。

回调方法允许使用者在不修改事务处理器代码的情况下,扩展事务处理器的行为。必须在处理器内部对事务执行之前或之后启用回调方法。事务前的回调允许注入故障或者延时。事务后的回调则可以将已经被处理的事务送入记分板或者送入功能覆盖模型中,进行覆盖率数据的采集。

在该验证平台中,利用回调方法创建了三个回调基类的扩展类,分别用于故障的注入、将事务送入记分板和覆盖数据的采集。

(4) 测试案例的设计。

为了达到更高的覆盖率,需要对随机激励的约束进行修改。或者对于随机化激励难以验证的功能,则需要创建特定的测试案例。此时,需要对生成器的功能进行扩展。

该验证平台采样工厂模式,可以在不修改验证环境的情况下,通过只修改测试案例,达到改变随机约束的目的。能够同时支持直接测试和随机测试。需要特别注意的是,每个测试案例都要实例化验证环境,在测试案例中对生成器的父类初始化完成后,再对生成器的子类进行初始化。

在UART的验证中,共创建了以下3个测试案例:

初始测试案例(debug_test.sv):生成的随机事务只与事务描述符内的约束相关。

改进约束的测试案例(constrained_test.sv):在该测试案例中,对配置描述符添加了新的约束。

直接测试案例(driected_test.sv):在该测试案例中,利用专用的事务代替配置描述符中的随机事务。

3 验证结果

利用Synopsys公司的VCS仿真工具运行该验证平台,通过多次反馈分析提高功能覆盖率。先利用修改随机约束和不同的随机种子的方法,生成不同的随机配置和数据。当功能覆盖率不能有效提高时,再进行直接测试。最终,使得各功能覆盖率模型的覆盖指标达到100%,如图4所示。

例如,在随机测试的后期,覆盖率报告显示intr_type的覆盖率为80%,没有采样到intr_type=3′d2的值,表示没有产生UART忙中断。从而通过创建直接测试案例,在发送或接收数据过程中,向线路控制寄存器中写数据,则产生UART忙中断。仿真后再次查看覆盖率统计报告,显示覆盖率为100%。

4 验证平台的可重用分析

利用传统的直接测试方法编写测试台时,没有可重用的验证组件。而在层次化的可重用验证平台中,将验证平台需要实现的整体功能进行划分,利用不同的验证组件进行实现,使得验证更易于进行,也便于对验证平台的功能进行改进。该验证平台的可重用性主要体现在以下两个方面:

一是对于不同的IP模块进行验证时,可以复用验证平台结构,也可以有选择的重用验证组件。例如,对于连接至APB外围总线的多个设备,具有相同的APB接口时序,可以重用验证平台中的激励产生器和总线功能模型,只需要按照具体要求修改激励的约束条件。

二是从模块级到系统级验证的重用。对于SoC进行系统级验证时,主要是验证各个IP模块之间的连接关系、时序关系、地址映射和中断的优先级关系是否符合设计要求。此时,原IP模块各个接口的协议不变,不再使用激励生成器和驱动器,而是由系统级的处理器给IP模块提供相应的激励信号。利用各个组件的“即插即用”特性,仍然可以最大限度的重用模块级验证平台。例如,在对整个SoC进行系统级验证时,就可以在将UART直接与APB总线连接,其它验证组件连接关系不变的情况下进行。监视器、覆盖率模型以及故障注入组件仍然与模块级验证时一样进行工作,确保验证功能的完整性。可见,层次化的验证平台将底层细节抽象成事务级进行管理,减少了对底层细节的控制,从而提高工作效率。验证平台的重用能够使得验证工程师从建立验证环境中解脱出来,允许更多的时间考虑如何更有效的验证设计。

5 结 语

利用SystemVerilog的面向对象特征,易于建立层次化的可重用验证平台。结合带约束的随机验证和覆盖率驱动的验证技术,能够有效提高验证效率,确保验证功能的完整性。各验证组件相对独立,易于重用,具有广泛的适用性。

参考文献

[1]须自明,刘站.各种验证技术在SoC设计中的应用[J].微计算机信息,2006(Z1):120-121.

[2]徐英伟,刘佳.SoC功能验证的特点和方法[J].微处理机,2006,28(2):11-13.

[3]程刚,蔡敏.基于SystemVerilog的SoC功能验证方法研究[J].科学技术与工程,2009,11(22):6814-6818.

[4]刘杰,徐伟俊,夏宇闻.设计验证中的随机约束[J].中国集成电路,2006(1):28-31.

[5]闫沫,张媛.基于SystemVerilog语言的设计验证技术[J].现代电子技术,2008,31(6):8-11.

[6]SPEAR C.SystemVerilog for verification[M].[S.l.]:Springer Science+Business Media Inc.,2006.

[7]BERGENRON J,CEMY E,HUNTER A.Verificationmethodology manual for SystemVerilog[M].[S.l.]:Springers,Synopsys Inc.and ARM Limited,2006.

[8]丁婷婷,申敏.分层式验证平台及覆盖技术在SOC上的应用[J].北京电子科技学院学报,2007,15(2);55-57.

[9]BERGERON J.Writing test-benches using SystemVerilog[M].[S.l.]:Springer Science+Business MediaInc.,2006.

公开可验证 篇5

本文基于文献和离散对数难解性, 提出了一种新的秘密共享方案, 该方案利用新定义的Γ-Mignotte列将文献推广到了一般接入结构上, 使其具有了更加广泛的应用。新方案可以防止欺诈行为, 无论他是分发者还是参与者。

一、Mignotte门限秘密共享方案

设D为秘密分发者, 为参与者集合, S为欲共享的秘密。Mignotte门限秘密共享方案简单描述如下:

1.D选择合适的-Mignotte列, 使得公开选定的-Mignotte列;

2.D计算秘密份额, 将计算得到的n个秘密份额通过安全信道分发给参与者;

3.在恢复阶段, 不失一般性, 参与者p1, p2, …pt将重构秘密S, 这t个参与者提供他们各自的, 构造同余方程组:

利用中国剩余定理则可重构秘密。这里。

而少于t个参与者无法重构秘密S, 甚至得不到关于秘密S的任何信息。

二、基于-Mignotte列的可验证秘密共享方案

1.符号说明。为了给出新方案, 我们需要引入一些符号:为集合的所有子集构成的集合;

:对于给定的集合和给定的整数列, 元素mi的最小公倍数, 记为。

2.方案设计。定义2:设, 若整数列满足:

则, 整数列称为广义 (t, n) |-Minnotte列。

显然, 每个列都是广义-Mignotte列。

定义3:设, 对于接入结构, 若整数列满足:

例1:取接入结构, 根据的定义知:。则据定义3, 整数列18, 3, 5为一列, 这是因为。

对于接入结构和欲共享的秘密S, 新的秘密共享方案如下:

1.初始化阶段。在这个阶段, 秘密分发者D执行如下两步:

(1) 选取适当的Γ-Mignotte列, 使得, 这里

(2) 为每个参与者pi选取一个正整数ni及阶为mi的元素 (选取ni时, 应保证证证是的因数) 。

2.构造阶段。

(1) 分发者D计算, 公开;

(2) 计算秘密份额, 将这n个秘密份额通过安全信道发送给参与者。

3.验证及恢复阶段。

(1) 为了验证分发者的欺诈行为, 任何一个参与者pi通过计算来确认子集获得的秘密份额正确性;

(2) 汇聚秘密份额, 构造同余方程组:

容易看出, 秘密S是上述方程组模的惟一解。这是因为Ii是通过得到的, 且。

例2:令, 我们选择例1中的整数列18, 3, 5。这样, 秘密S介于区间[5, 15]。秘密份额。集合可以恢复秘密S, 但集合只能得到。

三、方案分析

由于在构造阶段, 我们利用了定义3中的-Mignotte列和Mignotte门限秘密共享方案, 所以方案的可行性是无需讨论的, 下面我们重点讨论方案的可验证性。

在验证阶段, 参与者可以利用来验证分发者的真实性。这是因为, 由可得对于正整数ni及阶为mi的元素 (选取ni时, 应保证mi是的因数) 都成立。公开并不会泄漏关于秘密S的任何信息。事实上, 攻击者若利用来获得S相当于求解离散对数这一数学难题。

四、小结

基于Mignotte门限秘密共享方案和离散对数难解性提出了一种新的可验证秘密共享方案, 由于建立在一般接入结构上, 使其具有了更加广泛的应用;方案可以防止欺诈, 无论其为分发者还是参与者;方案虽然增加了验证算法, 但计算量并没有很大增加, 作为需要验证算法的系统是具有可操作性及程序要求的。

摘要：基于Mignotte门限秘密共享方案和离散对数难解性提出了一种基于一般接入结构的可验证秘密共享方案, 方案可以防止分发者或者参与者的欺诈, 作为需要验证算法的系统具有可操作性及程序要求。

公开可验证 篇6

一个可验证的秘密共享方案允许参与者确认其他参与者所提供信息的真实性。Choretal[1]在1985年, 提出了第一个可验证的秘密共享方案, 然后很多文章对它进行了讨论。1995年, Harn[2]提出了可验证的多重秘密共享方案, 但在此方案中, 为了验证秘密份额是否有效, 每个参与者不得不验证个等式。之后, Shao和Cao基于YCH方案[3]提出了一个高效的可验证的多秘密共享方案, 但是它需要事先在秘密分发者和参与者之间建立一个安全信道, 造价比较高。在2008年一个基于非奇次线性递归的秘密共享方案被提出[4]。本方案在此基础上, 提出了一个基于奇次线性递归和椭圆曲线的多秘密共享方案, 在该方案中, 可以验证参与者和秘密分发者的真实性, 并且计算量比较小, 较文献[2]有明显的计算优势。其中运用了ECRSA密码体制和ECDLP的难解性问题。因为子秘密都被隐藏起来, 因此该方案不需要安全信道。与文献[4]比较, 在恢复阶段计算比较简单, 安全性分析显示该方案是计算安全的。

1奇次线性递归 (homogeneous linear recursion , HLR)

定义1 设t为一个正整数, c0, c1, …, ct-1, a1, a2, …, at为实数。一个次数为t的奇次线性递归如下定义:

$[\text{Η}\text{L}\text{R}]\{\begin{array}{l}u{}_0=c{}_0,u{}_1=c{}_1,\cdots ,u{}_{t-1}=c{}_{t-1}\\ u{}_{i+t}+a{}_{1}u{}_{i+t-1}+\cdots +a{}_{t}u{}_i=0(i\ge 0)。\end{array}$

定义2 [HLR]定义如下一相关等式

xt+a1xt-1+…+at=0 。

假定这个等式有t个根, 当然这个假设在复数域上是成立的。事实上这些根不一定完全不同, 不妨设不同的根为α1, α2, …, αl, 相应的重数为m1, m2, …, ml, 换句话说, [HLR]的相关等式可以记为:

(x-α1) m1 (x-α2) m2… (x-αl) ml=0, 其中m1+m2+…+ml=t。

定理1 假设 (ui) 是[HLR]中所定义的, 而[HLR]的相关等式的根为α1, α2, …, αl, 相应的重数为m1, m2, …, ml, 可得

ui = p1 (i) α${}_1^i$+ p2 (i) α${}_2^i$+ … + pl (i) α${}_l^i$。

对于任意的j, j=1, 2, …, l, 有:

pj (i) =A0+A1i+…+A (mj-1) i (mj-1) 。

也就是说pj (i) 是一个次数不超过mj-1的多项式。

2环ZN上的椭圆曲线

定义3 设N=p1p2, p1和p2为大于3的素数, ZN上的同余方程y2≡x3+ax+b (mod N) 的所有解 (x, y) ∈ZN×ZN, 连同一个无穷原点Ο, 共同构成ZN上的椭圆曲线y2=x3+ax+b, 其中a, b是满足gcd (4a3+27b2, N) =1的两个整数。在EN (a, b) 上定义的加法与在素数域上椭圆曲线定义的加法法则一样。

引理1 设EN (a, b) 为一个满足gcd (4a3+27b2, N) =1和N=p1p2 (p1, p2为素数) 的椭圆曲线, 设nN=lcm (#Ep1 (a, b) , #Ep2 (a, b) ) 。对于任意的p∈EN (a, b) 和任意的整数k, 都有 (knN+1) p=p。证明见文献[6]。

定义4 定义在椭圆曲线上的RSA密码体制满足以下三点。

2.1密钥的产生

使用者U选择两个大素数p1, p2且p1≡p2≡2 (mod 3) , U计算N=p1p2, nN=lcm (p1+1, p2+1) 。然后U选择一个整数e, 且gcd (e, nN) =1, U计算一个整数d使得ed≡de≡1 (mod nN) 。其中公钥为{N, e}, 私钥为{d}。

2.2加密过程

一个明文M= (mx, my) 是一个整数对, mx∈ZN, my∈ZN, 设M= (mx, my) 是EN (0, b) 上的一个点, b是由mx和my决定的, 计算

C=Ek (M) =eM。

2.3解密过程

接收者收到C以后, 计算

M=Dk (C) =dC。

定理2 设N=p1p2, nN=lcm (p1+1, p2+1) 和ed≡de≡1 (mod nN) 。在EN (0, b) 上如果有C=eM, 那么M=dC。

证明dC=deM= (knN+1) M=M (引理1) 。

3方案构成

3.1初始化阶段

设S={S1, S2, …, Sk}表示在n个参与者中共享的k个秘密, U={U1, U2, …, Un}表示n个参与者。秘密分发者选取两个大素数p1, p2, 计算N=p1p2。选择一个Q∈EN (0, b) , 使得在[Q]上离散对数是难解的。秘密分发者选择一个整数α≠0, 定义以下相关的等式

(x-α) t=xt+a1xt-1+…+at=0。

秘密分发者选择一个素数q (q>ai) i=1, 2, …, t, 并在公告牌上公布{N, Q, α, q}。

每一个参与者Ui随机选择一个整数si作为他的秘密份额, 并且计算Ri=siQ, 然后将 (Ri, i) 通过公开的信道传送给秘密分发者。秘密分发者必须确保对所有的i≠j都有Ri≠Rj, 否则要求参与者重新发送。

3.2秘密分发阶段

秘密分发者按以下步骤进行分发:

(1) 任意选取一个整数e使得gcd (e, nN) =1, 计算d使得ed≡de≡1mod (φ (nN) ) ;

(2) 计算R0=dQ和Bi=dRi (i=1, 2, …, n) ;

(3) 计算Ii=xBi+yBi (i=1, 2, …, n) 。xBi是Bi的横坐标, yBi是Bi的纵坐标;

(4) 考虑如下的奇次线性递归等式:

$\{\begin{array}{l}u{}_0={\rm I}{}_0,u{}_1={\rm I}{}_1,\cdots ,u{}_{t-1}={\rm I}{}_{t-1}\\ u{}_{i+t}+a{}_{1}u{}_{i+t-1}+\cdots +a{}_{t}u{}_i=0\text{m}\text{o}\text{d}q(i\ge 0)；\end{array}$

(5) 计算ui, t≤i≤n+k;

(6) 计算yi=Ii-ui-1, t<i≤n和ri=Si-ui+n;1≤i≤k;

(7) 公布{R0, e, r1, r2, …, rk, yt+1, …, yn}。

3.3秘密恢复阶段

每个参与者Ui可以通过计算siR0得到自己的秘密伪份额Bi (siR0=sidQ=dsiQ=dRi=Bi) 。假设t个参加秘密恢复的参与者{ui}i∈I (I⊆{1, 2, …, n}) 提供自己的秘密伪份额Bi, 每个参加恢复的参与者都可以验证其他参与者的秘密伪份额Bj是否真实 (eBj=edRj= (knN+1) Rj=Rj) 。秘密计算者用t个数对 (i-1, ui-1/αi-1) i∈I构造t-1次多项式

$\begin{array}{l}p(x)={\displaystyle \sum _{i\in {\rm I}}\frac{u{}_{i-1}}{\alpha {}^{i-1}}}{\displaystyle \prod _{\begin{array}{l}j\in {\rm I}\\ j\ne i\end{array}}\frac{x-(j-1)}{(i-j)}}\text{m}\text{o}\text{d}q\\ =A{}_0+A{}_{1}x+\cdots +A{}_{t-1}x{}^{t-1}\text{m}\text{o}\text{d}q\end{array}$

而ui=p (i) αimod q (i≥t) , 然后计算Si=ri+ui+n (1≤i≤k) 。

4方案的安全性和动态性分析

4.1安全性分析

4.1.1 t-1个或更少的参与者试图恢复秘密

p (x) 是[HLR]的相关方程, 它是t-1次多项式。假设t-1个或更少的参与者试图恢复秘密, 那么他们只能得到t-1对或更少对$\left(i,\frac{u{}_i}{\alpha {}^i}\right)$。因此他们没有办法来决定t-1次多项式p (x) 。因此无法推出其他任何秘密。

4.1.2 攻击者试图从公开的信息Ri获得参与者Ui的子秘密si

因为Ri=siQ, 而Ri中si的安全性是基于ECDLP 的难解性, 没有方法可以解决ECDLP。因此si是安全的。

4.1.3 在恢复阶段, 参与者Ui试图获得别人的秘密sj

因为Bj=sjR0, 而Bj中sj的安全性是基于ECDLP 的难解性。因此sj是安全的。

4.1.5 攻击者试图从R0获得d

因为R0=dQ和ed≡de≡1 mod (φ (nN) ) 。因此R0中d的安全性依然基于ECDLP和ECRSA, 因此无法获得d。

4.2动态性分析

(1) 如果秘密Si需要更新时, 只需要更新公告牌上的ri的信息即可。

如果想要删除某个Sj时, 只需要从公告牌上删除相关的信息即可。

(2) 当某个成员Ui需要退出时, 只要删除Ui的相关的信息即可。

相反, 如果需要加入某个成员Un+1时, 只需要按照步骤计算Un+1的相关信息即可。

5结束语

提出了一个可验证的动态多秘密共享方案。参与者拥有的子秘密是自己选择的。秘密分发者得到的只是一个用子秘密运算后的秘密影子。别的参与者可以动态地扩展, 而多重秘密可以根据需要动态地更新。因为该方案的过程比较简单。因此有很好的应用前景。

摘要：一个基于奇次线性递归和环ZN上的椭圆曲线可验证的多秘密共享方案被提出。该方案的安全性是基于ECRSA加密体制的安全性和ECDLP的不可求性。并且是一个动态的多秘密共享方案, 不需要安全通道, 成本比较低。此方案在分发阶段和验证阶段比较简单。

关键词：奇次线性递归,椭圆曲线,动态

参考文献

[1]Chor B, Goldwasser S, Micali S, et al.Verifiable secret sharing and achieving simultaneity in the presence of faults.In:Proceedings of

[26]th IEEE Symposium on Foundations of Computer Science, IEEE, Portland, 1985:251—260

[2]Harn L.Efficient sharing (broadcasting) of multiple secret.IEEE Proceedings on Computers and Digital Techniques, 1995;142 (3) :237—240

[3]Yang C C, Chang T Y, Hwang M S.A (t, n) multi-secret sharing scheme.Applied Mathematics and Computation, 2004;151:483—490

[4]Hadian Dehkordi M, Mashhadi S.Verifiable secret sharing schemes based on non-homogeneous linear recursions and elliptic curves.Computer communications, 2008;31:1777—1784

[5]Biggs NL.Discrete Mathematics.Revised ed, NewYork:Oxford Uni-versity Press, 1989

公开可验证 篇7

关键词：可制造性,设计,本体,OWL,SWRL

0前言

目前,设计工程师在设计零部件时,只是考虑设计上的可行性,没有考虑制造的实际情况。大多数设计师在设计时往往是根据以前的经验,认为设计出来的是可制造的。这种根据经验的设计方法已经不能满足快速产品开发的需求。目前大多数的研究主要集中在用本体方法去表示设计和制造知识,主要在语义层面上进行操作。没有考虑如何合理构建设计知识和制造知识,保证推导出的制造工艺知识在实际工程上是可行的。

Chungoora等人最先提出了一个产品设计和制造的语义互操作的框架[1],文献[2]通过一个基础核心本体实现设计和制造知识的验证,保证知识的无缝共享,基于核心本体分别构建了设计本体和制造本体。在设计领域的可制造性推理方面,文献[3]开发了一个基于本体的产品配置系统,用OWL语言(Web Ontology Language)来表达配置模型,进而使用SWRL语言(Semantic Web Rule Language)表达配置约束,最终使用JESS完成配置过程;文献[4]在protege中添加插件SWRLTab,用来编写规则进行推理;文献[5]研究了一种基于特征的本体的产品模型的可制造性的验证方法,通过添加规则实现可制造性的验证;文献[6]提出一个设计特征模型到制造特征模型的转换的新方法,通过动态链接列表实现转换过程。

1 总体框架

图1解释了基于本体的面向制造工艺性验证的零件设计框架,主要由基础层、领域层和实例层组成。基础层由核心产品模型和ISO 10303AP224标准构成,在此基础上建立领域层中的设计本体和制造本体,并建立它们的映射关系,建立用于验证可制造性的SWRL规则库。实例层中根据已有的规则库,对具体的设计案例的制造性约束进行推理,验证可制造性。利用本体的特点使得设计领域和制造领域的互操作性得到增强,可制造性的经验知识被添加到规则库中,经验知识的不断积累,可以长期指导设计师进行产品设计。

2 基础层

基础层为后面的领域层和实例层提供基础支持,从ISO10303 AP224标准中抽取核心概念,并确定核心概念和核心概念之间的关系。通过OWL语言构建一个核心设计和制造本体,获取核心设计知识和制造知识。通过在共同的基础本体上构建领域本体,可以帮助领域本体开发者减少语义异质问题。图2展示了基础本体中的核心概念的类结构,如特征feature可以分为孔hole、块cuboid、倒角fillet、圆柱cylin⁃der和槽groove。

3 领域层

领域层是通过细化基础层中的概念而来,如图3所示,一个零部件的制造需要经过许多加工工序,常见的加工工序有车、钻、刨、铣、磨,一个抽象的加工工艺能够被更加具体地细分。工序drilling可以被细分为ordinary_drilling、reaming_drilling、expanding_drilling和screwing_drilling。利用本体的类定义每个加工工序,每个加工工序的子类定义工序的子特点。通过OWL语言对知识进行编码,从而使得建立的知识同时被设计工程师和制造工程师理解。映射机制主要是指设计特征和加工工序之间的对象属性,它是连接设计知识中的特征和制造知识的制造工艺的中心纽带,每一个设计特征都对应于一个具体的加工工艺。如图3所示,圆柱体cylinder的子类turned_boss需要经过车床进行车加工,长方体cuboid需要经过刨床进行刨加工,沟槽groove需要经过磨床进行磨削加工,孔hole的二级子类钻孔drilled_hole需要在钻床上进行钻加工。

SWRL语言能够充分定义可制造性规则,推理出所需要的设计知识和制造知识。基于前面定义好的类和属性,就可以用SWRL定义产品设计特征和制造约束之间的关系。将以往设计者的经验和实际制造情况转化为制造规则,利用这些规则可以有效地将设计知识和制造知识紧密地结合起来,长期指导设计师进行产品设计。例如,使用SWRL添加如下防止尺寸过大的规则,它的表达式如下:

4 案例实施

图4展示了一个完工后的轴承座,它从原始的毛坯铸造件到成品需要经过许多工序。4个钻孔和2个扩孔需要在钻床上加工,1个倒角需要在车床上进行车削加工,轴承孔沟槽需要在磨床上进行精加工以达到粗糙度。本文列出四个考虑可制造的规则,在设计阶段,设计师就能提前考虑实际制造中的约束情况。

表1定义了设计轴承座时考虑可制造性的SWRL规则。规则1:设计人员在设计阶段可以考虑钻刀直径的大小。由于制造性的约束,如果只存在直径小于8 mm的刀具,在设计孔直径大小时,如果没有考虑实际的制造情况,定义的孔的直径小于8 mm,就会出现不合理的直径的结果。规则2:考虑设计扩孔扩孔刀具直径的大小。规则3:考虑设计倒圆角时车刀外圆的大小。规则4:考虑设计轴承孔的粗糙度时磨床的精度。

5 结束语

本文结合产品设计过程中不能考虑可制造性的问题,提出一个基于本体的产品设计框架,不仅能够支持设计和制造知识的融合,而且能够支持可制造性的验证,将制造过程中的约束装换为设计中的规则库。本文能验证简单的制造性约束,但复杂的约束情况还需要继续研究。

参考文献

[1]Chungoora N,Young RIM.AFramework to Support Semantic Interoperability in Product Design and Manufacture[C].Proceedings of the 20th CIRP Design Conference,2011:435-443.

[2]Anjum N,Harding J,Young R,et al.Verification of knowledge shared across design and manufacture using a foundation ontology[J].Int J Prod Res,2013,51(22):6534-6552.

[3]Yang D,Dong M,Miao R.Development of a product configuration system with an ontology-based approach[J].Comput Aided Design,2008,40(8):863-878.

[4]Dong M,Yang D,Su L.Ontology-based service product configuration system modeling and development[J].Expert Syst Appl.,2011,38(9):11770-11786.

[5]Anjum N,Harding JA,Young RI,et al.Manufacturability verification through feature-based ontological product models[C].Proceedings of the Institution of Mechanical Engineers,Part B:Journal of Engineering Manufacture,2012,226(6):1086-1098.

公开可验证 篇8

关键词：可验证秘密共享,隐私保护,分布式不经意传输

0 引 言

不经意传输协议 (OT) 首先由Rabin[1]于1981年提出, 此后, OT协议又出现了多种形式, 1985年, Even等人提出了2取1的不经意传输协议;Brassard, Crépeau和Robert于1986年给出了N取1的不经意传输协议的概念;2001年Naor等人给出了N取M的不经意传输协议的具体描述, 并且它也是所有不经意传输协议中最为一般的形式。目前, OT协议已成为密码学的一个基础本原知识和基本模块, 在信息挖掘、数据库访问、电子合同、安全多方计算等许多密码协议中都有着举足轻重的作用。

然而, 随着网络技术的飞速发展, 各种信息系统得到广泛应用的同时, 也变得日益复杂起来, 在庞大的待处理的信息面前, 集中式计算渐露疲态, 分布式计算应运而生。因此, 不经意传输协议也逐步拓展到分布式环境中, 解决了OT协议中计算复杂度高、效率低、带宽消耗高等问题。文献[2]提出了分布式不经意传输协议, 即S持有n条消息, R期望得到其中的某一条, 但S和R并不直接交互, 而是由m个代理服务器实现与R的不经意传输, 且S在初始化协议之后, 就下线不再与R进行任何通信, 各个服务器之间也互不通信。Naor和Pinkas的基本思想是把秘密共享应用于不经意传输中, 并给出了基于多项式插值的 (k, m) -DOT${}_1^2$方案;文献[3]从信息论的角度定义了正确且保密的 (k, m) -DOT${}_1^n$协议, 并在文献[2]的基础上给出了基于多项式插值的 (k, m) -DOT${}_1^n$方案和基于一般接入结构的 (k, m) -DOT${}_1^n$方案;文献[4,5]提出了对于一般安全参数的信息论定义的分布式不经意传输协议, 并扩展了文献[3]中基于多项式插值的结果;文献[6]提出了基于可验证秘密共享的2取1的可验证分布式不经意传输方案 (VDOT${}_1^2$) 。

目前普遍存在的分布式不经意传输协议方案, 存在着以下两个方面的问题:一方面, 一般情况下, 在一次协议中, 虽然各代理服务器不知道R到底与多少个代理服务器交互过, 但如果不能控制R至多得到k个子秘密, 那么即使协议本身是安全的, 发送方的安全也不能保障。针对上述问题, 在文献[2]中给出了k>m/2情况下的解决方案, 而在文献[4]中则是令k=m回避了此问题。另一方面, 为了便于安全性分析, 通常假定所有的代理服务器都是半可信的, 但如果存在某些恶意的代理服务器, 那么将会导致接收者重构出错误的消息。针对这些恶意的代理服务器, 文献[6]仅给出了VDOT${}_1^2$的解决方案。

本文针对上述两个问题, 在VDOT${}_1^2$的基础上提出了VDOT${}_1^n$方案, 该方案除了具备一般分布式不经意传输协议的特点外, 还具备以下优点: (1) 接收者R可以与所有的服务器进行交互, 避免了一般方案中对门限值k的限制; (2) 接收者R可以验证所有消息的正确性, 避免了恶意的代理服务器通过某些手段造成对其隐私的危害, 如:篡改某个消息的秘密份额并监听该篡改行为是否会被发现等等。

1 预备知识

首先, 我们对一般形式的ElGamal加密方案做了一些扩展, 具体描述如下:

令A、B为加密方案的参与双方。A随机选取两个大素数p, q, 使之满足等式p=2q+1, g是有限域Gq上的生成元, 选取β∈[0, q-1]和u, u0, …, un-1∈Gq, 使之满足u=u0, …, un-1, uσ=1, 并计算Gσ=uσg (n-1) β, Gi=ui/gβ (0≤i≠σ≤n-1) , 发送 (G0, …, Gn-1, u) 给B, 并用零知识证明可以计算出loggG0, …, loggGn-1中的某一个。

B验证A的零知识证明是否有效, u是否在有限域Gq上, 及等式u=G0, …, Gn-1是否成立, 若上述均成立, 则B响应n条加密的消息$\overline{s{}_i}=s{}_{i}G{}_i^k$, 其中k∈[0, q-1]是其私钥, 计算并公布其公钥K=gk;否则, 终止协议。

由于G${}_{\sigma }^k$= (g (n-1) β) k=K (n-1) β, 故当A收到B发送的加密消息后, 可以解密出$s{}_{\sigma }=\overline{s{}_{\sigma }}/{\rm K}{}^{(n-1)\beta }$;又由于A不能计算出loggGb (0≤b≠σ≤n-1) , 故无法解密出sb。

其次, 为了重构正确的消息sσ, R必须能够检测所有的代理服务器是否对秘密份额进行了篡改。本文借助于文献[7]中提到的可公开验证的秘密共享方案, 以解决上述问题。它是一个不需要可信机构参与的非交互式的可验证秘密共享方案, 我们只需采用上述方案的秘密分发阶段和秘密重构阶段即可, 其主要思想为:能够验证秘密份额的一致性, 更确切的说, 假定 (x1, …, xm) 是在秘密分发阶段分发给各个代理服务器的某条消息的秘密份额, 则在秘密重构阶段, 一定存在${\displaystyle \prod _{j\in J}x}{}_j{}^{{\displaystyle {\prod }_{l\in J}^{i\ne j}}\frac{j-l}{i-l}}=x{}_i$, 其中J是一个选定的集合, 且|J|=t, i∉J。

本文方案在上述可公开验证秘密共享方案的基础上做了一些变形。假定代理服务器Sj持有的秘密份额记作kj, 且满足等式Kj=gkj, 则存在等式${\displaystyle \prod _{j\in J}{\rm K}}{}_j{}^{{\displaystyle {\prod }_{l\in J}^{i\ne j}}\frac{j-l}{i-l}}={\rm K}{}_i$。因此, 我们可以得到下面的等价等式:

${\displaystyle \prod _{j\in J}x}{}_j{}^{{\displaystyle {\prod }_{l\in J}^{i\ne j}}\frac{j-l}{i-l}}=x{}_i\iff {\displaystyle \prod _{j\in J}(}x{}_j{\rm K}{}_j^{\beta }){}^{{\displaystyle {\prod }_{l\in J}^{i\ne j}}\frac{j-l}{i-l}}=x{}_i{\rm K}{}_i^{\beta }$

其中 (x1, …, xm) 是某个秘密的各秘密份额, Kj是其对应的公钥。

为了能够检测代理服务器是否存在欺骗行为, 即是否存在秘密份额被篡改过, 接收者只需要验证上述等式右侧的值是否与接收到的消息一致即可。

2 N取1的分布式不经意传输方案

下面我们将给出VDOT${}_1^n$方案的具体实现。规定若1≤j≤t, 则称Sj为主服务器;否则称其为验证服务器。

Step1S借助于可公开验证的秘密共享方案实现对消息s0, …, sn-1及其私钥k在m个代理服务器S1, …, Sm中的共享。

Step2R选取两个大素数p, q, 使之满足等式p=2q+1, g是有限域Gq上的生成元, 选取β∈[0, q-1], u, u0, …, un-1∈Gq, 使之满足u=u0, …, un-1, uσ=1, 并计算得到Gσ=uσg (n-1) β, Gi=ui/gβ (0≤i≠σ≤n-1) , 发送 (G0, …, Gn-1, u) 给每个主服务器Sj, 利用零知识证明其可以计算得到loggG0, …, loggGn-1中的某一个。

Step3 每个主服务器Sj验证以下三点是否成立: (1) R的零知识证明的有效性; (2) u是否为有限域Gq上的元素; (3) 等式u=G0, …, Gn-1是否成立。若上述条件均成立, 则Sj计算$\overline{x{}_{b,j}}=x{}_{b,j}G{}_b^{k{}_j}(0\le b\le n-1)$, 其中xb, j是Sj持有的关于sb的秘密份额, kj是其持有的关于私钥k的秘密份额, 接着Sj将$\overline{x{}_{b,j}}(0\le b\le n-1)$及其公钥Kj=gkj发送至R;否则, 终止协议。

Step4R对于每个j验证$\overline{x{}_{b,j}}\in G{}_q$是否成立, 若不成立, 则终止协议;若成立, 计算sσ的各秘密份额$x{}_{\sigma ,j}=\overline{x{}_{\sigma ,j}}/{\rm K}{}_j^{(n-1)\beta }$, 及消息$s{}_{\sigma }={\displaystyle \prod _{j\in \{1,\cdots ,t\}}x}{}_{\sigma ,j}{}^{{\displaystyle {\prod }_{l\in \{1,\cdots ,t\}}^{l\ne j}\frac{-l}{j-l}}}$。

Step5R接着计算:$\overline{x^{\prime }{}_{b,i}}={\displaystyle \prod _{j\in \{1,\cdots ,t\}}\overline{x{}_{\sigma ,j}}}{}^{{\displaystyle {\prod }_{l\in \{1,\cdots ,t\}}^{l\ne j}\frac{i-l}{j-l}}}(i=t+1,\cdots ,n-1)$, 并发送$(G{}_0,\cdots ,G{}_{n-1},\overline{x^{\prime }{}_{b,i}})$给每个验证服务器Si。

Step6 每个验证服务器Si验证等式$\overline{x^{\prime }{}_{b,i}}=x{}_{b,i}G{}_b^{k{}_i}$, 并发送应答消息给R, 若等式成立, 则回复应答消息为”Yes”;否则, 为”No”。

Step7 对于所有的b (0≤b≤n-1) , 若多数验证服务器的响应为“Yes”, 则接收者接受该应答消息, 输出消息sσ;否则, 拒绝接受应答消息, 协议结束。也就是说, 存在一个概率多项式时间算法V满足:若V (r1, …, rn) =“接受”, 则O (r1, …, rn) =sσ;若V (r1, …, rn) =“拒绝”, 则O (r1, …, rn) ≠sσ。

3 安全性分析

下面将从三个方面对本文方案的安全性进行分析:

(1) 纵使S与所有的代理服务器进行合谋, 也无法获得关于R的选择σ (0≤σ≤n-1) 的任何消息。

假设存在一个攻击者A*, 可以控制S及所有的代理服务器。但不管A*如何欺骗, R所传送的消息序列总是与其选择σ相对应, 也就是说, 对于任意的消息m∈{0, 1}*总可以得到下面的等式:

P[M=m|σ=0]=P[M=m|σ=1]=…

=P[M=m|σ=n-1]=P[M=m]=Pm

若A*的输出为O (M, κ) , 其中κ是A*的知识, 则:

$\begin{array}{l}{\rm P}[{\rm O}=\sigma ]={\rm P}[{\rm O}=0|\sigma =0]{\rm P}[\sigma =0]+\cdots +\\ {\rm P}[{\rm O}=n-1|\sigma =n-1]{\rm P}[\sigma =n-1]\\ ={\displaystyle \sum _m{\rm P}}[{\rm O}=0|\sigma =0\wedge {\rm M}=m]{\rm P}[{\rm M}=m|\sigma =0]/n+\cdots +\\ {\displaystyle \sum _m{\rm P}}[{\rm O}=n-1|\sigma =n-1\wedge {\rm M}=m]\frac{{\rm P}[{\rm M}=m|\sigma =n-1]}{n}\\ ={\displaystyle \sum _m\frac{{\rm P}{}_m}{n}}\times {\rm P}[{\rm O}(m,\kappa )=0|\sigma =0\wedge {\rm M}=m]+\cdots +\\ {\displaystyle \sum _m\frac{{\rm P}{}_m}{n}}\times {\rm P}[{\rm O}(m,\kappa )=n-1|\sigma =n-1\wedge {\rm M}=m]\end{array}$

由于m是一个字符常量, κ也不依赖于σ, 故上式等价于:

$\begin{array}{l}{\rm P}[{\rm O}=\sigma ]={\displaystyle \sum _m\frac{{\rm P}{}_m}{n}}{\rm P}[{\rm O}(m,\kappa )=0|{\rm M}=m]+\cdots +\\ {\displaystyle \sum _m\frac{{\rm P}{}_m}{n}}{\rm P}[{\rm O}(m,\kappa )=n-1|{\rm M}=m]\\ ={\displaystyle \sum _m\frac{{\rm P}{}_m}{n}}=\frac{1}{n}。\end{array}$

也就是说, 纵使S与所有代理服务器合谋, 获取R的选择σ的概率也只为1/n。

(2) 在DDH假设成立条件下, R与t-1个代理服务器合谋, 仅能够获取其选择的消息sσ, 而无法获取其未选择的消息sb (0≤b≠σ≤n-1) 。

由本文方案得知, 代理服务器分为两组:主服务器和验证服务器。在第三步中, 规定主服务器需验证R零知识证明的有效性等, 因此, 要求至少存在一个主服务器是诚实的。假设R可以计算出loggGσ′, 并试图通过与代理服务器的合谋重构出一条其未选择的消息sb (0≤b≠σ′≤n-1) 。而为了得到此消息, 他必须从Sj中获得关于此消息的全部秘密份额xb, j, 但其获得此值的概率不大于1/n+ε。这是因为, 攻击者从诚实的参与者获得的消息包括:经ElGamal加密的秘密份额$\overline{x{}_{b,j}}$, 以及关于等式$\overline{x^{\prime }{}_{b,i}}=x{}_{b,i}G{}_b^{k{}_i}$是否成立的应答消息, 对于前者, ElGamal加密方案在DDH假设下是语义安全的, 对于后者攻击者可以通过验证等式$\overline{x^{\prime }{}_{b,i}}=\overline{x{}_{\sigma ,j}}{}^{{\displaystyle {\prod }_{l\in \{1,\cdots ,t\}}^{l\ne j}\frac{i-l}{j-l}}}$达到同样的效果, 因此, 攻击者获得xb, j的概率不大于1/n+ε, 即R与t-1个代理服务器合谋, 不能得到其未选择的消息。

(3) 该方案是可验证的, 当且仅当不诚实的代理服务器个数不超过 (n-t) /2。

从方案的第七步得知, 若代理服务器不存在欺骗行为, 则接收者便可以输出正确的sσ。换句话说, 若接收者的输出与其选择的消息sσ不同, 则说明多数验证服务器的应答消息为“No”, 同理, 若接收者的输出与sσ一致, 则多数验证服务器的应答消息为“Yes”。根据题设得知, 全部的代理服务器中至多存在 (n-t) /2个不诚实的代理服务器, 则可以推出至少存在t (n- (n-t) /2= (n+t) /2≥t) 个诚实的服务器。现在假设存在h个诚实的主服务器, 那么可以推断出, 存在t-h个恶意的主服务器和t-h个诚实的验证服务器。对于每一个诚实的验证服务器Si, 一定存在$\overline{x^{\prime }{}_{\sigma ,i}}=x{}_{\sigma ,i}G{}_{\sigma }^{k{}_i}$, 亦即:

$x{}_{\sigma ,i}G{}_{\sigma }^{k{}_i}={\displaystyle \prod _{j\in \{1,\cdots ,t\}}(}\overline{\overline{x{}_{\sigma ,j}}}G{}_{\sigma }^{k{}_j}){}^{{\displaystyle {\prod }_{l\in \{1,...,t\}}^{l\ne j}\frac{i-l}{j-l}}}$

令:$\overline{x{}_{\sigma ,j}}=\overline{\overline{x{}_{\sigma ,j}}}G{}_{\sigma }^{k{}_j}(j\in \{1,\cdots ,t\})$, 若Sj是诚实的, 则必有$x{}_{\sigma ,j}=\overline{\overline{x{}_{\sigma ,j}}}$, 且经过进一步变形可得到:

$\begin{array}{l}x{}_{\sigma ,i}G{}_{\sigma }^{k{}_i}={\displaystyle \prod _{j\in \{1,\cdots ,t\}}(}\overline{\overline{x{}_{\sigma ,j}}}G{}_{\sigma }^{k{}_j}){}^{{\displaystyle {\prod }_{l\in \{1,...,t\}}^{l\ne j}\frac{i-l}{j-l}}}\\ ={\displaystyle \prod _{j\in \{1,\cdots ,t\}}(}\overline{\overline{x{}_{\sigma ,j}}}){}^{{\displaystyle {\prod }_{l\in \{1,\cdots ,t\}}^{l\ne j}\frac{i-l}{j-l}}}\cdot G{}_{\sigma }^{k{}_i}\end{array}$

即$x{}_{\sigma ,i}={\displaystyle \prod _{j\in \{1,\cdots ,t\}}(}\overline{\overline{x{}_{\sigma ,j}}}){}^{{\displaystyle {\prod }_{l\in \{1,\cdots ,t\}}^{l\ne j}\frac{i-l}{j-l}}}$。也就是说, 除恶意的主服务器持有的t-h个秘密份额$\overline{x{}_{\sigma ,j}}$不一致外, 至少存在t-h个一致的秘密份额xσ, i和h个一致的秘密份额$\overline{\overline{x{}_{\sigma ,j}}}$, 其中$x{}_{\sigma ,j}=\overline{\overline{x{}_{\sigma ,j}}}$, 因此, 我们就可以构造出一个t-1 (t-h+h-1=t-1) 次多项式, 且该多项式与秘密共享方案的构造多项式相同, 则R的输出sσ也恰好等于这t个值经拉格朗日插值后在0点的值。

综上, 本文的VDOT${}_1^n$方案是可验证的。

4 结 论

本文提出了VDOT${}_1^n$方案。在该方案中, 接收者R除了可以与所有的服务器进行交互, 避免了其他方案中对门限值k的限制外, 还能够验证所有消息的正确性, 防止潜在恶意的代理服务器通过篡改某个消息的秘密份额而误导其重构出错误的消息。因为该方案借助的可公开验证秘密共享方案一次只能共享一个秘密, 效率低, 故当n的值非常大时, 很可能成为许多应用的瓶颈, 所以, 利用可验证的多秘密共享方案构造出一种高效的VDOT${}_1^n$方案仍是一个有待解决的问题, 也是我下一步研究的主要内容。

参考文献

[1]Rabin MO.Howto exchange secrets by oblivious transfer[R].Techni-cal Report TR-81, Aiken Computation Laboratory, HarvardUniversity, 1981.

[2] Noar M, Pinkas B.Distributed Oblivious Transfer[C]//Advances in Cryptology-Proceeding of AISACRYPT’00, 2000, LNCS, 1976:205-219.

[3]Blundo C, Arco P D’, Santis ADe, et al.NewResults on Unconditional-ly Secure Distributed Oblivious Transfer[C]//Proceedings of SelectedAreas in Cryptography-SAC’02, LNCS, 2002, 2595:291-309.

[4]Nikov V, Nikova S, Preneel B, et al.On Unconditionally Secure Distrib-uted Oblivious Transfer[C]//INDOCRYPT, 2002, LNCS, 2551:395-408.

[5]Blundo C, Arco P D’, Santis A, et al.On Unconditionally Secure Distrib-uted Oblivious Transfer[J].Journal of Cryptology, Springer, 2007, 20 (3) :323-373.

[6] Zhong S, Yang Y R.Verifiable distributed oblivious transfer and mobile agent security[J].Mobile Networks and Applications, 2006, 11 (2) :201-210.