仝 樂，郝 蓉，于 佳，2

1.青島大學 計算機科學技術學院，山東 青島266071

2.中國科學院 信息工程研究所 信息安全國家重點實驗室，北京100093

1 引言

雙線性配對運算[1]是密碼學中的基礎運算，被廣泛應用于各種密碼算法[2-5]。然而，雙線性配對運算十分耗時，因此很多學者對如何加速雙線性配對運算進行了研究[6-8]。但在計算資源受限的設備上，這些加速效果仍難以滿足要求。為解決這一問題，一些針對雙線性配對的安全外包方案被提出。

基于單服務器，Chevallier-Mames 等人[9]首次提出可驗證的雙線性配對運算外包協(xié)議。Kang 等人[10]對文獻[9]進行改進，提出更高效的方案。但這些方案的計算效率仍較低，在計算資源受限的設備中并不適用。Canard 等人[11]提出了一種更高效的可驗證雙線性配對運算外包協(xié)議，但該協(xié)議僅針對輸入可公開的情況。Guillevic 等人[12]提出了兩種滿足隱私性的雙線性配對運算外包方案，該方案在單服務器模型下，運行效率高于以往的方案，但該方案不能滿足可驗證性。以上基于單服務器的方案優(yōu)點是可用性較強，然而在用戶端的執(zhí)行效率較低。蔣鐵金等人[13]提出了一個基于單服務器的可驗證方案，雖然提高了本地設備運行效率，但方案中使用的預計算會占用資源受限設備的存儲空間，并且本地驗證率僅為2/5。

基于雙服務器，Chen 等人[14]首先提出一個雙線性配對安全外包方案。該方案引入預計算，使得資源受限設備僅需執(zhí)行5 次點加和4 次模冪運算，且可驗證率為1/2。Tian 等人[15]進一步提出兩個基于不串謀雙服務器的雙線性配對外包方案。第一個方案驗證率與Chen所提方案[14]相同，效率更高；第二個方案驗證率更高，但效率降低。Tian 的方案中仍使用了預計算。任艷麗等人[16]提出了一個驗證率更高的雙線性配對外包方案，可驗證率幾乎為1。以上方案在用戶端的效率得到了提高，但這些方案都基于兩個服務器不串謀的假設，這在實際應用中很難保證。因此基于單服務器設計的方案更有優(yōu)勢。

為解決以上問題，提出一個基于單服務器的雙線性配對安全外包方案，使用標量乘法外包技術和輸入盲化技術，避免了預計算，可驗證率接近1。同時資源受限設備在加密，驗證和恢復過程中不需要進行耗時的標量乘法運算，相比于之前方案效率更高。

2 問題描述

2.1 系統(tǒng)模型

圖1 所示為本文所提方案的系統(tǒng)模型，系統(tǒng)中有兩個實體，外包用戶和云服務器。外包用戶通常是計算資源受限的設備并且需要執(zhí)行耗時的雙線性映射運算。云服務器能提供可配置的計算資源。云計算服務使得用戶以最小的代價獲取并配置計算資源。用戶能完全控制云端的計算資源。用戶需要將計算任務e(A,B)外包給云服務器。用戶首先將要計算的雙線性映射函數(shù)向云服務器公開。為保證安全性，用戶將問題輸入點A，B和橢圓曲線參數(shù)E 盲化為A'，B'和E'，并發(fā)送給云服務器。用戶期望云服務器計算并返回被盲化的結果，并對其驗證，若驗證失敗則拒絕，若驗證通過則接受并對返回結果解盲化得到正確結果。

圖1 系統(tǒng)模型圖

2.2 設計目標

本文所提方案滿足以下要求：

（1）輸入輸出隱私性。用戶外包任務的原始輸入不能泄露給云服務器，云服務器計算得到的結果也是被盲化的結果。

（2）可驗證性。用戶能夠以接近1 的概率對云服務器的惡意行為進行檢測，只有當云服務器返回的結果正確才接受。

（3）高效性。用戶在盲化，驗證和恢復階段所用時間應該遠小于用戶在本地計算時間。

（4）無預計算。用戶端在執(zhí)行外包方案的過程中不需要進行預計算。

3 預備知識

3.1 橢圓曲線

記K=?p為有p個元素的有限域，E 為定義在K上的橢圓曲線。這個橢圓曲線可以用如下方程的形式來定義：

E(?p)上的一點A可以用坐標(x,y)的形式表達。點集E(?p)是一個有限域上的阿貝爾群。用E={a,b,p}來表示這個橢圓曲線。

3.2 橢圓曲線上的基本運算

3.2.1 雙線性配對運算

設循環(huán)加法群G1，G2和循環(huán)乘法群GT的階都是大素數(shù)p。雙線性配對可以表示成映射e：G1×G2→GT，這個映射滿足以下性質(zhì)：

（1）雙線性：對任意的R ∈G1,Q ∈G2和都有e( aR ,bQ)=e(R,Q)a。b

（2）非退化性：存在R ∈G1和Q ∈G2使得e(R,Q)1。（3）可計算性：對任意的R ∈G1和Q ∈G2，存在有效的算法可以計算e(R,Q)的值。

3.2.2 點加運算

給定一個定義在有限域上的橢圓曲線E，對于橢圓曲線上兩個不同的點P 和點Q，點加的過程為：過點P和點Q 做一條直線，直線與橢圓曲線相交的第三個點為R′，再過R′點做垂直于X 軸的直線，交橢圓曲線另一點為R，點R 就是點P 和點Q 相加的結果。定義：R=P+Q。

3.2.3 倍點運算

當點加運算中的兩個點無限接近于重合，這時兩點相加為倍點運算。倍點的計算過程為：過點P 做橢圓曲線的切線與橢圓曲線相交于點R'，再過R'點做垂直于X 軸的直線，交橢圓曲線另一點為R，定義：R=2P。

3.2.4 標量乘法運算

標量乘法是n個點P 相加的運算，定義：R=nP。目前計算標量乘的算法主要有二進制展開法，帶符號的二進制法，m 進制法，帶符號的m 進制法等。標量乘法的本質(zhì)是點加運算，使用優(yōu)化算法可以減少點加運算的次數(shù)。但是當標量較大時，對資源受限的用戶來說仍然是耗時的[17]。

4 方案描述

首先介紹了所提方案中用到的符號。接著介紹本文所提的雙線性配對外包新方案，該方案工作在單服務器模型下。然后對所提方案的安全性進行了分析，并在運行效率方面與其他協(xié)議做了比較。

4.1 符號描述

T 表示本地計算資源受限的用戶，U 表示云服務器，K表示一個域，?p表示模p 的有限域，E 表示有限域?p上的橢圓曲線，a和b表示橢圓曲線方程的系數(shù)，G1和G2表示循環(huán)加法群，GT表示一個循環(huán)乘法群，P1和P2分別表示群G1和G2的生成元，A和B 表示外包方案的輸入點，m 為安全參數(shù)。

4.2 新方案設計

輸入：A ∈G1，B ∈G2

輸出：e(A,B)

由雙線性配對的非退化性可知，e(P1,P2)為循環(huán)乘法群GT上的生成元。P1，P2和e(P1,P2)為公開參數(shù)。橢圓曲線上的點A，點B，P1和P2的坐標分別為：(x1,y1)，(x2,y2)，(x3,y3)，(x4,y4)。

本文所提方案流程如圖2 所示，用戶首先隨機選取參數(shù)，隨后將盲化后的標量和橢圓曲線上的點發(fā)送給云服務器。云服務器計算標量乘法并返回結，用戶收到后對雙線性配對的參數(shù)進行盲化，并向云服務器請求雙線性配對運算。云服務器進行雙線性配對運算，并將結果返回給用戶。用戶收到結果后進行驗證，若結果正確則接收并恢復原始結果，否則輸出“錯誤”。方案執(zhí)行過程如下：

圖2 方案流程圖

（1）用 戶T 隨 機 選 擇 g1, g2,t1,t2,r1,r2∈?p，k1,k2,k3,k4,k5,k6∈?p。T 隨 機 生 成 大 素 數(shù)q，并 計 算N=pq。大素數(shù)q 將模數(shù)p 轉換為N，隱藏了真實的模數(shù)。

（2）用戶T 計算：

該步驟對數(shù)據(jù)進行盲化，真實數(shù)據(jù)加上原始模數(shù)p的隨機整數(shù)倍，并模新模數(shù)N，得到盲化后的結果。用分 別 表 示 橢 圓 曲 線 上 坐 標 為，和的點。

（4）用戶T 收到云服務器返回的結果，使用真實模數(shù)p對返回結果取模，恢復想得到的結果：

（5）用戶T 利用上一步得到的數(shù)據(jù)對雙線性配對運算的真實輸入點A和點B 進行盲化，隨后將盲化后的e(A+R3,P2)，e(P1,B+R4)，e(A+R3,B+R4)和e(R1+R5,R2+R6)發(fā)送給云服務器U，請求雙線性配對運算。云服務器U 返回：

（6）用戶T 通過群的階來驗證云服務器U 返回的結果α1，α2，α3是否在群GT中：

（7）用戶T 通過對群GT中的α1，α2，α3和e(P1,P2)進行操作得到點e(A,B)作為最終的計算結果。同時計算在群GT中和α4應是相同的點。

5 安全性分析和效率分析

5.1 安全性分析

本文所提的雙線性配對運算外包方案是一種可驗證的安全外包方案，即本方案滿足完備性、保密性和可驗證性，證明如下：

（1）完備性：若云服務器是誠實的，通過所提方案第（7）步計算所得是正確的，這是因為：

（2）保密性（用戶數(shù)據(jù)隱私性）：保密性包含兩部分，一部分是用戶向云服務器發(fā)送數(shù)據(jù)的保密性，另一部分是云服務器計算結果的保密性。本文所提方案中，用戶T 向云服務器U 發(fā)送的數(shù)據(jù)都進行了盲化處理，比如在所提方案第（2）步，用戶T 通過隨機選取的k1，k2將方案的輸入點A盲化為點A'。云服務器U 不能從點A'中得到點A。因此云服務器接收到的數(shù)據(jù)均為隨機獨立分布在群G1和群G2中的點。模擬器S只需要隨機生成群G1和群G2中的點，此時，模擬器S的輸出和云服務器U接收到的數(shù)據(jù)在計算上是不可區(qū)分的。另外，云服務器計算的返回值需要解盲化才能得到真實結果，而解盲化所需的參數(shù)g1和g2由用戶在本地保存，因此云服務器不能從返回結果中得到真實結果。

（3）可驗證性：所提方案中存在等式：α3=e(A+若云服務器U不按照所提方案計算，那只能將一個隨機值作為α3返回給用戶T，那么用戶T 在本地計算得到的e(A,B)=的值可以認為是在群GT上隨機分布的。同樣的值也可以認為是在群GT上隨機分布的。此時云服務器U 返回的結果能通過用戶T 驗證的概率可以忽略。因此，用戶T 總是拒絕不可信服務器U 返回的錯誤結果。

本文所提方案與文獻[9]、[14]、[15]方案都能滿足完備性、保密性和可驗證性。其中完備性主要是利用雙線性配對運算的雙線性，用戶只需要進行點乘和模冪運算就可以得到正確結果。保密性是通過計算多個標量乘法并將結果混入雙線性配對的參數(shù)中來實現(xiàn)。文獻[14]和[15]中所提方案基于單惡意的雙服務器模型，其假設較強。而本文所提方案基于不可信單服務器模型，更符合實際應用場景。同時本文所提方案的驗證概率接近于1，而文獻[14]和[15]中所提方案的驗證概率均為1/2。通過下一節(jié)的分析，本文所提方案比文獻[9]中所提方案更高效。

5.2 效率分析

文獻[14]和[15]方案基于不串謀的雙服務器，本地計算效率比以往的單服務器方案有所提高，但方案中引入了預計算。表1和表2分別表示兩個方案中預計算所需占用的本地存儲空間，其中K 表示單位為千次，M 表示單位為百萬次。可以看出在外包雙線性配對運算次數(shù)為107且使用橢圓曲線d1003-291-247 時，文獻[14]和[15]中的方案預計算分別占用16.26 GB和9.49 GB的存儲空間，然而這在存儲資源受限的設備如智能卡上是難以實現(xiàn)的。

在表3 中，將本文方案與文獻[9]、[14]、[15]中方案所需的預計算做了比較，由文獻[15]可知k 大概為20，h小于10。在表4中，將這些方案在本地設備上的運算量做了比較。PA 表示在群G1或群G2上的點加運算，SM表示在群G1或群G2上的標量乘法運算，ME 表示在群GT上的模冪運算，BP 表示雙線性配對運算，M 表示群GT上的點乘運算。同時，表5中將本文方案與文獻[9]、GT上的模冪運算，BP 表示雙線性配對運算，M 表示群GT上的點乘運算。同時，表5 中將本文方案與文獻[9]、[14]、[15]在模型、預計算、隱私性和驗證率方面做了功能比較。

表1 Chen等人方案中預計算占用存儲空間

表2 Tian等人方案中預計算占用存儲空間

表3 預計算運算量比較

表4 用戶端運算量比較

表5 方案功能比較

如表3 所示，本文所提方案與文獻[9]中所提方案均不需要預計算，而文獻[14]和[15]方案則需要本地用戶進行預計算。如表4 所示，本文所提方案與Chevallier-Mames 等人所提方案[9]相比，用戶T 不需要進行標量乘法運算。本文所提方案在本地僅需2 次點加運算和10次模冪運算，而文獻[9]需要4 次點加運算，10 次模冪運算和6次標量乘法運算。與基于雙服務器的方案[14-15]相比，本文方案中用戶的運算量雖無明顯優(yōu)勢，但不需要預計算，節(jié)省了預計算占用的計算資源和存儲資源。從表5 可以看出，本文所提方案與文獻[9]不需要預計算，且基于單服務器模型，與文獻[14]、[15]相比假設更弱，更符合實際情況。而本文方案與文獻[9]方案相比，本文所提方案效率更高。

6 結束語

首先介紹了基于單服務器和雙服務器的安全外包雙線性配對運算的方案。在以往的方案中，基于單服務器的方案在本地運行效率較低?；陔p服務器的方案雖減少了用戶在執(zhí)行方案時的計算量，但都基于不串謀的假設，這在實際使用中并不實用。針對這些問題，設計了基于單服務器的安全外包方案，基于不可信單服務器，明顯更加實用。與同樣基于單服務器的以往方案相比，本文方案針對用戶本地的計算量進行了優(yōu)化，使得用戶端效率提高。同時用戶端也能以高概率對云服務器返回結果進行驗證。經(jīng)過比較分析，可以看出新方案明顯優(yōu)于目前已有的方案。

在設計對云服務器返回結果的驗證部分時，不可避免地用到了模冪運算，而模冪運算也是耗時的運算。如何在基于單服務器模型和雙服務器模型下針對雙線性配對運算進行效率更高的安全外包，將會是下一步要考慮的研究工作。