Page 346 - 《软件学报》2021年第6期

1920 Journal of Software 软件学报 Vol.32, No.6, June 2021

将本文提出的理性委托计算协议与文献[6,30,31]的方案进行比较,从通信复杂性、计算复杂性和是否抵抗
重放攻击这 3 个方面进行对比,见表 4.
Table 4 Performance comparison of protocol
表 4 协议性能对比
通信复杂性 计算复杂性 是否抵抗重放攻击
文献[30] ≥4 O((2n+8)⋅Exp+1⋅Paring) 否
文献[31] poly(S(n)) O(n⋅polylog(T(n))+poly(S(n))) 否
文献[6] ≥2 O(2poly(k,n,logT)) 否
本文协议 2 O(1) 是
文献[30]提出了完全委托的可验证外包计算(verifiable outsourced computation with full delegation,简称
FD-VC)方案,通信复杂性大于等于 4,计算复杂性为 O((2n+8)⋅Exp+1⋅Paring),它不能抵抗重放攻击.该方案将预
处理阶段和函数计算委托给云服务器,并支持计算函数的动态更新,方案的正确性和安全性基于双线性对和双
线 Diffie-Hellman 指数问题的困难性假设.由于双线性对在计算上开销比较大,因此该方案效率比较低.
文献[31]提出了一个用于非确定性计算的非交互私自验证委托计算方案,通信复杂性为 poly(S(n)),计算复
杂性为 O(n⋅polylog(T(n))+poly(S(n))),其中,n 表示输入长度,T(n)和 S(n)分别表示非确定性时间和空间.该方案基
于亚指数 LWE(learning with errors)假设,在此方案之前的工作都是基于随机预言模型(the random oracle model,
简称 ROM)或知识假设,但该方案性能较低且不能抵抗重放攻击.
[4]
文献[6]基于全同态加密技术,提出了对 Gennaro 等学者 工作的改进协议,文献中的第 1 个协议消除了
Gennaro 等学者方案中的大公钥,委托方计算复杂性仍然是 poly(T,k),但密钥长度为 poly(n,k,logT);第 2 个协议将
委托方在离线阶段的计算复杂性减少到 poly(n,k,logT).该协议不能抵抗重放攻击.
本文采用 NTRU 公钥加密体制和 Pedersen 承诺方案,设计基于理性信任模型的理性委托计算协议.其通信
复杂性为 2,计算复杂性为 O(1),该协议可抵抗重放攻击.协议引入了可信第三方 TTP,用来帮助委托方 P 发布任
务和选择计算方 C,以及帮助诚实的参与者惩罚背叛的另一方.与文献[6,30,31]相比,在本文中,委托方 P 不需要
花费大量时间去验证计算方 C 返回的证明计算结果正确性的证据,而是通过验证计算方 C 返回的对计算结果
的承诺:若 com = g FD g 1 r modq ,则委托方 P 接受该计算结果并支付和奖励计算方 C;若 com ≠ g FD g 1 r modq ,则委
()
()
托方 P 拒绝接受该计算结果.
5 结束语
本文基于理性信任模型研究了理性委托计算问题,并在理性信任模型下,详细分析了理性参与者在博弈论
环境中的策略及效用问题,提出了基于理性信任模型的理性委托计算协议.该协议结合改进的 NTRU 公钥密码
体制与 Pedersen 承诺机制,将计算任务委托给理性的计算方.为了更好地激励理性计算方“诚实”地完成计算任
务并返回正确的计算结果,本文引入了计算方的生存周期作为奖励或惩罚计算方的参数,防止了参与者重入攻
击的问题.本文采用 NTRU 公钥加密体制做加密运算,NTRU 加密算法虽然运算速度快、具有抵抗量子攻击的
能力,但其参数多的问题将会给协议的执行增加一定的工作量.因此,选取比 NTRU 公钥密码体制更加有效的加
密算法将是下一步工作的方向.

References:
[1] Hamlin A, Schear N, Shen E, Varia M, Yakoubov S, Yerukhimovich A. Cryptography for big data security. In: Proc. of the Big
Data: Storage, Sharing, and Security (3S). Boca Raton: CRC Press, 2016. 241−288.
[2] Xue R, Wu Y, Liu MH, Zhang LF, Zhang R. Progress in verifiable computation. Scientia Sinica (Informationis), 2015,45(11):
1370−1388 (in Chinese with English abstract).
[3] Kilian J. Improved efficient arguments. In: Proc. of the CRYPTO. Berlin: Springer-Verlag, 1995. 311−324.