基于可傳遞性的公平的外包計(jì)算協(xié)議

李海穎,張江霄,隋春榮

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

基于可傳遞性的公平的外包計(jì)算協(xié)議

李海穎,張江霄,隋春榮

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

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

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

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

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

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

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

1.1 基礎(chǔ)知識

為了能更好地構(gòu)建基于可傳遞性的公平的外包計(jì)算協(xié)議，本節(jié)給出所使用的密碼學(xué)原語.

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

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

3)(可計(jì)算性)ê是多項(xiàng)式時(shí)間可計(jì)算的.

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

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

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

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

1.2 可傳遞條件模型

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

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

2 匿名的可傳遞外包計(jì)算協(xié)議

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

2.1 基本參數(shù)

2.2 所需算法

本文所構(gòu)造的匿名的可傳遞外包計(jì)算協(xié)議主要需要以下2個(gè)算法.

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

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

2.3 生成協(xié)議

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

2.4 計(jì)算協(xié)議

此協(xié)議或者允許用戶完成相應(yīng)的計(jì)算任務(wù)，或者允許用戶把該計(jì)算任務(wù)轉(zhuǎn)移給其他人，從而能實(shí)現(xiàn)計(jì)算任務(wù)的直接轉(zhuǎn)移，減輕OU的負(fù)擔(dān).具體協(xié)議如下：

2.5 付費(fèi)協(xié)議

此協(xié)議允許OU驗(yàn)證用戶提供的計(jì)算結(jié)果result的正確性，若正確，則OU給P發(fā)送用戶計(jì)算正確的消息，以便幫助用戶能從銀行提取自己的報(bào)酬.若不正確，則OU給P發(fā)送用戶計(jì)算錯(cuò)誤的消息，并提供錯(cuò)誤的計(jì)算結(jié)果以及對應(yīng)的證明，在P驗(yàn)證成功后，再允許OU贖回自己的電子現(xiàn)金.具體協(xié)議如下：

3 安全屬性分析

本文所構(gòu)造的匿名的可傳遞外包計(jì)算協(xié)議具有正確性、公平性、不可重復(fù)花費(fèi)性、可傳遞性和傳遞憑條的不可鏈接性.下面分別進(jìn)行簡要的說明.

說明1：本協(xié)議具有正確性.如果外包者和用戶都是誠實(shí)的，他們將在付費(fèi)協(xié)議中執(zhí)行交換協(xié)議，并最終能保證用戶可以得到相應(yīng)的報(bào)酬，而外包者能得到正確的計(jì)算結(jié)果.

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

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

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

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

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

4 效率分析

把本文、Carbunar[2]和Chen[6]等構(gòu)建的協(xié)議分別從外包者單位時(shí)間的計(jì)算量、外包計(jì)算協(xié)議的公平性和匿名性3部分進(jìn)行比較，具體的比較結(jié)果見表1.

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

由表1可以知道新的外包計(jì)算協(xié)議，由于可傳遞條件模型的特性，可以允許外包者有一定的彈性驗(yàn)證時(shí)間，而且可以利用條件性對報(bào)酬的流向進(jìn)行調(diào)整，使得新協(xié)議中外包者單位時(shí)間的計(jì)算量不大，允許外包者可以處理很重的計(jì)算任務(wù)；也是因?yàn)榭蓚鬟f條件模型使得新協(xié)議具有公平性；由于GS證明的可自更新性保證了外包者和用戶的匿名性.因此，新協(xié)議的效率更高，更實(shí)用.

5 結(jié)束語

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

[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] 張江霄,李舟軍,高延武,等.基于花費(fèi)鏈最優(yōu)匿名的等長可傳遞電子現(xiàn)金系統(tǒng)[J].電子學(xué)報(bào),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] 任艷麗,丁寧,王天銀,等.可完全驗(yàn)證的雙線性對運(yùn)算外包算法[J].中國科學(xué)：信息科學(xué)，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] 李福祥,霍建秋,林慕清,等.基于雙線性映射的公共可驗(yàn)證外包計(jì)算方案[J].東北大學(xué)學(xué)報(bào)(自然科學(xué)版),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] 韓益亮,陳飛,楊曉元.可驗(yàn)證的外包屬性簽名方案[J].密碼學(xué)報(bào),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ì)算中空間位置關(guān)系的保密判斷[J].計(jì)算機(jī)學(xué)報(bào),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ì)算的無線體域網(wǎng)數(shù)據(jù)共享方案[J].通信學(xué)報(bào),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.

(責(zé)任編輯：孟素蘭)

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

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

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

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