蔣鐵金 任艷麗

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

關(guān)鍵詞：

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

中圖分類號(hào)： TP309.2 文獻(xiàn)標(biāo)志碼：A

0引言

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

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

1本文方案

1.1雙線性對(duì)運(yùn)算

設(shè)G1、G2是階為q的加法循環(huán)群，GT是階為q的乘法循環(huán)群，Z*q表示模q乘法群，其中q是一個(gè)大素?cái)?shù)。如果滿足以下條件，則稱e：G1×G2 → GT是一個(gè)雙線性映射[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）可計(jì)算性。

對(duì)于R∈G1，Q∈G2，存在有效算法能計(jì)算得出e（R，Q）。

如果雙線性映射存在，則成e（R，Q）為一個(gè)雙線性對(duì)。

1.2所提算法

2方案分析

2.1正確性

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

2.2安全性

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

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

首先，證明EVIEWreal～EVIEWideal這兩個(gè)的含義是否應(yīng)該說明一下？請(qǐng)明確?；貜?fù)：這兩個(gè)定義很復(fù)雜，在文獻(xiàn)[13]中有詳細(xì)定義，鑒于篇幅所限可以不說明。。

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

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

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

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

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

其次，證明UVIEWreal～UVIEWideal。

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

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

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

3性能分析

3.1理論分析

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

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

3.2實(shí)驗(yàn)分析

對(duì)上述理論分析進(jìn)行實(shí)驗(yàn)認(rèn)證。用來模擬該算法運(yùn)行的用戶和服務(wù)器的時(shí)間，代碼編寫所使用的機(jī)器語言是Java，使用的方法庫是JPBC，可參考網(wǎng)址：http：//gas.dia.unisa.it/projects/jpbc/javadocs/api/index.html，分別運(yùn)行于普通計(jì)算機(jī)和工作站當(dāng)中。其中：普通計(jì)算機(jī)配置：Pentium DualCore CPU E5300 @ 2.60GHz 2.60GHz RAM 2.00GB；工作站計(jì)算機(jī)配置：Intel Xeon CPU E51620 v2 3.70GHz 3.70GHz RAM 16.0GB。實(shí)驗(yàn)當(dāng)中，q設(shè)為160bit素?cái)?shù)。

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

表格（有表名）

表2各外包方案用戶計(jì)算時(shí)間ms

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

1002621610171219265

20052310201150444511

30078128300226692766

4001043444062968841077

50013121049836510931261

60015469160643413111539

70018246970450415351813

80022013780658517512047

90023383490564519992285

1000263873100574121982576

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

4結(jié)語

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

參考文獻(xiàn)：

[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.（無期號(hào)）

[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].西安電子科技大學(xué)學(xué)報(bào)，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.