1. 东北大学 计算机科学与工程学院，辽宁 沈阳 110819；
2. 东北大学 软件学院，辽宁 沈阳 110819
收稿日期: 2015-03-11
基金项目: 国家自然科学基金资助项目(61300196); 中央高校基本科研业务费专项资金(N130317003); 国家科学技术重大专项资助项目(2013ZX03002006); 辽宁省科技计划项目(2013217004); 沈阳自然科学基金资助项目(F14-231-1-08).
作者简介: 李福祥(1984-),男,辽宁沈阳人,东北大学博士研究生; 周福才(1964-),男,吉林长春人,东北大学教授,博士生导师.
摘要: 已有可验证计算方案存在以下不足:一是只有计算委托方才可以对计算结果进行验证;二是即使计算委托方可以授权其他用户进行验证，但也需要将自身验证密钥交给授权用户.针对上述不足，提出一个支持公共验证的外包计算模型，给出其算法形式化定义及安全模型，并利用双线性映射提出了一个包含三方实体的公共可验证外包计算方案，给出了方案算法的具体描述、实体间的通信协议以及效率分析，方案验证无需私钥参与，实现了公共可验证性.在可证安全模型下证明该方案具有不可伪造性，其安全性可归约于l-SBDH问题的困难性.
关键词: 双线性映射公共可验证外包计算不可伪造性可验证计算
Bilinear Map-based Public Verifiable Outsourced Computation Scheme
LI Fu-xiang1, HUO Jian-qiu1, LIN Mu-qing1,ZHOU Fu-cai2
1. School of Computer Science & Engineering, Northeastern University, Shenyang 110819, China;
2.School of Software, Northeastern University, Shenyang 110819, China.
Corresponding author: ZHOU Fu-cai, professor, E-mail: fczhou@mail.neu.edu.cn
Abstract: There are two shortcomings for the existing verifiable computation schemes. One is that only the owner who outsourced the computation can verify the result, and the other is when the owner authorizes other users to verify the result, he has to send his secret key to all the authorized users. In order to overcome the problems, an outsourced computation model was proposed which supports the public verification. The description and security model were formalized and a publicly verifiable outsourced computation scheme, which is based on the bilinear map and contains three entities, was also presented. The algorithm implementation and the communication protocol were also described in details. The verification phase in the scheme does not need the owner’s secret key so it can be publicly verifiable. The scheme can be proved to satisfy unforgeability in the security model, and the security can be reduced to the hardness of the l-SBDH problem.
Key words: bilinear mappublic verifiableoutsourced computationunforgeabilityverifiable computation 外包计算[1, 2]也称为委托计算，是一种客户-服务器的服务模式，它允许客户将函数计算过程交付给服务器，而客户自身仅产生待计算变量及接收返回的计算结果.这种模式对终端计算能力要求低，使其可以完成对复杂计算问题的处理.因此外包计算不但使计算资源得到更加充分的利用，同时也促进了移动便携设备的发展.但由于计算过程外包于网络服务器，所以如何保证计算被正确地执行，同时满足验证效率要优于计算效率，即实现高效的可验证外包计算成为保障网络信息安全研究领域的热点之一.
Anderson等在SETI@home实现计划[3]中实现了利用全球空闲计算机资源进行计算，开始了对外包计算的研究.Gennaro等[4]介绍了可验证计算的概念，并且给出了包含源客户以及服务器两方实体的可验证计算(verifiable computation，VC)模型.该模型规定验证信息私钥必须由源客户保留，不可分发给其他客户，因此只有该客户可以验证计算结果.以VC模型为基础，Gennar等利用加密的布尔电路[5]和全同态加密技术[6]实现了一个函数外包方案.Parno等在VC中扩展了公共授权[7]和公共可验证性[8]两个重要性质，弥补了VC模型[9]无法进行验证授权的不足.他们通过建立VC和属性基加密的关联，给出了具有公共授权的VC模型，即公共可验证计算(public verifiable computation，PVC)模型[10].该模型中有初始客户、服务端和授权客户三类实体，与VC不同的是，PVC授权用户可以是多个，满足公共可验证性.靳方元等[11]提出了一个基于全同态加密的委托计算方案，从猜测私钥信息、伪造输入输出和得到对应明文3方面证明了方案的安全性.此外，还有学者针对集合的交、并、差集等运算的可验证性进行了研究[12, 13]，但其研究仍没有考虑到公共可验证性.其他研究还包括针对密文数据的交集运算[14]以及针对私有大数据集合的交集运算等[15].现有模型大多存在实现公共授权时，需要将验证密钥交给授权用户的不足，因此并不完全符合公共可验证性的要求.
在文献[9, 10]提出的VC模型基础上，针对公共可验证性要求，本文提出了一个公共可验证计算外包模型(public verifiable outsourced computation model，PVOCM)，并对其正确性和安全性给出了形式化定义.设计了满足公共验证性的三方外包计算通信协议，以双线性映射理论为基础，针对多项式求值外包，给出了一个新型公共可验证外包计算方案，该方案能被证明具有在选择消息攻击下的不可伪造性，其安全性可归约为l-strong bilinear Diffie-Hellman(l-SBDH)问题假设.通过对其计算效率分析，方案满足客户查询和验证开销小于函数计算开销的外包计算效率要求.
1 相关知识1.1 双线性映射设G和GT为p阶循环群，g为G生成元，则有e:G×G→GT，且e满足条件e(ga,gb)=e(g,g)ab以及e(g,g)≠1，即e满足双线性、非退化性和可计算性，则称e为双线性映射.
1.2 计算l-SBDH问题及困难性假设定义1计算l-SBDH问题.设λ为安全参数，G和GT为p阶循环群，g为G生成元，e:G×G→GT为双线性映射，给定g,gt,…,gtl∈G，其中t∈ZP*，随机选取c∈ZP*，计算e(g,g)
.定义2如果找不到概率多项式时间算法在poly(λ)时间内解决l-SBDH问题，即找不到满足l-SBDH问题的二元组，使得(c,e(g,g)
)∈ZP*{-t}×GT，则称l-SBDH问题是困难的.1.3 多项式的表达形式定义3多重集合.集合S是全集U的一个子集，S中的每一个元素都可以出现多次，这样的集合S称为多重集合，元素x的阶就是该元素在多重集合S中出现的次数，表示为S(x).
定义4多项式的表达形式.设Sd,n表示满足n元d次的多项式的所有项的集合，f(x1,x2,…,xn)表示n元d次多项式求值函数，则函数f(x1,x2,…,xn)可以表示为
2 PVOCM2.1 系统模型PVOCM由5个概率多项式时间算法组成，PVOCM={KeyGen,Setup,Compute,Verify,Update}，各算法的具体描述为
1) (pk,sk)←KeyGen(λ,F)密钥生成算法.输入一个秘密参数λ和一个函数簇F，输出公私密钥对(pk,sk).
2) sign(f)←Setup(sk,pk,f)初始化算法.将(pk,sk)及函数簇F中某具体函数f作为输入，输出为函数f的签名值sign(f).
3) (r,p)←Compute(pk,f,a)函数求值算法.将公钥pk和某具体函数f以及计算变量a作为输入，输出结果r=f(a)和证据p.
4) {0,1}←Verify(pk,sign(f),a,r,p)验证算法.将公钥pk，签名值sign(f)，变量a及结果r=f(a)和证据p作为输入，输出结果1或0，其中1代表验证结果正确，0代表验证结果错误.
5) sign(f′)←Update(sk,pk,sign(f),f′)更新算法.将公私密钥对(pk,sk),sign(f)和新选函数f′作为输入，输出的是f′的签名值sign(f′).
2.2 安全模型2.2.1 正确性设λ是初始化选定的安全参数，F是函数簇，定义算法check为多项式时间算法，其以函数输入x，计算结果r和函数f为输入，当结果确实为f计算结果时，返回accept，否则返回reject，即
{accept,reject}←check(x,r,fi)
对于任何i=0,…,poly(λ)，变量x∈domain(fi)，PVOCM是正确的，则要求各算法正确执行后，算法Compute结果满足：
其中neg(λ)为可忽略函数.
2.2.2 安全性设λ为安全参数，通过敌手Adv和挑战者Chal的挑战实验给出安全性定义.
挑战实验：
定义敌手Adv，对于选定变量b=(b1,b2,…,bn)，它试图通过以下步骤来伪造一个结果通过验证：
1) 挑战者Chal执行算法KeyGen，输出公私密钥对(pk,sk)，将公钥pk给Adv，私钥sk保留.执行算法Setup，生成初始函数签名值sign(f0).
2) Adv向Chal进行查询，Chal向Adv返回sign(f0).之后Adv可以向Chal进行poly(λ)次的查询，每一次查询Chal进行一次Update算法，并将更新的函数签名值sign(fi)发送至Adv.
3) Adv对于特定具体函数fi输出一个伪造结果r′及伪造的证据p′=(p′1,p′2,…,p′n).
4) 若Verify(pk,sign(fi),b,r′,p′)输出为1，且有fi(b)≠r’，则Adv伪造成功，否则Adv失败.
定义5PVOCM安全性.令PVOCM={KeyGen,Setup,Compute,Verify,Update}是公共可验证外包计算模型，在上述挑战实验过程中，如果敌手Adv伪造成功的概率满足：
则称PVOCM满足不可伪造性.
3 具体方案针对多项式求值计算，基于双线性映射提出包含源端Sou(函数拥有者)，服务端Ser(计算执行者)以及客户端C(计算发起和验证者)三方实体的公共可验证外包计算方案(bilinear map-based public verifiable outsourced computation scheme,BPVOCS)，并证明该方案满足不可伪造性，其安全性可归约于l-SBDH问题困难性假设.
方案构成：
BPVOCS包括5个多项式时间算法，即BPVOCS={KeyGen,Setup,Compute,Verify,Update}，其具体算法描述为
1) (pk,sk)←KeyGen(λ,F)密钥生成算法.函数簇F是满足n元d次多项式函数的集合.KeyGen首先生成一个λ位的素数p，再生成p阶循环群G和GT，及双线性映射函数e.取G中生成元g和n个随机值t1,t2,…,tn∈Zpn.计算签名生成集Wn,d={g∏i∈StiS(i):∀S∈Sn,d}.其中Wn,d中的元素个数为Cn+dn.
最终公钥pk={g,Wn,d,G,GT,e}，私钥sk包括n个随机值t1,t2,…,tn.
2) sign(f)←Setup(sk,pk,f)函数签名值初始化算法.设f(t)表示n元d次多项式函数，总共有k项，由多重集合S1,S2,…,Sk来表示.对于i=1,2,…,k，有∀Si∈Sn,d.每项系数为c1,c2,…,ck.使用Wn,d和pk中椭圆曲线参数计算多项式签名值：
3) (r,p)←Compute(pk,f,a)函数计算算法.首先计算r=f(a)，再产生证据p.
若结果r是正确计算得到的结果，则可找出n个多项式q1(x),q2(x),…,qn(x)，使得f(x)-r=
.证据p包含n个元素p1,p2,…,pn，其中pi=gqi(t).4) {0,1}←Verify(pk,sign(f),a,r,p)结果验证算法.利用p=(p1,p2,…,pn),pk,函数签名值sign(f),r和变量a以及双线性映射e来验证是否有式(3)成立.
又由式(3)可以转化为验证：
如果式(4)成立，则该算法接受结果r，输出1，反之拒绝结果r并且输出0.
5) sign(f′)←Update(sk,pk,sign(f),f′)函数签名值的更新.f表示当前计算函数，f′表示新计算函数，则
4 安全性证明和性能分析4.1 正确性证明BPVOCS是正确的，表示如果方案步骤都是正确执行，产生的结果都是按照正确步骤执行得到的，没有被恶意篡改的，则客户端将以极大概率接受结果，即客户端执行验证算法1←Verify(pk,sign(f),a,r,p).证明过程略.
4.2 安全性证明BPVOCS满足不可伪造性，即要证明敌手Adv，对于选定变量b=(b1,b2,…,bn)试图伪造出正确结果和证据(r′,p′)是不可行的.
定理1BPVOCS的不可伪造性.敌手Adv伪造结果及证据(b,r′,p′)，如果最终客户端C的验证算法输出为1的概率是极小概率neg(λ)，即Adv伪造成功的概率是极小概率neg(λ)，则满足不可伪造性.
证明 敌手Adv选定b=(b1,b2,…,bn).源端Sou随机选择一个系列变量t=(t1,t2,…,tn)，创建相应的Wn,d，令t1=τ，对于i∈{2,3,…,n}，Sou选择随机的(ri,si)，使得bi=ri·b1+si，计算ti=ri·τ+si.Sou记录所有ri，计算Wn,d.Sou选定初始函数f0，计算出初始sign(f0).
查询阶段.Adv向Sou查询初始函数签名值sign(f0)以及后续sign(fi).
伪造阶段.Adv指定Sou使用过的某函数fi，伪造b对应的错误值r′和证据p′，其中r′≠fi(b)，p′=(p′1,p′2,…,p′n).
最后客户验证阶段，客户C接到Adv发过来的(b,r′,p′)，及Sou端pk和对应sign(fi).
假设敌手Adv伪造成功，则有r′≠fi(b)和Verify(pk,sign(fi),b,r′,p′)=1同时成立.令δ=r′-fi(b)，明显δ≠0.由于客户端C处验证成功，所以有e(g,g)fi(t)-r′=
)成立.则有
.因此有
.又因为有
，所以有
这样在客户端C处可以得到
至此，在客户端C处已知的g,gτ,gτ2,…,gτl情况下，在多项式时间里得到了e(g,g)
，而这与l-SBDH假设相矛盾，因此假设中敌手成功伪造错误结果通过验证不成立，证明了本文BPVOCS满足不可伪造性.4.3 效率分析源端Sou在KeyGen算法计算签名生成集Wn,d时，Wn,d中的元素个数是Cn+dn，而生成每个元素的复杂度为O(d)，故生成Wn,d复杂度为O(d·Cn+dn)，即O(Cn+dn).私钥生成的复杂度为O(n)，产生双线性配对参数的复杂度都是低于O(n)，故KeyGen算法的计算复杂度为O(Cn+dn).对于Setup算法，函数签名值sign(f)要计算Cn+dn项，故其复杂度也是O(Cn+dn).对于Update算法，由于满足n元d次多项式的函数之间的区别最多是Cn+dn个系数，所以Update算法的计算复杂度为O(Cn+dn).由于Sou端KeyGen算法和Setup算法只执行一次，之后执行Update算法，所以Sou运行的时候计算复杂度为O(Cn+dn).
在服务端Ser执行Compute算法.首先计算函数值r=f(b)，由于函数的最高次幂是d，所以计算函数值的复杂度为O(nd).之后Ser进行证据p=(p1,p2,…,pn)的生成，证据pi=gqi(t)，故生成每个证据的计算复杂度和生成函数签名值的复杂度一样，都是O(Cn+dn)，所以生成证据p的计算复杂度为O(Cn+dn).因此，Ser运行时计算复杂度为O(nd).
客户端C执行Verify算法.
的复杂度为O(n)，计算e(sign(f)g-r,g)的复杂度为O(1)，之后将两个结果进行比较，复杂度也为O(1).因此C的计算复杂度为O(n).由此可见客户端C的工作量是远低于其他两个实体所需的工作量的，这就满足本文减轻客户端C的负担，使得计算能力较弱的设备也可以进行复杂计算任务的设计初衷.
5 结论1) 提出公共可验证外包计算模型PVOCM，介绍了三方通信协议以及模型的正确性和安全性定义.
2) 针对多项式求值计算，提出基于双线性映射的公共可验证外包计算方案BPVOCS，给出方案具体实现算法，并证明其满足正确性和不可伪造性，其安全性可归约于l-SBDH问题的困难性.
3) 同其他同类方案相比，验证过程中不需私钥的参与，满足公共可验证性，且客户验证代价明显低于服务端计算代价，符合计算外包的本质要求.
参考文献
| [1] | Green M, Hohenberger S, Waters B.Outsourcing the decryption of ABE ciphertexts[C]//Procceding of the 20th USENIX Cnference on Security.San Francisco, 2011:34-34.( 1) |
| [2] | Chung K M, Kalai Y, Vadhan S.Improved delegation of computation using fully homomorphic encryption[M].Berlin:Springer, 2010:483-501.(1) |
| [3] | Anderson D P, Cobb J, Korpela E, et al.SETI@Home:an experiment in public-resource computing[J].Communications of the ACM, 2002, 45(11):56-61.(1) |
| [4] | Gennaro R, Gentry C, Parno B.Non-interactive verifiable computing:outsourcing computation to untrusted workers[M].Berlin:Springer, 2010:465-482.(1) |
| [5] | Yao A.Protocols for secure computations[C]//Procceding of the 23rd Annual Symposium on Foundations of Computer Science.New York, 1982:160-164.(1) |
| [6] | Gentry C.A fully homomorphic encryption scheme[D].Stanford:Stanford University, 2009.(1) |
| [7] | Barbosa M, Farshim P.Delegatable homomorphic encryption with applications to secure outsourcing of computation[M].Berlin:Springer, 2012:296-312.(1) |
| [8] | Goldwasser S, Kalai Y T, Rothblum G N.Delegating computation:interactive proofs for muggles[C]// Procceding of the 40th Annual ACM Symposium on Theory of Computing.Victoria, 2008:113-122.(1) |
| [9] | Bitansky N, Canetti R, Chiesa A, et al.From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again[C]//Procceding of the 3rd Innovations in Theoretical Computer Science Conference.Cambridge, 2012:326-349.(2) |
| [10] | Parno B, Raykova M, Vaikuntanathan V.How to delegate and verify in public:verifiable computation from attribute-based encryption[M].Berlin:Springer, 2012:422-439.(2) |
| [11] | 靳方元, 朱艳琴, 罗喜召.基于可验全同态加密的委托计算方案[J], 计算机工程,2012, 38(23):150-153. (Jin Fang-yuan, Zhu Yan-qin, Luo Xi-zhao.Delegation of computation scheme basedon verifiable fully homomorphic encryption[J].Computer Engineering, 2012, 38(23):150-153.)(1) |
| [12] | Papamanthou C, Tamassia R, Triandopoulos N.Optimal verification of operations on dynamic sets[M]//Advances in Cryptology-CRYPTO 2011.Berlin:Springer, 2011:91-110.(1) |
| [13] | Canetti R, Paneth O, Papadopoulos D N.Triandopoulos, verifiable set operations over outsourced databases[M].Berlin:Springer, 2014:113-130.(1) |
| [14] | Zheng Q, Xu S.Verifiable delegated set intersection operations on outsourced encrypted data[C]//Procceding of the 2015 IEEE International Conference on Cloud Engineering(IC2E).Tempe, 2015:175-184.(1) |
| [15] | Kamara S, Mohassel P, Raykova M, et al.Scaling private set intersection to billion-element sets[M]//Financial Cryptography and Data Security.Berlin:Springer, 2014:195-215.(1) |
本文献在全文中的定位：
... 外包计算[1, 2]也称为委托计算，是一种客户-服务器的服务模式，它允许客户将函数计算过 ...
1
本文献在全文中的定位：
... 外包计算[1, 2]也称为委托计算，是一种客户-服务器的服务模式，它允许客户将函数计算过 ...
1
本文献在全文中的定位：
... Anderson等在SETI@home实现计划[3]中实现了利用全球空闲计算机资源进行计算，开始了对外包计算的研究 ...
1
本文献在全文中的定位：
... 利用全球空闲计算机资源进行计算，开始了对外包计算的研究.Gennaro等[4]介绍了可验证计算的概念，并且给出了包含源客户以及服务器两方实体 ...
1
本文献在全文中的定位：
... 该客户可以验证计算结果.以VC模型为基础，Gennar等利用加密的布尔电路[5]和全同态加密技术[6]实现了 ...
1
本文献在全文中的定位：
... 布尔电路[5]和全同态加密技术[6]实现了一个函数外包方案.Parno等在VC中扩展了公共授权 ...
1
本文献在全文中的定位：
... 现了一个函数外包方案.Parno等在VC中扩展了公共授权[7]和公共可验证性[8]两个重要 ...
1
本文献在全文中的定位：
... 了公共授权[7]和公共可验证性[8]两个重要性质，弥补了VC模型[9] ...
2
本文献在全文中的定位：
... [8]两个重要性质，弥补了VC模型[9]无法进行验证授权的不足.他们通过建立VC和属性基加密的关联，给出了 ...
... 在文献[9, 10]提出的VC模型基础上，针对公共可 ...
2
本文献在全文中的定位：
... 公共授权的VC模型，即公共可验证计算(public verifiable computation，PVC)模型[10].该模型中有初始客户、服务端和授权客户三类实体，与VC不同的是，PVC ...
... 在文献[9, 10]提出的VC模型基础上，针对公共可验证性要求，本文提出了一个公共可 ...
1
本文献在全文中的定位：
... 与VC不同的是，PVC授权用户可以是多个，满足公共可验证性.靳方元等[11]提出了一个基于全同态加密的委托计算方案，从猜测私钥信息、伪造输 ...
1
本文献在全文中的定位：
... 此外，还有学者针对集合的交、并、差集等运算的可验证性进行了研究[12, 13]，但其研究仍没有考虑到公共可 ...
1
本文献在全文中的定位：
... 差集等运算的可验证性进行了研究[12, 13]，但其研究仍没有考虑到公共可验证性.其他研究还包括针对密文数据 ...
1
本文献在全文中的定位：
... 究仍没有考虑到公共可验证性.其他研究还包括针对密文数据的交集运算[14]以及针对私有大数据集合的交集运算等 ...
1
本文献在全文中的定位：
... 以及针对私有大数据集合的交集运算等[15].现有模型大多存在实现公共授权时，需要将验证密钥交给授权用户的 ...
