蔣鐵金 任艷麗

摘要：雙線性對運算是公鑰密碼算法的基本運算之一，在基于身份加密、基于屬性加密等密碼體制中有重要應(yīng)用?，F(xiàn)有可行的雙線性對外包算法均基于兩個不可信服務(wù)器，這在實際應(yīng)用中不易實現(xiàn)。針對此問題，提出一種基于單個服務(wù)器的雙線性對運算外包算法。通過少量的預計算，即可對用戶的輸入進行盲化處理，實現(xiàn)輸入及輸出的保密性，并能有效地驗證外包結(jié)果的正確性。實驗結(jié)果表明，所提算法只需進行常數(shù)次點加和模乘運算，極大地降低用戶的計算代價，并且可驗證性概率可達到2/5。與現(xiàn)有的雙線性外包算法相比，所提算法僅需要調(diào)用一個不可信服務(wù)器，在實際應(yīng)用中更易實現(xiàn)。

關(guān)鍵詞：

雙線性對；外包算法；單個不可信服務(wù)器；公鑰密碼算法；計算代價

中圖分類號： TP309.2 文獻標志碼：A

0引言

隨著云計算技術(shù)[1]的發(fā)展，外包計算也逐漸引起人們的重視[2]。將耗時的計算任務(wù)外包給服務(wù)器，不僅可以節(jié)約用戶的計算成本，而且可以提高用戶的計算效率[3]。然而，將計算任務(wù)外包給服務(wù)器也存在很多安全隱患，如服務(wù)器可能泄漏用戶數(shù)據(jù)，或者返回錯誤的計算結(jié)果[4-6]。為了解決這些問題，Gennaro等[7]提出了一種可驗證計算方案，輸入輸出信息對服務(wù)器是保密的。

雙線性計算被認為是最常見、最昂貴的計算之一。ChevallierMames等[8]首次提出了橢圓曲線配對的外包算法，將雙線性對計算外包給不可信服務(wù)器；，但需要用戶進行等同復雜的點乘和模冪運算。在此基礎(chǔ)上，Chen等[9]對ChevallierMames等[8]的算法作出改進，通過增加預計算，消除了用戶的點乘和模冪運算；但是服務(wù)器輸出結(jié)果的可驗證性概率減少為1/2。隨后，Tian等[10]提出了兩個雙線性對外包算法A、B，通過改變預計算的復雜度，既減少了用戶的計算量，又提高了外包效率，其中算法A的預計算復雜度明顯高于算法B。然而，在真實的云計算環(huán)境中，同時找到兩個服務(wù)器進行外包計算，而且至少一個服務(wù)器是真實的誠實的，這樣的假設(shè)很難實現(xiàn)，因此，基于單個服務(wù)器的外包算法更具有實用性，并且不需考慮服務(wù)器的誠實性[11]。所以，本文提出了一種新的算法TPair，既能降低用戶計算量、保護用戶敏感信息，又能驗證服務(wù)器的輸出結(jié)果。與現(xiàn)有的雙線性對外包算法相比，本文的算法是基于單個服務(wù)器的雙線性對外包算法，所以提高了外包計算的安全性，實用性更強。

1本文方案

1.1雙線性對運算

設(shè)G1、G2是階為q的加法循環(huán)群，GT是階為q的乘法循環(huán)群，Z*q表示模q乘法群，其中q是一個大素數(shù)。如果滿足以下條件，則稱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正確性

如果服務(wù)器是誠實的，所提的算法是正確的。

2.2安全性

本節(jié)證明方案的安全性，相關(guān)的安全性概念證明可參考文獻[13]。

引理1算法（T，U）是雙線性外包算法TPair基于單個不可信服務(wù)器的安全外包實現(xiàn)。其中輸入（A，B）是秘密可信、可信受保護或者敵對受保護的輸入。

首先，證明EVIEWreal～EVIEWideal這兩個的含義是否應(yīng)該說明一下？請明確。回復：這兩個定義很復雜，在文獻[13]中有詳細定義，鑒于篇幅所限可以不說明。。

下面，分3種不同輸入情況進行討論，分別是秘密可信的輸入、可信受保護的輸入以及敵對受保護的輸入。

如果輸入?yún)?shù)（A，B）是可信或者敵對受保護的輸入，而不是可信秘密的輸入，則外界E總能知道輸入信息（A，B）。在這種情況下，模擬器S1將與實際實驗環(huán)境情況一樣，總能知道輸入信息（A，B）。

如果輸入（A，B）為可信秘密的輸入，則執(zhí)行過程如下：S1忽略第i個輸入，隨機選取5組隨機數(shù)，并提交給不可信服務(wù)器U′。當U′返回服務(wù)結(jié)果后，S1隨機檢測U′的兩個輸出。如檢測出一個錯誤，則S1保存當前所有狀態(tài)，輸出Yip=“error”，Yiu=φ此處的φ，是否是空集？請明確?；貜停罕硎镜氖且粋€輸出符號，并不是空集。，repi=1。如果沒有錯誤被檢測出來，則S1繼續(xù)檢查另外三個輸出。當輸出都通過檢測，S1輸出Yip=φ，Yiu=φ，repi=0。否則，S1任選一隨機數(shù)r，輸出Yip=r，Yiu=φ，repi=0。注意，上述的所有情況中，S1都要保存其所有狀態(tài)信息。

在實際和理想的實驗環(huán)境中，服務(wù)器U′的輸入?yún)?shù)是沒有區(qū)別的。在理想的實驗環(huán)境中，所有的輸入?yún)?shù)都是隨機選取的。而在實際實驗環(huán)境中，查詢操作過程是獨立隨機的。

如果在第i輪，服務(wù)器U′是可信的，則EVIEWireal ～EVIEWiideal ，因為在實際實驗環(huán)境中TU正確執(zhí)行TPair算法輸出的結(jié)果等同于理想實驗環(huán)境中S1執(zhí)行該算法輸出的結(jié)果。如果在第i輪，服務(wù)器U′是不可信的，返回了錯誤的計算結(jié)果，而可以被T、S1檢測出來的概率為2/5；反之，如果沒有檢測出來，則用戶T被成功欺騙，輸出該錯誤結(jié)果。在實際環(huán)境當中TPair輸入的結(jié)果相對于E也是隨機的。在理想實驗環(huán)境當中，S1用一個隨機值r∈GT代替其計算結(jié)果，因此，在服務(wù)器U′是不可信的情況下，仍然有EVIEWireal ～EVIEWiideal 成立。通過上面的證明，可以得出EVIEWreal～EVIEWideal。

其次，證明UVIEWreal～UVIEWideal。

模擬器S2的執(zhí)行過程如下：S2忽略第i個輸入，隨機選取五組隨機數(shù)，并提交給服務(wù)器U′。然后，S2保存自己和U′的所有狀態(tài)。也許E能夠輕易地分辨出理想實驗和實際實驗（因為理想實驗環(huán)境下的輸出結(jié)果總是不出錯的），但是E卻不能夠?qū)⑦@個信息傳遞給U′。因為在第i輪，實際實驗環(huán)境下，T總是再次隨機化傳遞給U的輸入?yún)?shù)：理想實驗環(huán)境下，S2總是將獨立隨機的查詢結(jié)果傳遞給服務(wù)器U′，從而可以得出UVIEWireal ～UVIEWiideal 。通過以上證明，可以得出UVIEWreal～UVIEWideal。

引理2算法（T，U）是雙線性外包算法TPair基于單個不可信服務(wù)器的（O（1/n），2/5）安全外包實現(xiàn)，其中n為階數(shù)q的比特長度。

證明算法TPair計算e（A，B）調(diào)用了3次Rand子程序、（t2+t+5）次G1（或者G2）群內(nèi)點加、2次GT群內(nèi)乘法。使用查表法可以省略調(diào)用Rand的計算量，選取較小t值可當成點加計算。另一方面，計算e（A，B）在有限域內(nèi)大約需要O（n）次的乘法運算。綜上所述，算法（T，U）是外包算法TPair的效率為O（1/n）的安全外包實現(xiàn)。另一方面，如果在任何一次執(zhí)行TPair算法時出現(xiàn)錯誤，能被T檢測出的概率為2/5。

3性能分析

3.1理論分析

在不同方案中，為求解e（A，B）將其計算任務(wù)外包給服務(wù)器，用戶T需要進行的模冪、模逆、模乘、點乘、點加次數(shù)、服務(wù)器個數(shù)、驗證概率如表1所示。

表1中，本文算法TPair與ChevallierMames等[8]的算法相比，雖然二者都是基于單個服務(wù)器的雙線性對外包算法，但是，本文算法在實現(xiàn)了用戶輸入輸出參數(shù)的保密性的同時，減少了用戶計算量，完全將模冪與點乘運算外包給了不可信服務(wù)器，所作的模逆運算、模乘運算次數(shù)都要少，效率上有明顯的提高。而與Chen等[9]和Tian等[10]算法相比，本文算法在效率和驗證概率上有所不足，但是本文算法只使用了一個不可信的服務(wù)器。兩個服務(wù)器存在兩個服務(wù)器均返回錯誤計算結(jié)果的可能，其可驗證率的計算需要兩個服務(wù)器中某個服務(wù)器的計算結(jié)果正確，而基于單個服務(wù)器則不需要。所以，本文算法安全性更高、更實用。

3.2實驗分析

對上述理論分析進行實驗認證。用來模擬該算法運行的用戶和服務(wù)器的時間，代碼編寫所使用的機器語言是Java，使用的方法庫是JPBC，可參考網(wǎng)址：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設(shè)為160bit素數(shù)。

比較用戶用不同算法所花費的時間如表2所示。在重復次數(shù)相同的情況下，與ChevallierMames等[8]相比，本文所提出的算法TPair需要用戶計算的時間大大減少。而與Chen等[9]和Tian等[10]相比，本文所提出的算法需要用戶計算的時間較高；但是不同于Chen等[9]和Tian等[10]中基于兩個服務(wù)器，本文的算法只基于單個服務(wù)器，在效率相差不大的前提下，安全性能更高，更具有實用性。

表格（有表名）

表2各外包方案用戶計算時間ms

輪數(shù)文獻[8]方案文獻[9]方案文獻[10]A方案文獻[10]B方案本文方案

1002621610171219265

20052310201150444511

30078128300226692766

4001043444062968841077

50013121049836510931261

60015469160643413111539

70018246970450415351813

80022013780658517512047

90023383490564519992285

1000263873100574121982576

本文所提出的方案TPair的時間曲線如圖1所示。由圖1可知，通過采用本文方案TPair，用戶把雙線性對的計算負擔外包給服務(wù)器，因此計算時間遠小于直接計算的時間，隨著計算輪數(shù)的增加，二者之間差距會越來越大。由此可以得出，本文所提方案TPair是一個安全的雙線性對外包算法，并且用戶與服務(wù)器的計算耗時之和仍小于用戶的直接計算耗時，這大大提高了用戶的運行效率。

4結(jié)語

針對現(xiàn)有可行的雙線性對外包算法必須基于兩個服務(wù)器的缺點，本文提出了一種基于單個不可信服務(wù)器的雙線性對安全外包算法，該算法大大降低了用戶的計算量，并且還可以實現(xiàn)用戶輸入和輸出的保密性。后續(xù)工作將在保證用戶外包效率不降低的前提下，提高不可信服務(wù)器的可驗證概率。

參考文獻：

[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]

解理，任艷麗.隱藏訪問結(jié)構(gòu)的高效基于屬性加密方案[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.