基于可傳遞性的公平的外包計算協議

李海穎,張江霄,隋春榮

(邢臺學院 數學與信息技術學院，河北 邢臺 054001)

基于可傳遞性的公平的外包計算協議

李海穎,張江霄,隋春榮

(邢臺學院 數學與信息技術學院，河北 邢臺 054001)

針對現有的外包計算存在外包計算不公平性、用戶和外包者不是匿名的、且用戶無法傳遞外包計算的問題，基于可傳遞條件模型，構建了一個公平的用戶和外包者匿名的可傳遞外包計算協議.利用Groth-Sahai的承諾和對應證明的可自更新性，新協議保證了用戶和外包者的匿名性，且允許用戶在不想進行計算時，可以不通過外包者，直接把該計算傳遞給其他用戶，從而增加了外包計算的實用性.

外包計算；匿名性；GS證明；交互簽名；可傳遞性條件

外包計算允許某個需要做大量計算任務的用戶，把自己的工作交給云中的一個外包者OU，OU然后可以把任務外包給很多其他的用戶W，在W完成所分配的任務后，OU再付給W對應的報酬.也正是外包計算的出現，既可以幫助某些用戶完成計算量很大的任務，也可以充分利用某些閑置的用戶.但是外包計算存在外包者和用戶之間的不公平問題，即：無法保證外包者付費給用戶后，用戶卻沒有按量完成所分配的計算量；無法保證用戶在完成所分配的計算量后，外包者卻不支付所對應的費用；外包者和用戶之間無法保證公平的交換，同時外包者和用戶不具有匿名性.

正是外包計算的眾多優點，很多學者對其進行研究.為了解決外包者和用戶之間的不公平問題，Golle等[1]首先引入環模式，利用環模式的限制，OU能夠以很大的概率確定W已經足量的完成了OU所分配的任務；Carbunar[2]提出了一個基于公平條件付費的外包計算，解決了在用戶完成所分配的計算量后，卻無法收到對應的費用問題，但是他使用了切割選擇算法和秘密分享協議，因此協議的效率很低；Carbunar[3]又提出了一個新的基于公平付費的外包計算協議，利用的基本協議是條件電子現金協議[4]和可傳遞電子現金協議[5]，但是該協議仍然使用了切割選擇算法，因此協議的效率仍然很低.在2012年，Chen等[6]基于公平的條件付費協議，使用驗證加密構建了一個外包計算協議，該協議考慮了懶惰的、部分誠實的用戶，但是該協議的OU和W都不是匿名的，而且當外包者的外包任務很多的情況下，外包者的計算量太大.Guillevic[7]和Ma[8]等分別針對特殊函數、一般函數等的專項計算量問題的外包問題研究.2016年，任艷麗等[9]提出基于單個雙線性對運算的可完全驗證的外包算法，提高了用戶的可驗證概率.李福祥等[10]針對外包計算只有計算委托方才可以對結果驗證的問題，構建了一個基于雙線性映射的公共可驗證外包計算方案；2017年，韓益亮等[11]將屬性簽名與外包雙線性對計算相結合，提出了一個外包計算結果可驗證的輔助驗證屬性簽名方案.陳振華等[12]設計了內積協議，基于此協議構建了一個云外包計算中空間位置關系的保密判斷.張維緯等[13]構建了一個支持安全外包計算的無線體域網數據共享方案.

針對已有的外包模型中，存在外包計算的不公平性、OU和W不是匿名的，以及外包者任務繁重的問題，構建了一個OU、W1和相應的傳遞者Wi都是匿名的公平的外包計算協議，且在某個W1不想做自己的外包任務時，無需讓OU重新分配任務，就可以直接把自己的外包任務傳遞給另一個用戶W2，同時能保證W1、W2和OU的匿名性.

1 背景知識及可傳遞條件模型

1.1 基礎知識

為了能更好地構建基于可傳遞性的公平的外包計算協議，本節給出所使用的密碼學原語.

定義1(雙線性對)雙線性對是一個滿足下面條件的映射，定義ê：G1×G2→G3，其中群G1、G2和G3是階乘法循環群，p為素數；g,h分別是群G1和G2的生成元.

2)(非退化性)ê(g.h)≠1；

3)(可計算性)ê是多項式時間可計算的.

定義2(SXDH問題)[14]設(p,G1,G2,G3,ê,g,h)是一個素數階群，其中p為素數，g,h分別是G1,G2的生成元，ê：G1×G2→G3.SXDH(Symmetric external Diffe-Hellman)問題指在群G1和G2上DDH問題是困難的.

定義3(GS證明) GS證明[14]在標準模型下給出有關雙線性群中等式的非交互式零知識證明，它適合多種雙線性群中群元素關系的等式，具體包括：雙線性乘積等式、多標量乘法等式和二次等式，本文只使用基于SXDH假設下的雙線性乘積等式.

定義4(交互簽名) 交互簽名[15]允許用戶對消息、驗證秘鑰、對應的簽名做承諾，并證明被承諾的簽名是被承諾消息的簽名.交互簽名提供了很多算法，本文只需要算法SigCom，具體算法如下：

在密鑰sk給出一個消息M的承諾CM，算法SigCom允許簽名者可以在密鑰sk下直接生成消息M的簽名σ的承諾Cσ以及對應的證明πσ，該證明證明了Cσ是一個消息承諾CM的一個有效的簽名，同時簽名者又不知道消息承諾CM的原消息M.在此消息M是Diffe-Hellman對(x,y)∈G1×G2，具體是指存在一個a∈Zp，且x=ga,y=ha.

1.2 可傳遞條件模型

可傳遞條件模型首先在文獻[16]中提出，該模型允許用戶從商家購買商品，向商家支付對應面額的電子現金，商家在收到用戶支付的電子現金后，無需存入銀行就可以直接花費該電子現金，直到某個商家不想花費該電子現金，而是存入銀行，同時用戶和商家在花費之前，會附加一個條件，該條件在滿足某個觸發條件時，可以對電子現金的流向進行調整，從而滿足某個已知條件.該模型可以用于在線賭博、預言市場等應用.本文就是利用該模型來解決外包計算的公平性問題，既允許用戶自己完成外包計算，也可以把該外包計算傳遞給其他用戶，當存在下面條件：用戶的計算不完整或者商家沒有給用戶付對應的報酬時，就可以利用此模型中的條件性來達到外包計算的公平性.具體參見圖1.

圖1 可傳遞條件模型Fig.1 Transferable and conditional model

2 匿名的可傳遞外包計算協議

可傳遞條件模型保證用戶正常完成計算并獲得對應的報酬，或者用戶直接把該計算傳遞給其他用戶，其他用戶完成計算后再獲得相應的報酬，當外包者收到計算結果后，會進行簡單判斷就給用戶支付對應的報酬，但是如果在后面固定時間內發現計算結果不正確，就會給條件者發送錯誤信息，這樣就導致用戶無法獲得對應的條件承諾值，用戶也就無法從銀行提取對應的電子現金面額；同樣若用戶計算結果正確，并未獲得相應的計算報酬，用戶也會向條件者發送外包者的錯誤信息，也就導致外包者會得到銀行對應的懲罰.從而實現匿名的公平的可傳遞外包計算協議.匿名的可傳遞外包計算由外包者OU、多個用戶W1、W2、…、Wn、條件者P和銀行B組成.

2.1 基本參數

2.2 所需算法

本文所構造的匿名的可傳遞外包計算協議主要需要以下2個算法.

Verify(OU(params,pkOU,skou,ckB,result)?P(ckP,ekP)：此協議是一個交互協議，OU驗證用戶所提供的結果result是否正確，若正確就給P發送用戶計算正確的消息，以便后期用戶從P得到被承諾的值；若計算結果不正確，則給P發送用戶計算錯誤的消息，以及Wi的計算結果和對應的錯誤證明，綜合判定結果，以便OU贖回自己的電子現金；

Redeem(W(params,pki,ski,biao)P(ckP,ekP))：此協議是一個交互協議，若W收到OU的電子現金，且P收到OU發送的用戶計算正確的消息，P就給W解開被承諾值，以便W能從銀行提取對應的電子現金；若W進行正確計算后，P沒有收到OU發送的用戶計算正確的消息，則向P提供計算的結果和對應的正確證明，綜合判定后，P再給W解開被承諾值，以便W能從銀行提取對應的電子現金.

2.3 生成協議

包括條件生成和簽名生成，具體描述如下.

2.4 計算協議

此協議或者允許用戶完成相應的計算任務，或者允許用戶把該計算任務轉移給其他人，從而能實現計算任務的直接轉移，減輕OU的負擔.具體協議如下：

2.5 付費協議

此協議允許OU驗證用戶提供的計算結果result的正確性，若正確，則OU給P發送用戶計算正確的消息，以便幫助用戶能從銀行提取自己的報酬.若不正確，則OU給P發送用戶計算錯誤的消息，并提供錯誤的計算結果以及對應的證明，在P驗證成功后，再允許OU贖回自己的電子現金.具體協議如下：

3 安全屬性分析

本文所構造的匿名的可傳遞外包計算協議具有正確性、公平性、不可重復花費性、可傳遞性和傳遞憑條的不可鏈接性.下面分別進行簡要的說明.

說明1：本協議具有正確性.如果外包者和用戶都是誠實的，他們將在付費協議中執行交換協議，并最終能保證用戶可以得到相應的報酬，而外包者能得到正確的計算結果.

說明2：本協議具有公平性.首先外包者可以得到完整的計算結果，假設扮作攻擊者的用戶，獲得了相應的憑條，但是外包者沒有得到相應的計算結果.如果攻擊者能實現這個，卻沒有給外包者相應的計算結果，那攻擊者只有從條件者處獲得相應的憑條，即條件者獲得了相應計算結果，那外包者也會從條件者處獲得相應的計算結果，這和前提條件矛盾，因此對于外包者來說是公平的，即外包者可以獲得完整的計算結果.

說明3：本協議具有匿名性[16].本協議中W1,W2和OU具有匿名性.

其次W1具有匿名性，W1在自己完成計算時，會給條件者提供對應的承諾值和錯誤信息，在提供之前，都需要利用GS證明的可自更新性，對承諾值和錯誤信息進行更新，但是由GS證明可自更新性的不可區分性，可知，W1具有匿名性；當W1把計算傳遞給W2后，同時給W2提供對應的承諾值，在提供之前W1仍然利用GS證明的可自更新性，對承諾值進行更新，這樣就保證了W1的匿名性.總之，W1具有匿名性.以此類推，W2也具有匿名性.

說明4：本協議外包者具有不可重復花費性[16].假設外包者把相同的電子現金付給了不同的用戶，有以下2種可能：第一，外包者向不同的用戶提供了相同的憑條，這在后期會被銀行發現；第二，外包者向不同的用戶支付了不同的憑條，那說明外包者可以成功地偽造銀行的簽名，但是交互簽名是無法偽造的，因此這也是不可能的，因此本協議中外包者不可能發生重復花費.

說明5：本協議中傳遞用戶之間的憑條具有不可鏈接性[16].假設本協議是可鏈接的，則攻擊者必須能夠區分原承諾和更新后的承諾，由于GS證明中承諾的更新是不可區分的.因此，本協議中傳遞用戶之間的憑條具有不可鏈接性.

4 效率分析

把本文、Carbunar[2]和Chen[6]等構建的協議分別從外包者單位時間的計算量、外包計算協議的公平性和匿名性3部分進行比較，具體的比較結果見表1.

表1 外包計算協議的計算量和安全屬性比較Tab.1 Efficiency and security properties comparison in outsourcing computations scheme

由表1可以知道新的外包計算協議，由于可傳遞條件模型的特性，可以允許外包者有一定的彈性驗證時間，而且可以利用條件性對報酬的流向進行調整，使得新協議中外包者單位時間的計算量不大，允許外包者可以處理很重的計算任務；也是因為可傳遞條件模型使得新協議具有公平性；由于GS證明的可自更新性保證了外包者和用戶的匿名性.因此，新協議的效率更高，更實用.

5 結束語

本文構建了一個用戶和外包者的身份是匿名的，且用戶在不想完成計算時，可以實現外包計算可傳遞性的公平外包計算協議.基于可傳遞條件模型，保證了外包計算協議的公平性；利用GS證明的可更新性，保證了用戶和外包者身份的匿名性.同時，在保證用戶和外包者匿名性的前提下，減少了外包者單位時間的計算量.因此本協議的效率更高，實用性更強.

[1] GOLLE P,MIRONOV I.Uncheatable distributed computations[C]∥ CT-RSA 2001.Topics in Cryptiology-CT-RSA 2001,LNCS 2020,Berlin,German: Springer,2001:425-440.

[2] CARBUNAR B,TRIPUNITARA M.Conditional payments for computing markets[C]∥ CANS 2008.Cryptology and Network Security,LNCS 5339,Berlin,German: Springer,2008:317-331.

[3] CARBUNAR B,TRIPUNITARA M.Fair payments for outsourced computations[Z].IEEE Communications Society Conference on Sensor,Mesh and Ad Hoc Communications and Networks,Boston,Massachusetts,USA，Piscataway,2010.

[4] SHI L,CARBUNAR B,SION R.Conditional e-Cash[C]∥ FC 2007.Financial Cryptography and Data Security,LNCS 4886,Berlin,German: Springer,2007:15-28.

[5] 張江霄,李舟軍,高延武,等.基于花費鏈最優匿名的等長可傳遞電子現金系統[J].電子學報,43(9),1805-1809,2015.DOI: 10.3969/j.issn.0372-2112.2015.09.019.

ZHANG J X,L I Z J,GAO Y W,et al.Transferable e-cash system of equal length with optimal anonymity based on spending chain[J].Acta Electronica Sinica,43(9),1805-1809,2015.DOI: 10.3969/j.issn.0372-2112.2015.09.019.

[6] CHEN X F,LI J,SUSILO W.Efficient fair conditional payments for outsourcing computations[J].IEEE Transactions on Information Forensics and Security,2012,7(6):1687-1694.DOI:10.1109/TIFS.2012.2210880.

[7] GUILLEVIC A,VEGNAUD D.Algorithms for outsourcing pairing computation[C]∥ CARDIS 2014.Smart Card Research and Advanced Applications,LNCS 8968,Berlin,German: Springer,2015: 193-211.

[8] MA X,LI J,ZHANG F G.Outsourcing computation of modular exponentiations in cloud computing[J].In Cluster Compute,2013,16(4):787-796.DOI:10.1007/s10586-013-0252-0.

[9] 任艷麗,丁寧,王天銀,等.可完全驗證的雙線性對運算外包算法[J].中國科學：信息科學，2016,46:855-869.DOI: 10.1360/N112016-00020.

REN Y L,DING N,WANG T Y,et al.New algorithms for verifiable outsourcing of bilinear pairings[J].Scientia Sinica Informationis,2016,46:855-869.DOI: 10.1360/N112016-00020.

[10] 李福祥,霍建秋,林慕清,等.基于雙線性映射的公共可驗證外包計算方案[J].東北大學學報(自然科學版),2016,37(5)：619-623.DOI:1005-3026(2016)05-0619-05.

LI F X,HUO J Q,LIN M Q,et al.Bilinear map-based public verifiable outsourced computation scheme[J].Journal of Northeastern University (Natural Science),2016,37(5):619-623.DOI:1005-3026(2016)05-0619-05.

[11] 韓益亮,陳飛,楊曉元.可驗證的外包屬性簽名方案[J].密碼學報,2017,4(2):151-164.DOI: 10.13868/j.cnki.jcr.000170.

HAN Y L,CHEN F,YANG X Y.Verifiable outsourcing attribute-based signature scheme[J].Journal of Cryptologic Research,2017,4(2):151-164.DOI: 10.13868/j.cnki.jcr.000170.

[12] 陳振華,李順東,黃瓊,等.云外包計算中空間位置關系的保密判斷[J].計算機學報,2017,40(2):351-363.DOI: 10.11897/SP.J.1016.2017.00351.

CHEN Z H,LI S D,HUANG Q,et al.Privacy-preserving determination of spatial location-relation in cloud computing[J].Chinese Journal of Computers,2017,40(2):351-363.DOI: 10.11897/SP.J.1016.2017.00351.

[13] 張維緯,張育釗,黃焯,等.支持安全外包計算的無線體域網數據共享方案[J].通信學報,2017,38(4):64-75.DOI: 10.11959/j.issn.1000-436x.2017085.

ZHANG W W,ZHANG Y Z,HUANG C,et al.Data sharing scheme supporting secure outsourced computation in wireless body area network[J].Journal on Communications,2017,38(4):64-75.DOI: 10.11959/j.issn.1000-436x.2017085.

[14] GROTH J,SAHAI A.Efficient Non-interactive proof systems for bilinear groups[C]∥ In EUROCRYPT 2008.Advances in Cryptology-EUROCRYPT 2008,LNCS 4968,Berlin,German: Springer,2008:415-432.

[15] FUCHSBAUER G.Commuting signatures and verifiable encryption[C]∥ CRYPTO 2011.Advances in Cryptology-EUROCRYPT 2011,LNCS 6632,Berlin,German: Springer,2011:224-245.

[16] ZHANG J X,GUO H,LI Z J,et al.Transferable conditional e-cash with optimal anonymity in the standard model[J].IET Information Security,2015，9(1): 59-72.DOI:10.1049/iet-ifs.2013.0138.

(責任編輯：孟素蘭)

Fairoutsourcingcomputationsschemebasedontransferability

LIHaiying，ZHANGJiangxiao，SUIChunrong

(Mathematics and Information Technology Institute，Xingtai University，Xingtai 054001，China)

In outsourcing computations,there exist some problems such as the unfairness of outsourcing computations,the user and outsourcer is not anonymous,and the non-transferable of the outsourcing computations.This paper proposed a fair,full anonymous and transferable outsourcing computations scheme based on the transferable and conditional model.Using the Groth-Sahai's self-updating of commitment and corresponding proving,the new scheme guarantees that the user and outsourcers are fully anonymous.When the user didn't want to do the computation,he can transfer the computations to another.At last,these would improve the practicability of the outsourcing computations.

outsourcing computations;anonymity;GS proof;commuting signature;transferability and condition

TP309

A

1000-1565(2017)05-0555-06

10.3969/j.issn.1000-1565.2017.05.016

2017-03-22

河北省社科基金資助項目(HB14TQ005)

李海穎(1976—)，女，河北邢臺人，邢臺學院副教授，主要從事云計算方面研究.E-mail：rmth11@163.com

張江霄(1983—)，男，河北邢臺人，邢臺學院講師，博士.主要從事云計算及大數據方向研究.E-mail：orange_0092008@163.com