基于智能合約的雙線性對運算外包算法

李佩怡 李翔宇

(上海大學通信與信息工程學院 上海 200444)

0 引 言

云計算[1]是一種新型計算形式，它允許資源受限的用戶根據需求訪問計算資源共享池，即云服務器。它是繼計算機、互聯網后在信息時代的一個變革，是信息時代的一個巨大飛躍，它的產生使得外包計算成為可能。外包計算是指服務器幫助計算能力有限的用戶執行復雜度高的運算，并根據自己提供的計算服務向用戶收取相應的費用。外包計算解決了資源受限的用戶的計算問題，也極大地降低了用戶的計算成本。

盡管外包計算有其獨特的優勢，但是它也帶來了一些安全問題和挑戰[2]。首先，云服務器[3]只能被認為是半可信的，而資源受限的用戶的外包源可能包含一些敏感信息，用戶不希望將這些敏感信息暴露給服務器。因此，第一個安全挑戰就是保密性，即云服務器無法獲取用戶真正的計算內容及計算結果。其次，云服務器只能被認為是半可信的，因為它發送給用戶的計算結果可能是錯誤的。因此，第二個安全挑戰為可驗證性，即保證用戶可以驗證其接收到的計算結果是否正確。但是，用戶的驗證過程不能涉及很復雜的運算，否則外包將變得毫無意義。最后，外包計算的主要目的是降低用戶的計算成本。因此，在實現前兩者的前提下，需要保證外包算法中用戶的計算成本遠遠小于直接計算。

雙線性對運算是密碼學領域中常見的運算，但是它的復雜度較高，對計算能力有限的用戶來講，是極其耗時的，因此，許多研究人員希望將它外包給服務器進行計算。Chevallier等[4]首先提出了基于單個服務器的雙線性對外包算法。在該算法中，用戶通過付費的方式讓服務器執行雙線性任務，服務器計算完成后將計算結果發送給用戶，如果服務器返回錯誤的結果，用戶可以完全檢測到，但是，用戶還需要執行模指數運算和標量乘運算，其中模指數運算的復雜度約等價于雙線性對運算，所以該算法并不實用。與Chevallier等[4]不同，其他研究人員試圖實現基于兩臺服務器的高效外包算法。Chen等[5]首先提出在外包算法中加入預計算過程，由此提出了一種實用的雙線性對外包算法。該算法中，用戶首先執行預計算對數據進行隱藏，然后，由服務器執行多次雙線性對運算后，把結果發送給用戶。整個過程，用戶只需要執行一些簡單的運算，但是，用戶只能以1/2的概率檢測到服務器產生的錯誤，服務器依然可以欺騙到用戶。Tian等[6]提出了兩種雙線性對運算外包算法，該算法由兩臺服務器分開執行部分外包運算來保證用戶隱私。其中一種外包算法降低了用戶和服務器的計算量，但其可驗證性為1/2，另一種外包算法提高了可驗證性，但犧牲了用戶和服務器的效率。Ren等[7]提出了一種完全可驗證的雙線性對外包算法，但用戶需要與每臺服務器交互兩次，并且增加了一些計算代價。近年來，一部分研究人員將注意力重新轉向基于單個服務器的安全外包算法的研究工作中。Shao等[8]提出了一種面向車載網的完全可驗證的雙線性對外包算法。由于該算法特殊的應用場景，用戶的部分數據可以公開，對該算法的隱私性要求相對較低，因此云服務器的計算效率大幅提高。但是該算法的應用場景受限，且該算法中用戶的計算涉及復雜度極高的模冪運算。Dong等[9]提出了一種新的雙線性對外包算法，該算法引入集合來隱藏用戶的輸入，并且它的可驗證概率約為1。由于該算法引入集合來隱藏用戶信息，用戶的計算量及服務器執行對運算的次數增大很多。

近年來，隨著開源項目比特幣[10]的發展，大家逐漸認識到區塊鏈技術[11-13]。區塊鏈系統是由大量節點組成的去中心化的分布式系統，系統中的所有交易均需要由各個節點共同參與驗證，區塊鏈利用該共識機制[14-15]解決了系統中節點間的信任問題，從而確保了區塊鏈上數據的一致性和正確性。在外包計算中，用戶和服務器之間缺乏信任，而將區塊鏈技術應用在外包計算中就可以解決這一問題。Zhang等[16]為了實現安全外包服務的安全公平支付而不依賴第三方，提出了一種基于區塊鏈的公平支付框架，該方案用區塊鏈代替第三方支付平臺，用于云計算中的外包服務的付費環節。Hu等[17]首先提出了基于區塊鏈的搜索加密云方案，該方案使用智能合約替換中央服務器，構建了一個分散的隱私保護搜索方案，保證用戶可以從服務器處獲取到正確的搜索結果，而無須擔心惡意服務器的潛在錯誤行為。Wu等[18]提出了基于區塊鏈的匿名的分散式眾包方案BPTM，該方案提出由任務請求方和任務執行人分別將加密后的任務和個人信息發送給到區塊鏈系統，然后由區塊鏈進行任務匹配，該方案可以保證匹配結果的可靠性且不泄露用戶隱私。Lin等[19]首先提出了基于區塊鏈的雙線性對運算外包算法。該算法中，由區塊鏈來執行預計算、向兩個服務器分發外包任務并對服務器的返回結果進行驗證。但是，該算法中由于兩個服務器是半可信的，如果它們相互串通，可能會泄露用戶的隱私信息。

在基于對的密碼體制中，雙線性對運算一直是最昂貴的運算，它對密碼體制的實現有著非常重要的影響，另外，它在信息安全中有著廣泛的應用。本文結合區塊鏈中的智能合約，提出一種新的雙線性對安全外包算法。主要貢獻如下：(1) 與已有算法不同，本文算法將整個區塊鏈系統當作一個“服務器”，完全解決了服務器缺乏信任的問題。另外，利用智能合約的運行機制，用戶在外包算法中不需要驗證過程，即能實現可驗證概率為1。(2) 本文算法在確保用戶的隱私性的基礎上，降低了用戶和服務器的計算代價。(3) 將雙線性對運算通過智能合約部署在區塊鏈系統上，用戶可以隨時調用智能合約執行該算法，更加實用。

1 相關知識

1.1 雙線性對運算

設q為大素數，G1和G2是兩個生成元為P和Q、階為q的加法群，GT是一個階為q的乘法群。若滿足下列性質，則稱e:G1×G2→GT是一個雙線性對映射[20-23]：

(2) 非退化性。存在U∈G1，V∈G2，滿足e(U,V)≠1。

(3) 可計算性。對任意U∈G1，V∈G2，均可以計算e(U,V)。

若該雙線性映射存在，那么稱e(U,V)為一個雙線性對[20-23]。

雙線性對映射可通過基于有限群的超奇異橢圓曲線上的Weil或Tate對實現。為簡便起見，我們在本文中使用上述符號，更多細節參考文獻[20-23]。

1.2 智能合約

智能合約[24-25]又稱“智能合同”，它是一段提前設定好觸發條件后部署到區塊鏈上的程序。一旦達到智能合約的預設條件，智能合約便被自動執行。與普通合約一樣，智能合約也需要事先經過多方認證。部署在區塊鏈上的智能合約均有唯一的調用函數和相關參數，區塊鏈網絡中的各個節點可以根據不同的調用函數和參數執行不同的智能合約。智能合約的運行模型如圖1所示。

若需執行一個智能合約，客戶端需首先發起一筆交易，通知區塊鏈系統中的節點需要調用的函數及所需參數。系統中的所有節點都將接收到這筆交易，然后每個節點會調用相應的函數從區塊鏈系統中獲取對應的智能合約，并在本地環境中執行該智能合約獲得執行結果。為防止惡意節點作惡，每個節點在運行智能合約后，需要將自己得到的結果與區塊鏈中其他節點的結果進行比較。最后，當各個節點在確認最終結果無誤后才將該結果記錄到區塊鏈上。目前支持智能合約的有以太坊、Hyperledger Fabric。

1.3 安全定義

Hohenberger等[26]首先對安全外包計算做出形式化定義。下面，我們做簡要介紹。算法Alg由可信方T和不可信程序U組成，其中：可信方T為資源受限的用戶；不可信程序U為云服務器。另外，TU表示用戶T調用云服務器U進行計算。敵手A=(E,U′)，其中：E表示惡意環境，在該環境下，Alg會提交惡意輸入；U′表示惡意環境E生成的惡意軟件，它會試圖代替U作惡。

定義1(外包定義) 如果算法Alg接受5個輸入，并生成3個輸出，我們則稱算法Alg遵守外包算法的輸入/輸出規范。有關外包算法Alg輸入/輸出的詳細描述如表1所示。

表1 外包的輸入/輸出

安全模型需確保：即使可信方T使用了惡意環境E撰寫的惡意軟件U′，E和U′也不能獲取外包算法TU的輸入和輸出的任何信息。

定義2(安全模型) 若算法Alg可以滿足下列條件，我們則稱TU是算法Alg的一次安全執行。

(1) 正確性。TU是Alg的一次正確執行。

(2) 保密性。對于所有的敵手A=(E,U′)，在TU的執行過程中不能得到有關算法Alg輸入/輸出的任何信息。

若需證明算法Alg滿足保密性，則需證明對于所有的敵手A=(E,U′)，存在兩個模擬器(S1,S2)在計算上不能正確區分隨機變量EVIEWreal～EVIEWideal和UVIEWreal～UVIEWideal。其中：EVIEWreal～EVIEWideal表示惡意環境E在TU的執行過程中不能得到算法Alg輸入/輸出的相關信息；UVIEWreal～UVIEWideal表示惡意環境E撰寫的惡意軟件U′在TU執行過程中不能得到算法Alg輸入/輸出的相關信息。該部分的詳細證明可參考文獻[26]。

定義3((α,β)-outsource-security) 假設TU是算法Alg的一次正確執行，對于任意輸入x，如果T的運行時間小于或等于Alg的α倍，并且用戶T能以大于或等于的概率發現服務器U的惡意行為，則稱(T,U)是算法Alg的(α,β)-outsource-security實現。

2 基于智能合約的雙線性對運算外包方案

2.1 方案概述

本文算法的參與方包括用戶和“服務器”。與以往算法[5-9]不同，此處的“服務器”是指區塊鏈系統。該方案將原本需要服務器計算的雙線性對運算寫入智能合約，并將智能合約部署在區塊鏈系統上，用戶可以隨時調用智能合約執行雙線性對運算。

同樣地，為了保證隱私性，我們需要將雙線性對運算的輸入和輸出進行隱藏。整個方案的流程如圖2所示。與文獻[5-9]中一樣，我們也要先調用Rand子程序生成所需參數，對雙線性對運算的輸入進行隱藏。然后，由用戶發起一筆交易，通知區塊鏈系統中的各個節點需要調用的函數及所需參數。之后，各節點利用調用函數從區塊鏈系統中讀取相應的智能合約，并在本地執行環境執行該智能合約獲得執行結果。為防止惡意節點作惡，每個節點在運行智能合約后，需要將自己得到的結果與區塊鏈中其他節點的結果進行比較。當各個節點在確認最終結果無誤后，該結果才會被記錄到區塊鏈上。最后，用戶檢索區塊鏈上的交易數據，獲得相應的運算結果，再執行部分簡單計算獲得最終的結果。

從上文中可知，最終被寫入區塊鏈中的數據已經經過各個節點的相互對比驗證，故該結果是完全可信的，所以本文方案中減少了用戶驗證的環節，但可以保證算法的可驗證性為1。

2.2 Rand子程序

為了保證算法的隱私性，我們引入集合來構造元素間的關系。集合之間的關系如圖3所示，即A=A1∪A2∪A3，B=B1∪B2∪B3。Rand子程序生成amP時，將元素amP隨機分布在集合A1、A2、A3中；生成bnQ時，將元素bnQ隨機分布在集合B1、B2、B3中。其中m∈{2,3，…，i},n∈{2,3，…，i}。每個集合中需至少包含一個元素。集合A1、A2、A3中的元素分別用am1P、am2P、am3P表示，集合B1、B2、B3中的元素分別用bn1Q、bn2Q、bn3Q表示。

因此，Rand生成的元素間應存在如下關系：

(1)

(2)

2.3 具體算法

結合區塊鏈和智能合約，提出一個雙線性對運算的安全外包算法VCBP(Verifiable-Contracts-Bilinear Pairings)。在該算法中，需要由服務器執行的雙線性對運算被寫入智能合約，該智能合約被部署在區塊鏈系統上。用戶通過發起交易通知區塊鏈中的各個節點執行智能合約從而得到所需雙線性對運算的結果。

令q為一個大素數，算法的輸入為兩個隨機點A和B，其中A∈G1，B∈G2，輸出為e(A,B)。另外，A、B和e(A,B)對智能合約都是保密的。算法的執行過程如圖4所示，具體算法如下：

2) 用戶T隨機詢問區塊鏈系統，系統返回計算結果：

U(A+a1P,B+b1Q)→e(A+a1P,B+b1Q)U(amP,B+b1Q)→e(amP,B+b1Q)=αmU(A+a1P,bnQ)→e(A+a1P,bnQ)=βn，m∈{2,3,…,i}，n∈{2,3,…,i}U(ai+1P,B+b1Q)→e(ai+1P,B+b1Q)=θ1U(A+a1P,bi+1Q)→e(A+a1P,bi+1Q)=θ2

3) 由于區塊鏈上的記錄的計算結果是由區塊鏈中的節點聯合得出的，所以上述結果是完全可信的。因此，用戶T獲得區塊鏈系統返回的結果，就可以直接計算最終結果：

(1)T計算：

(3)

(4)

(2)T再計算：

e(A,B)=e(A+a1P,B+b1Q)e(-a1P,B+b1Q)·

e(A+a1P,-b1Q)e(a1P,b1Q)

(5)

3 安全性及性能分析

3.1 安全性分析

我們首先分析了算法的隱私性、可驗證概率和復雜度，然后結合安全性定義給出了嚴格的安全證明。

(1) 隱私性。如果區塊鏈中的惡意節點想要獲得雙線性對運算的輸入信息，那么可以分為如下情況：

如果惡意節點想要獲取輸入A的信息，那么它必須知道a1P，則它必須知道我們構造a1P所用的各個元素。因為ρm∈{+1,-1},m∈{2,3，…,i}，所以惡意節點猜出ρ的概率為2-(i-1)；因為t1、t2、t3取區間[1,s]中的任意整數，所以惡意節點猜出t1、t2、t3的概率為s-3；因為amP隨機分布在集合A1、A2、A3中，m∈{2,3，…,i},所以，惡意節點猜中amP的概率為3-(i-1)，因此，節點猜出A的概率為s-36-(i-1)；同理，節點猜出B的概率為s-36-(i-1)。

因此，惡意節點猜出雙線性對運算的輸入的概率為s-66-2(i-1)。當s=5、i=10時,雙線性對運算中敏感信息暴露的概率為10-17，可以忽略不計。

(2) 可驗證概率。在本文方案中，用戶調用智能合約來執行雙線性對運算，相當于把區塊鏈系統當作一個大型“服務器”。在區塊鏈系統中，每個節點在本地執行環境運行智能合約后，需要將自己得到的結果在網絡中廣播，與區塊鏈中其他節點的結果進行比較。當網絡中的節點對比計算結果后，超過一半的節點對計算結果達成共識，則該結果作為最終結果被記錄到區塊鏈上。否則，網絡中的節點需再次執行智能合約，完成外包任務。在該系統中，一旦有惡意節點作惡，便會在結果比對環節被立馬檢測出來。所以，該算法的可驗證概率為1。

(4) 安全性證明。下面本文方案給出嚴格的安全性證明，相應的安全性定義證明可參考文獻[26]。

定理1在基于單個服務器的模型中，本文算法(T,U)是VCBP算法的正確執行，其中算法的輸入(A,B)可能是誠實的、保密的、誠實的，受保護的或惡意的、受保護的。

證明在基于單個服務器的安全模型中，令(E,U′)是與PPT算法T交互的PPT敵手。

第一，證明EVIEWreal～EVIEWideal，即惡意環境E在TU的執行過程中不能得到有關算法Alg輸入/輸出的任何信息。

由于算法的輸入(A,B)分為三種情況，因此，分開討論：

如果輸入(A,B)為誠實的、受保護的或者惡意的、受保護的，那么惡意環境E總是可以獲取輸入(A,B)。在這兩種情況下，模擬器S1將與real環境下一樣，總是能夠知道輸入(A,B)。

劉俊紅等[4]對廢舊膠粉的改性方法及原理作了簡要介紹，重點綜述了廢橡膠粉在聚乙烯、聚丙烯、聚氯乙烯等橡塑復合材料中的研究和應用進展。對廢橡膠粉在橡塑復合材料中的研究、開發和應用前景進行了展望。

綜上所述，我們可以得出在基于單個服務器的模型中，本文算法(T,U)是VCBP算法的正確執行，其中算法的輸入(A,B)可能是誠實的、保密的，誠實的、受保護的或惡意的、受保護的。

3.2 性能分析

本節將本文算法VCBP分別與Shao等[8]提出的CVCC算法和Dong等[9]提出的BPS算法的性能進行了比較，如表2所示。其中，PA、SM、MExp、MM、MInv、Pair依次表示加法群G1或G2中的點加運算、標量乘、乘法群GT中的模冪運算、模乘運算、模逆運算、雙線性對運算。

表2 基于單個服務器的雙線性對外包算法性能比較

根據3.1節的安全性分析可知，如果我們設s=5、i=10,則雙線性對運算中敏感信息暴露的概率為10-17，可以忽略不計。

假設s=5、i=10。由表2可知，與CVCC算法[8]相比，首先，本文算法用戶的計算過程中，不涉及標量乘和模冪運算。其次，雖然我們的算法用戶的計算過程中增加了1次點加運算和2次模逆運算，但是這兩種運算的計算代價很小，所以增加的計算成本可以忽略不計。最后，在本文算法中，用戶需要多執行約42次模乘運算，但是，在CVCC算法[8]中用戶需要執行1次模冪運算。而模冪運算的計算復雜度非常高，用平方乘方法計算1次模冪運算，約需執行1.5L次模乘運算，L是模冪運算中指數的比特長度。通常，L至少取160 bit，因此，1次模冪運算大約相當于240次模乘運算。因此，用戶執行1次模冪運算的計算代價要遠遠大于執行42次模乘運算的計算代價。同時，CVCC算法[8]和本文算法，用戶均需要執行一次Rand子程序。而本文算法中， Rand子程序并不需要執行模冪運算。另外，CVCC算法[8]是面向車載網的，由于其特殊的應用場景，該算法中輸入B是可以公開的，而本文算法VCBP中，輸入A和B是完全保密的，所以，這就導致了CVCC算法和本文算法中云服務器執行雙線性對運算的次數有所差異。除此之外，本文算法VCBP的性能要遠遠高于CVCC算法[8]。

4 實 驗

本節做了一些實驗來評估所提算法VCBP和其他算法[8-9]的效率。在實驗中，設置s=5、i=10，用戶由一臺Intel core i3 CPU(2.5 GHz)、4 GHz內存的計算機模擬。其中，智能合約部署在Hyperledger Fabric上，我們使用另一臺Intel core i5 CPU(1.6 GB)、8 GB的計算機連接Hyperledger Fabric區塊鏈系統，模擬區塊鏈系統中的一個節點去運行智能合約，幫助用戶執行雙線性對運算，該節點表示區塊鏈中的任意一個節點。另外，使用的編程語言為Java，并使用了JPBC(Java-Pairing-Based Cryptography)數據庫。

關于算法中智能合約的部署過程如下：

(1) 設置Java鏈代碼開發環境：首先，利用開源的應用容器引擎Docker和Docker Hub的預構建區塊鏈網絡組件鏡像來運行本地區塊鏈網絡；其次，安裝構建軟件Gradle和HTTP客戶端軟件SoapUI，Gradle用于構建鏈代碼，即智能合約，SoapUI用于實現智能合約與Hyperledger Fabric的REST接口間的通信；然后，完成區塊鏈定義，并啟動本地區塊鏈網絡；最后，從Hyperledger Fabric的GitHub存儲庫獲取最新源代碼，構建Java shim客戶端JAR。

(2) 編寫和構建算法中的Java鏈代碼，即智能合約：首先，安裝適用于Eclipse(基于Java的開發平臺)的Gradle Buildship插件，從GitHub存儲庫中克隆名為ChaincodeTutorial的Java鏈代碼框架項目，并將該項目導入開發平臺Eclipse中；然后，編寫算法中的智能合約代碼，并利用單元測試框架Junit來測試；最后，使用開發平臺Eclipse和Eclipse的Gradle Buildship插件構建智能合約。

(3) 部署并執行鏈代碼：首先，向本地區塊鏈網絡注冊已經構建好的智能合約；然后，打開SoapUI，導入步驟(2)中克隆的Chaincode Tutorial項目中的REST項目，打開REST項目中的ChaincodeLog Deploy請求，并提交請求，至此，算法中的鏈代碼部署完成；最后，調用函數運行鏈代碼。

本文算法中所部署的智能合約的核心代碼如下，該部分代碼主要實現外包任務中所有的雙線性對運算，即2.3節中步驟2)由區塊鏈執行的雙線性對運算。

protected void uResponse() {

Q1=pairing.pairing(inputA_a1P,inputB_b1Q);

for(int i=0;i<9;i++) {

alpha[i]=pairing.pairing(aP[i],inputB_b1Q);

beta[i]=pairing.pairing(inputA_a1P,bQ[i]);

}

theta[0]=pairing.pairing(aP[9],inputB_b1Q);

theta[1]=pairing.pairing(inputA_a1P,bQ[9]);

}

代碼中，Q1表示e(A+a1P,B+b1Q)，alpha[i]表示αm，beta[i]表示βn(m∈{2,3,…,10}，n∈{2,3,…,10})，theta[0]和theta[1]分別表示θ1和θ2。其中，函數pairing.pairing()為JPBC(Java-Pairing-Based Cryptography)數據庫自帶的函數，可以直接調用它來執行雙線性對運算。

接下來，我們根據模擬實驗的結果對所提算法VCBP和其他算法[8-9]進行了對比。

圖5是VCBP算法的模擬實現。在算法VCBP中，用戶將復雜度極高的雙線性對運算交給區塊鏈系統，并且由于智能合約的運行機制，用戶可以免去驗證過程，所以，用戶只需執行少量的簡單運算，如模乘運算、點加運算等。因此，如圖5所示，在VCBP算法中，用戶執行簡單運算花費的時間要遠遠小于直接執行雙線性對運算。另外，智能合約的運行機制也保證了算法VCBP的可驗證概率為1，所以VCBP算法是完全可驗證的雙線性對外包算法。

如圖6所示，我們將VCBP算法分別與Shao等[8]和Dong等[9]提出的雙線性對運算外包算法中用戶的執行時間進行比較。如圖6(a)所示，當s=5、i=10時，VCBP中用戶的計算成本要遠遠低于CVCC[8]。如圖6(b)所示，當s=5、i=10 時，VCBP中用戶的計算成本約為BPS算法[9]的一半，另外，本文算法的可驗證概率為1。

圖7比較了VCBP算法和Shao等[8]及Dong等[9]提出的雙線性對運算外包算法中服務器的執行時間。由圖7可知，當s=5、i=10時，與VCBP相比，CVCC算法[8]中服務器的計算時間非常低，但是由于CVCC算法中用戶需要執行復雜的模冪運算，所以CVCC算法[8]中服務器的計算時間與VCBP不具有可比性。與BPS[9]相比，VCBP中服務器的計算消耗也有所降低。

通過上述對比實驗可知，與Shao等[8]提出的算法CVCC算法以及Dong等[9]提出的BPS算法相比，VCBP中用戶的計算代價有了大幅度降低，服務器的計算代價也有一定降低。另外，本文算法的可驗證概率可達到1。綜上所述，與已有算法[8-9]相比，本文算法的安全性和性能更高。

5 結 語

基于單個服務器的安全模型，本文利用智能合約的運行特點，將安全外包與區塊鏈相結合，提出一個新的雙線性對運算外包算法。本文算法能夠保護用戶數據的隱私性，并且用戶從區塊鏈獲得的數據不需要進行驗證就可以使用，減少了驗證環節。同已有的基于單個服務器的雙線性對運算外包算法相比，本文算法在保證安全性的基礎上，同時提高了用戶和服務器的計算效率，并且實現了完全可驗證性。