基于單個服務器的雙線性對運算外包算法

蔣鐵金 任艷麗

摘要：雙線性對運算是公鑰密碼算法的基本運算之一，在基于身份加密、基于屬性加密等密碼體制中有重要應用。現有可行的雙線性對外包算法均基于兩個不可信服務器，這在實際應用中不易實現。針對此問題，提出一種基于單個服務器的雙線性對運算外包算法。通過少量的預計算，即可對用戶的輸入進行盲化處理，實現輸入及輸出的保密性，并能有效地驗證外包結果的正確性。實驗結果表明，所提算法只需進行常數次點加和模乘運算，極大地降低用戶的計算代價，并且可驗證性概率可達到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.