基于单个服务器的双线性对运算外包算法

蒋铁金 任艳丽

摘要：双线性对运算是公钥密码算法的基本运算之一，在基于身份加密、基于属性加密等密码体制中有重要应用。现有可行的双线性对外包算法均基于两个不可信服务器，这在实际应用中不易实现。针对此问题，提出一种基于单个服务器的双线性对运算外包算法。通过少量的预计算，即可对用户的输入进行盲化处理，实现输入及输出的保密性，并能有效地验证外包结果的正确性。实验结果表明，所提算法只需进行常数次点加和模乘运算，极大地降低用户的计算代价，并且可验证性概率可达到2/5。与现有的双线性外包算法相比，所提算法仅需要调用一个不可信服务器，在实际应用中更易实现。

关键词：

双线性对；外包算法；单个不可信服务器；公钥密码算法；计算代价

中图分类号： TP309.2 文献标志码：A

0引言

随着云计算技术[1]的发展，外包计算也逐渐引起人们的重视[2]。将耗时的计算任务外包给服务器，不仅可以节约用户的计算成本，而且可以提高用户的计算效率[3]。然而，将计算任务外包给服务器也存在很多安全隐患，如服务器可能泄漏用户数据，或者返回错误的计算结果[4-6]。为了解决这些问题，Gennaro等[7]提出了一种可验证计算方案，输入输出信息对服务器是保密的。

双线性计算被认为是最常见、最昂贵的计算之一。ChevallierMames等[8]首次提出了椭圆曲线配对的外包算法，将双线性对计算外包给不可信服务器；，但需要用户进行等同复杂的点乘和模幂运算。在此基础上，Chen等[9]对ChevallierMames等[8]的算法作出改进，通过增加预计算，消除了用户的点乘和模幂运算；但是服务器输出结果的可验证性概率减少为1/2。随后，Tian等[10]提出了两个双线性对外包算法A、B，通过改变预计算的复杂度，既减少了用户的计算量，又提高了外包效率，其中算法A的预计算复杂度明显高于算法B。然而，在真实的云计算环境中，同时找到两个服务器进行外包计算，而且至少一个服务器是真实的诚实的，这样的假设很难实现，因此，基于单个服务器的外包算法更具有实用性，并且不需考虑服务器的诚实性[11]。所以，本文提出了一种新的算法TPair，既能降低用户计算量、保护用户敏感信息，又能验证服务器的输出结果。与现有的双线性对外包算法相比，本文的算法是基于单个服务器的双线性对外包算法，所以提高了外包计算的安全性，实用性更强。

1本文方案

1.1双线性对运算

设G1、G2是阶为q的加法循环群，GT是阶为q的乘法循环群，Z*q表示模q乘法群，其中q是一个大素数。如果满足以下条件，则称e：G1×G2 → GT是一个双线性映射[12]。

1）双线性性。

R∈G1，Q∈G2，a，b∈Z*q，

e（aR，bQ）=e（R，Q）ab

2）非退化性。

R∈G1，Q∈G2，e（R，Q）≠1

3）可计算性。

对于R∈G1，Q∈G2，存在有效算法能计算得出e（R，Q）。

如果双线性映射存在，则成e（R，Q）为一个双线性对。

1.2所提算法

2方案分析

2.1正确性

如果服务器是诚实的，所提的算法是正确的。

2.2安全性

本节证明方案的安全性，相关的安全性概念证明可参考文献[13]。

引理1算法（T，U）是双线性外包算法TPair基于单个不可信服务器的安全外包实现。其中输入（A，B）是秘密可信、可信受保护或者敌对受保护的输入。

首先，证明EVIEWreal～EVIEWideal这两个的含义是否应该说明一下？请明确。回复：这两个定义很复杂，在文献[13]中有详细定义，鉴于篇幅所限可以不说明。。

下面，分3种不同输入情况进行讨论，分别是秘密可信的输入、可信受保护的输入以及敌对受保护的输入。

如果输入参数（A，B）是可信或者敌对受保护的输入，而不是可信秘密的输入，则外界E总能知道输入信息（A，B）。在这种情况下，模拟器S1将与实际实验环境情况一样，总能知道输入信息（A，B）。

如果输入（A，B）为可信秘密的输入，则执行过程如下：S1忽略第i个输入，随机选取5组随机数，并提交给不可信服务器U′。当U′返回服务结果后，S1随机检测U′的两个输出。如检测出一个错误，则S1保存当前所有状态，输出Yip=“error”，Yiu=φ此处的φ，是否是空集？请明确。回复：表示的是一个输出符号，并不是空集。，repi=1。如果没有错误被检测出来，则S1继续检查另外三个输出。当输出都通过检测，S1输出Yip=φ，Yiu=φ，repi=0。否则，S1任选一随机数r，输出Yip=r，Yiu=φ，repi=0。注意，上述的所有情况中，S1都要保存其所有状态信息。

在实际和理想的实验环境中，服务器U′的输入参数是没有区别的。在理想的实验环境中，所有的输入参数都是随机选取的。而在实际实验环境中，查询操作过程是独立随机的。

如果在第i轮，服务器U′是可信的，则EVIEWireal ～EVIEWiideal ，因为在实际实验环境中TU正确执行TPair算法输出的结果等同于理想实验环境中S1执行该算法输出的结果。如果在第i轮，服务器U′是不可信的，返回了错误的计算结果，而可以被T、S1检测出来的概率为2/5；反之，如果没有检测出来，则用户T被成功欺骗，输出该错误结果。在实际环境当中TPair输入的结果相对于E也是随机的。在理想实验环境当中，S1用一个随机值r∈GT代替其计算结果，因此，在服务器U′是不可信的情况下，仍然有EVIEWireal ～EVIEWiideal 成立。通过上面的证明，可以得出EVIEWreal～EVIEWideal。

其次，证明UVIEWreal～UVIEWideal。

模拟器S2的执行过程如下：S2忽略第i个输入，随机选取五组随机数，并提交给服务器U′。然后，S2保存自己和U′的所有状态。也许E能够轻易地分辨出理想实验和实际实验（因为理想实验环境下的输出结果总是不出错的），但是E却不能够将这个信息传递给U′。因为在第i轮，实际实验环境下，T总是再次随机化传递给U的输入参数：理想实验环境下，S2总是将独立随机的查询结果传递给服务器U′，从而可以得出UVIEWireal ～UVIEWiideal 。通过以上证明，可以得出UVIEWreal～UVIEWideal。

引理2算法（T，U）是双线性外包算法TPair基于单个不可信服务器的（O（1/n），2/5）安全外包实现，其中n为阶数q的比特长度。

证明算法TPair计算e（A，B）调用了3次Rand子程序、（t2+t+5）次G1（或者G2）群内点加、2次GT群内乘法。使用查表法可以省略调用Rand的计算量，选取较小t值可当成点加计算。另一方面，计算e（A，B）在有限域内大约需要O（n）次的乘法运算。综上所述，算法（T，U）是外包算法TPair的效率为O（1/n）的安全外包实现。另一方面，如果在任何一次执行TPair算法时出现错误，能被T检测出的概率为2/5。

3性能分析

3.1理论分析

在不同方案中，为求解e（A，B）将其计算任务外包给服务器，用户T需要进行的模幂、模逆、模乘、点乘、点加次数、服务器个数、验证概率如表1所示。

表1中，本文算法TPair与ChevallierMames等[8]的算法相比，虽然二者都是基于单个服务器的双线性对外包算法，但是，本文算法在实现了用户输入输出参数的保密性的同时，减少了用户计算量，完全将模幂与点乘运算外包给了不可信服务器，所作的模逆运算、模乘运算次数都要少，效率上有明显的提高。而与Chen等[9]和Tian等[10]算法相比，本文算法在效率和验证概率上有所不足，但是本文算法只使用了一个不可信的服务器。两个服务器存在两个服务器均返回错误计算结果的可能，其可验证率的计算需要两个服务器中某个服务器的计算结果正确，而基于单个服务器则不需要。所以，本文算法安全性更高、更实用。

3.2实验分析

对上述理论分析进行实验认证。用来模拟该算法运行的用户和服务器的时间，代码编写所使用的机器语言是Java，使用的方法库是JPBC，可参考网址：http：//gas.dia.unisa.it/projects/jpbc/javadocs/api/index.html，分别运行于普通计算机和工作站当中。其中：普通计算机配置：Pentium DualCore CPU E5300 @ 2.60GHz 2.60GHz RAM 2.00GB；工作站计算机配置：Intel Xeon CPU E51620 v2 3.70GHz 3.70GHz RAM 16.0GB。实验当中，q设为160bit素数。

比较用户用不同算法所花费的时间如表2所示。在重复次数相同的情况下，与ChevallierMames等[8]相比，本文所提出的算法TPair需要用户计算的时间大大减少。而与Chen等[9]和Tian等[10]相比，本文所提出的算法需要用户计算的时间较高；但是不同于Chen等[9]和Tian等[10]中基于两个服务器，本文的算法只基于单个服务器，在效率相差不大的前提下，安全性能更高，更具有实用性。

表格（有表名）

表2各外包方案用户计算时间ms

轮数文献[8]方案文献[9]方案文献[10]A方案文献[10]B方案本文方案

1002621610171219265

20052310201150444511

30078128300226692766

4001043444062968841077

50013121049836510931261

60015469160643413111539

70018246970450415351813

80022013780658517512047

90023383490564519992285

1000263873100574121982576

本文所提出的方案TPair的时间曲线如图1所示。由图1可知，通过采用本文方案TPair，用户把双线性对的计算负担外包给服务器，因此计算时间远小于直接计算的时间，随着计算轮数的增加，二者之间差距会越来越大。由此可以得出，本文所提方案TPair是一个安全的双线性对外包算法，并且用户与服务器的计算耗时之和仍小于用户的直接计算耗时，这大大提高了用户的运行效率。

4结语

针对现有可行的双线性对外包算法必须基于两个服务器的缺点，本文提出了一种基于单个不可信服务器的双线性对安全外包算法，该算法大大降低了用户的计算量，并且还可以实现用户输入和输出的保密性。后续工作将在保证用户外包效率不降低的前提下，提高不可信服务器的可验证概率。

参考文献：

[1]

CHAPMAN C， EMMERICH W， MARQUEZ F G， et al. Software architecture definition for ondemand cloud provisioning [J]. Cluster Computing， 2012， 15（2）： 79-100.

[2]

CHEN X， LI J， MA J， et al. New algorithms for secure outsourcing of modular exponentiations [J]. IEEE Transactions on Parallel and Distributed Systems， 2014， 25（9）： 2386-2396.

[3]

SHEN Z， TONG Q. The security of cloud computing system enabled by trusted computing technology [C]// ICSPS 2010： Proceedings of the 2010 2nd International Conference on Signal Processing Systems. Piscataway， NJ： IEEE， 2010： V211-V215.

[4]

REN K， WANG C， WANG Q. Security challenges for the public cloud [J]. IEEE Internet Computing， 2012， 16（1）： 69-73.

[5]

MEZGAR I， RAUSCHECKER U. The challenge of networked enterprises for cloud computing interoperability [J]. Computers in Industry， 2014， 65（4）： 657-674.

[6]

TAKABI H， JOSHI J B D， AHN G J. Security and privacy challenges in cloud computing environments [J]. IEEE Security & Privacy， 2010， 8（6）： 24-31.

[7]

GENNARO R， GENTRY C， PARNO B. Noninteractive verifiable computing： outsourcing computation to untrusted workers [C]// CRYPTO 2010： Proceedings of the 30th Annual Conference on Advances in Cryptology. Berlin： Springer， 2010： 465-482.

[8]

CHEVALLIERMAMES B， CORON J S， MCCULLAGH N， et al. Secure delegation of ellipticcurve pairing [M]// Smart Card Research and Advanced Application. Berlin： Springer， 2010： 24-35.

[9]

CHEN X， SUSILO W， LI J， et al. Efficient algorithms for secure outsourcing of bilinear pairings [J]. Theoretical Computer Science， 2015， 562： 112-121.（无期号）

[10]

TIAN H， ZHANG F， REN K. Secure bilinear pairing outsourcing made more efficient and flexible [C]// Proceedings of the 10th ACM Symposium on Information， Computer and Communications Security. New York： ACM， 2015： 417-426.

[11]

WANG Y， WU Q， WONG D S， et al. Securely outsourcing exponentiations with single untrusted program for cloud storage [C]// ESORICS 2014： Proceedings of the 19th European Symposium on Research in Computer Security. Berlin： Springer， 2014： 326-343.

[12]

解理，任艳丽.隐藏访问结构的高效基于属性加密方案[J].西安电子科技大学学报，2015，42（3）：97-102.（XIE L， REN Y L. Hidden access structure of efficient encryption scheme based on attribute [J]. Journal of Xidian University， 2015， 42（3）： 97-102.）

[13]

HOHENBERGER S， LYSYANSKAYA A. How to securely outsource cryptographic computations [C]// TCC 2005： Proceedings of the Second Theory of Cryptography Conference on Theory of Cryptography. Berlin： Springer， 2005： 264-282.