孫瑞，田有亮

（1. 貴州大學數學與統(tǒng)計學院，貴州 貴陽 550025；2. 貴州省公共大數據重點實驗室，貴州 貴陽 550025；3. 貴州大學計算機科學與技術學院，貴州 貴陽 550025）

安全可驗證的行列式云外包計算及其電子交易方案

孫瑞1,2，田有亮2,3

（1. 貴州大學數學與統(tǒng)計學院，貴州 貴陽 550025；2. 貴州省公共大數據重點實驗室，貴州 貴陽 550025；3. 貴州大學計算機科學與技術學院，貴州 貴陽 550025）

針對現有的云外包計算協(xié)議中服務端可能存在的用戶信息被泄露、篡改等問題，提出了一個云環(huán)境下的安全、高效、可驗證的矩陣行列式外包計算協(xié)議。首先，基于矩陣模糊技術構造云外包計算協(xié)議，它能夠在不需要任何困難性假設的前提下保證用戶信息的安全性；其次，通過構造一類特殊的變換矩陣對明文矩陣進行處理，使用戶在收到返還結果后，能有效驗證所反饋的計算結果是否被篡改，性能分析表明，此協(xié)議可以有效提高云外包計算的效率；最后，給出一個行列式外包計算的電子交易框架，能夠有效應用于電子商務等領域。

云外包計算；行列式計算；可驗證性

1 引言

云計算[1]是繼互聯(lián)網、物聯(lián)網之后信息技術領域引發(fā)的一次顛覆性變革[2]，然而，近幾年來云環(huán)境下屢發(fā)的用戶隱私被侵犯等問題使其成為制約云計算發(fā)展的關鍵因素。如何在為用戶正常提供云端服務的同時，保障其隱私不被泄露或篡改已成為相關人員面臨的重要研究課題。云外包計算是云計算的關鍵技術之一，近年來愈加受到學術界、商業(yè)界等眾多領域的廣泛關注。云外包計算，即云環(huán)境下的委托計算，是用戶在需要完成較為復雜的計算任務，又受限于自身設備的計算能力時，考慮將計算任務外包給具有海量計算能力的云端，后由云端將計算結果反饋給客戶端的過程。它能夠集中網絡平臺中閑置的各種計算資源構成設備平臺，向用戶提供具有超大規(guī)模計算能力的服務，既拓展了弱計算能力設備的功能，又為用戶節(jié)省了購買計算設備的昂貴成本[3]。

云外包在給人們帶來經濟、高效和靈活的服務的同時，也存在致命的安全隱患，如云服務端會因管理人員失職或黑客入侵造成用戶信息被泄露、篡改等問題。因此，云計算環(huán)境中用戶信息的安全性和計算結果的可驗證性是云外包技術發(fā)展、應用過程中面臨的關鍵性問題。1996年，Atallah等[4]提出了一個關于矩陣的乘法、求逆以及求線性方程組等線性代數的安全外包方案，隨后，他們利用偽裝技術提出了關于數值計算的安全外包方案[5]，但當時都未給出驗證反饋結果是否正確的方法。2010年，Atallah等[6]基于文獻[7]中的秘密共享方案對文獻[4]中矩陣的乘法運算進行改進，所構建的外包方案實現了可驗證性。Wang等[8]提出了一個求解大型線性方程組的外包計算方案，能夠安全、可驗證地解決線性方程組的求解問題。Lei等[9]提出了一個云環(huán)境下的大矩陣求逆外包計算方案，通過置換技術和蒙特卡羅[10]技術相結合，將客戶端計算的時間復雜度從O( n2.373)降低為 O( n2)，滿足了高效性，并且也是可驗證的。還有一部分學者站在同態(tài)、全同態(tài)加密的角度，研究線性代數的委托計算問題。Gentry[11]基于理想格提出了一個全同態(tài)加密方案， 但其運用到實際外包計算中的困難較大。2013年，靳方元[12]分別基于最大近似公約數困難性假設和求公約矩陣困難性假設，構造了針對矩陣運算的同態(tài)加密方案HME與全同態(tài)加密方案FHME，前者只能滿足有限次的矩陣乘法運算，而后者雖然密文長度有所減少、實用性增強，但也只適用于部分矩陣運算的范圍?？梢妼τ谕獍嬎惴桨傅陌l(fā)展，其主要趨勢是從滿足用戶數據的安全性，到實現外包方案的高效與可驗證性，再上升到減少密文長度與增強實用性的方向逐步完善。

對于矩陣行列式外包計算的研究，Mohassel[13]首先提出了一個關于行列式計算的同態(tài)加密外包思想，并且它是建立在密碼學假設的基礎之上。2013年，胡杏等[14]針對包含矩陣行列式在內的多個運算，通過矩陣拆分的方法，提出了一個可驗證的外包計算協(xié)議，并保證了用戶信息的安全性。鄔國欣[15]基于雙服務器模型，采用行與列拆分和矩陣模糊技術相結合的方式構造了一個安全的行列式外包計算方案，實現了抗雙服務器合謀和可驗證性的目標。

從相關的研究中可以看出，對于線性代數外包計算方案的構建有2種思路：一種是利用同態(tài)或全同態(tài)加密的方式，便于解密，但其安全性依賴于困難性假設，并且仍然存在密文長、通信量大和加解密效率低的缺陷，有些方案也并不適用于所有的線性代數運算，很難達到實用的標準；另一種思路則是通過矩陣變換的方法進行盲化處理，不需要建立在任何困難性假設的基礎上，且容易實現結果的可驗證性，卻仍然存在密文長、通信量大的缺點。

在分析上述研究的優(yōu)點與不足的基礎上，本文延續(xù)第2條思路——基于矩陣模糊技術[15]，提出一個針對矩陣行列式的安全、可驗證的外包計算協(xié)議。通過構造一類變換矩陣對明文矩陣進行矩陣模糊，整個外包過程中，在保證用戶信息安全性的基礎上，有效降低了用戶的計算量，并實現反饋結果的可驗證性目標。

2 外包計算模型

本文提出一個解決矩陣行列式的外包計算協(xié)議。在整個外包過程中，存在客戶端（委托方）和云端（計算方）兩方作為參與者。其中客戶端需要解決大規(guī)模矩陣行列式的復雜計算任務，但計算所需購買的設備十分昂貴；云端擁有閑置的

計算能力強大的設備平臺為解決各類復雜的計算問題提供服務。在外包過程中，為了保障用戶信息的安全性，需要對明文矩陣進行加密，由客戶端的加密模塊完成，其中包含密鑰生成階段和預計算階段。本文協(xié)議在用戶采取加密之前，分別先將明文矩陣中的每行元素進行處理，得到m個初級矩陣 X1,X2,… , Xm，另外再構造一個新的矩陣M，為后續(xù)驗證做準備。在經過置換矩陣加密后，客戶端把計算密文矩陣 Y1′, Y2′,… ,Ym′,M′行列式的任務外包給云端，隨后得到云端所反饋的結果。最后客戶端進入到解密和驗證階段，若結果通過驗證，則說明云端誠實工作；否則拒絕此結果，協(xié)議結束。具體的外包過程如圖1所示。

本協(xié)議所提出的外包計算系統(tǒng)所面對的安全威脅主要來源于云端，按照云端的行為特征可劃分為兩類威脅模型：半誠實模型[16]和惡意模型[17,18]。

半誠實模型：云服務端會誠實地按照協(xié)議完成計算任務，并不會篡改用戶的信息，但在此過程中仍會竊聽用戶的數據，以此得到用戶的敏感信息。

惡意模型：計算方沒有誠實地執(zhí)行協(xié)議，可能會出現泄露、篡改用戶信息或隨時終止協(xié)議等情況。

為了提高安全性，本協(xié)議主要是針對惡意模型下云服務端可能會存在的攻擊而構造。因此，本協(xié)議最終需要達到的目標有以下幾個。

1) 正確性：若云端誠實履行協(xié)議步驟，則其返還的結果一定為正確的。

2) 私密性：云服務端從輸入的數據中不能獲得初始行列式的具體內容，也不能從輸出值中獲取用戶所求結果的信息。

3) 可驗證性：當云端所反饋的結果正確時，用戶一定能夠驗證通過；當所反饋的計算結果錯誤時，用戶能驗證出并拒絕此結果。

4) 高效性：用戶使用本協(xié)議后的計算量遠遠小于其獨立完成行列式運算時的計算量以及云服務端在外包協(xié)議中的計算量。

3 委托計算協(xié)議

首先引入克羅內克函數的定義

用戶端想要將求矩陣X行列式的任務交給計算方進行計算，需要通過如下步驟和算法。

圖1 協(xié)議中的外包計算模型

3.1 原始數據預處理算法DCpret(X)

輸入 原始矩陣X。

輸出 隨機矩陣 X1,X2,… , Xm,M 。

第1步 隨機生成 i∈ [1,n]或 j∈ [1,n]。

第2步 將矩陣X的第i行(或第j列）的每個元素隨機拆分成 m (1 ＜ m ＜ n- 2)個元素之和，將其對應的元素替換矩陣X的第i行(或第j列）的相應元素，分別得到一組矩陣 X1,X2,…, Xm，使X=X1+ X2+… +Xm。

第3步 隨機選擇 t, r ∈ [1,n]且t ≠ r，計算矩陣M =XtXr。

第4步 輸出矩陣 X1,X2,… ,Xm,M 。 3.2 密鑰生成算法KeyGen

3.2.1 算法1 生成密鑰

輸入 一個安全參數λ

第1步 安全參數λ用來規(guī)定密鑰空間，客戶端在qF上均勻獨立生成 2m+ 組非零隨機數集

3.2.2 算法2 生成隨機置換函數π

第1步 設置初始 π= In(In為恒等置換）。

第2步 for j = 1∶(n - 1)。

第3步 設置i在j≤ i≤ n的隨機數。

第4步 交換 π[ i]和 π[ j]。

第5步 End for。

3.3 加密算法DCEnd(X,K)

輸入矩陣 X, X1,…, Xm,M 和密鑰K，用戶端調用算法 3進行加密得到行列式Y ′,Y1′,…,Ym′, M′。

算法3 DC加密

算法4 行列式計算

輸入 Y′, Y1′,… , Ym′ 和 M′

第1步 W從客戶端接收到加密后的矩陣 Y′, Y1′,… ,Ym′ ,M ′，調用任何存在的算法分別計算行列式值Y′,Y1′,… ,Ym′ ,M′。

l

若反饋結果同時滿足下列2個式子，則說明云端是誠實工作的；否則客戶端將拒絕接受所有結果，并終止協(xié)議。

4 協(xié)議分析與比較

4.1 協(xié)議分析

下面主要從正確性、安全性、可驗證性3個方面對本協(xié)議進行分析。

4.1.1 正確性

若云端嚴格按照協(xié)議完成計算，則其輸出結果一定正確。

又因為 P( i, j) = α δ ， P-1(i, j) =δ ，令

iπ(i),jπ-1(i),jY ′=PYP-1，則

2) 驗證和解密

①驗證階段

因為1-

′=

②解密階段

因此，若云端誠實履行協(xié)議，其反饋結果一定正確。

4.1.2 安全性

當矩陣規(guī)模和密鑰空間規(guī)模非常大時，敵手獲取輸入、輸出信息的概率是可以忽略的。

1) 獲取輸入信息的概率

1

對矩陣 Y, Y ,… ,Y中的每個元素及

2) 獲取輸出信息的概率

綜上分析，當密鑰空間與矩陣規(guī)模非常大時，敵手獲取輸入和輸出信息的概率都是可以忽略的，因此本協(xié)議保證了用戶輸入信息的隱私性和輸出信息的安全性。

4.1.3 可驗證性

對于云服務端反饋的計算結果，用戶能夠驗證出反饋結果是否被篡改。

若用戶要篡改輸出結果，并通過上面2個驗證條件時，首先要在Y′,Y1′,… ,Ym′ ,M′中確定Y′和M ′，共有 Cm

1

+2Cm

1+1種可能；其次要猜對系數集{l1, l2,… ,ln}和{s1, s2,… ,sn}，可能性為

1

2n，還要從Y1′,… ,Ym′ 中找到Yr′ ,Yt′，共有 Cm

2

qrt

所以，當云端誠實履行協(xié)議時，用戶所接收到的計算結果可以同時滿足式(1)和式(2)，反饋結果一定能夠被客戶端驗證通過并接受；當云端具有不誠實的行為時，便不能同時滿足上面的驗證條件，從而客戶端將拒絕此結果。因此，此協(xié)議為可驗證的。

4.2 性能分析與比較

本協(xié)議能夠有效降低用戶的計算量，使其效率有所提高。

表1 本文協(xié)議與相關協(xié)議的比較

在整個協(xié)議中，客戶端進行的各個階段有密鑰生成、加密、解密和驗證這4個部分，其主要的計算量在加密、解密和驗證階段，其時間復雜度最高為 O( n2)。假設云端計算行列式所用為較為常用的矩陣LC分解法[19]，則其時間復雜度為O( n3)；而客戶端獨立計算X原行列式的時間復雜度為 O( n3)，由此可知，通過本協(xié)議可以大大降低用戶的計算量。

現將本文提出的行列式外包計算協(xié)議與相關文獻中的方法進行比較，主要從效率、安全性、可驗證性和密鑰長度來分析。具體的比較結果如表1所示，其中，n表示行列式的階數，Sn和Fq分別表示變換群 Sn和有限域 Fq中元素的長度，m(1 ＜ m＜ n- 2)為把矩陣某行（或某列）元素分解為多個元素的個數。

相比密鑰長度更短，從而減小了用戶的開銷。

5 電子交易應用方案

在本文協(xié)議的基礎上，提出一個針對用戶的行列式外包計算的數據交易實例。本實例由用戶、云服務端W和可信第三方3部分組成，圖2為此外包計算交易的流程。

交易的具體過程如下。

1) 首先，用戶調用協(xié)議中的預處理算法DCPret( X )、密鑰生成算法KeyGen和加密算法DCEnd對原始數據進行處理。接著用戶在相應的交易機構進行注冊，提供合法的身份ID并獲取用來簽名的密鑰對 ID =＜ pkID,skID＞，再選擇合作的云服務端W以及業(yè)務，合成訂單并發(fā)送給可信第三方，同時向可信第三方支付外包費用。收款后可信第三方向用戶發(fā)送支付憑證，隨后用戶將訂單和密文信息發(fā)送給云服務端W提出交易。

2) 云服務端 W收到訂單與密文矩陣后調用協(xié)議中的算法DCSolve計算所求矩陣的行列式Y′,Y1′,… ,Ym′,M′，得到結果后將計算結果反饋給用戶。

3) 用戶調用協(xié)議中的解密算法DCDec和驗證算法DCVer對計算結果進行驗證，判斷反饋結果是否滿足驗證條件。若滿足，則接受此結果，并發(fā)送反饋結果有效的證明憑證給可信第三方，可信第三方核實憑證后公布訂單實現狀態(tài)，并將用戶支付的外包費用發(fā)放給云服務端W；若反饋結果不滿足驗證條件，則用戶拒絕此結果并發(fā)送反饋結果無效證明給可信第三方，可信第三方核實后發(fā)布訂單取消狀態(tài)，并退款給用戶，交易結束。

由于交易訂單是否能夠實現取決于云服務端的反饋結果能否通過用戶的驗證條件，所以，此交易方案可以有效避免因云服務端 W 的惡意篡改或為節(jié)約成本而隨意編造計算結果等行為對用戶造成的經濟損失。因此，通過執(zhí)行本方案，不但能夠節(jié)約用戶完成行列式計算的時間和成本，還保障了用戶的利益不受損失。

6 結束語

圖2 外包計算的電子交易流程

本文針對矩陣行列式運算提出了一個云環(huán)境下高效的、可驗證的外包計算協(xié)議。經過分析表明，本文協(xié)議在保證用戶信息安全性與可驗證性的基礎上，能夠實現高效性的目標。此外，在本文協(xié)議的基礎上給出了一個行列式外包計算的電子交易框架，可以有效地應用于電子商務等領域

中，保證用戶在進行交易時利益不受損失。接下來的工作是進一步研究如何提高云外包計算協(xié)議的效率，并將其運用到計算資源受限的應用環(huán)境。

[1] ARMBRUST M, FOX A, GRIFFITH R, et al. Above the clouds: a berkeley view of cloud computing[R]. UCB / EECS-2009-28. Berkeley, USA: Electrical Engineering and Computer Sciences, University of California at Berkeley, 2009.

[2] 馮登國, 張敏, 張妍, 等. 云計算安全研究[J].軟件學報, 2011, 22(1):71-83. FENFG D G, ZHANG M, ZHANG Y, et al. Study of cloud computing security[J].Journal of Software, 2011, 22(1):71-83.

[3] 羅軍舟, 金嘉暉, 宋愛波, 等. 云計算: 體系架構與關鍵技術[J].通信學報, 2011,32(7):3-21. LUO J Z, JIN J H, SONG A B, et al. Cloud computing: the architecture and key technologies[J]. Journal on Communications, 2011, 32(7):3-21.

[4] ATALLAH M J, KONSTANTINOS N, et al. Secure outsourcing of some computations[R].Indiana: Purdue University, 1996.

[5] ATALLAH M J, PANTAZOPOULOS K N, RICE J R, et al. Secure outsourcing of scientific computations[J]. Advances in Computers, 2002, 54(1):215-272.

[6] ATALLAH M J, FRIKKEN K. Securely outsourcing linear algebra computations[C]//The 5th ACM Symposium on Information. 2010: 48-59.

[7] SHAMIRA. How to share a secret[J].Communications of the ACM, 1979, 22(11):612-613.

[8] WANG C, REN K, WANG J. Harnessing the cloud for securely solving large-scale systems of linear equations [C]//The 31st International Conference on Distributed Computing Systems. 2011: 549-558.

[9] LEI X Y, LIAO X F, HUANG T W, et al. Outsourcing large matrix inversion computation to a public cloud[J]. IEEE transactions on Cloud Computing, 2013,1(1):78-87.

[10] MOTWANIR, RAGHAVANP. Randomized algorithms[M]. Cambridge: Cambridge University Press, 1995: 195-196.

[11] GENTRY C. Fully homomorphic encryption using ideal lattices[C]// ACM Symposium on Theory of Computing. 2009:169-178.

[12] 靳方元. 基于矩陣同態(tài)委托計算方案的研究與設計[D]. 蘇州:蘇州大學, 2013. JIN F Y. The research and design based on matrix homomorphism entrust calculation scheme[D]. Suzhou: Soochow University, 2013.

[13] MOHASSEL P. Efficient and secure delegation of linear algebra. Cryptology ePrint Archive, Report 2011/605[DB/OL]. http://eprint. iacr.org/2011/605.

[14] 胡杏, 裴定一, 唐春明. 可驗證安全外包矩陣計算及其應用[J].中國科學：信息科學, 2013,43(7): 842-852. HU X, PEI D Y, TANG C M. The caculation and application of verifiable secure outsourcing matrix[J]. Scientia Sinica Informations, 2013, 43(7): 842-852.

[15] 鄔國欣. 矩陣運算可驗證安全外包計算協(xié)議的研究[D]. 西安:西安電子科技大學, 2014. WU G X. Study of outsourcing matrix matrix verifiable security outsourcing computation protocol[D]. Xi’an: Xidian University, 2014.

[16] 羅文俊, 李祥. 多方安全矩陣乘法協(xié)議及應用[J]. 計算機學報, 2005, 28(7): 1230-1235. LUO W J,LI X. Multilateral security protocol and application of matrix multiplication[J]. Chinese Journal of Computer, 2005, 28(7): 1230-1235.

[17] 邵志毅. 云環(huán)境下的隱私保護計算[D]. 西安:陜西師范大學, 2015. SHAO Z Y. Privacy protection under the cloud environment[D]. Xi’an: Shaanxi Normal University, 2015.

[18] YANG B, YU Y, YANG C H. A secure scalar product protocol against malicious adversaries[J]. Journal of Computer Science & Technology, 2013, 28(1):152-158.

[19] 王開榮, 楊大地. 應用數值分析[M]. 北京: 高等教育出版社, 2010. WANG K R,YANG D D. Analysis of applied values[M]. Beijing: Higher Education Press, 2010.

[20] ZHANG J, ZHU Y, JIN F. Practical and secure outsourcing of linear algebra in the cloud[C]//International Conference on Advanced Cloud and Big Data. 2013: 81-87.

孫瑞（1993-），女，新疆烏魯木齊人，貴州大學碩士生，主要研究方向為密碼學理論與工程。

田有亮（1982-），男，貴州六盤水人，博士，貴州大學教授、碩士生導師，主要研究方向為算法博弈論、密碼學與安全協(xié)議。

Secure and verifiable outsourcing of determinant computing in the cloud and its electronic trading scheme

SUN Rui1,2, TIAN You-Liang2,3
(1. College of Mathematics and Statistics, Guizhou University, Guiyang 550025, China; 2. Guizhou Provincial Key Laboratory of Public Big Data, Guiyang 550025, China; 3. College of Computer Science and Technology, Guizhou University, Guiyang 550025, China)

In view of the problem that users’ informations are leaked and tampered possiblely exists at service terminal in existing outsourcing cloud computing protocols, a secure efficient and verifiable outsourcing protocol about determinant computing in the cloud was proposed. Firstly, the outsourcing computing protocol was based on the fuzz matrix technology and needed not under the premise of any difficulty assumptions to ensure the security of users’informations. Secondly, by means of generating a special kind of transformation matrixes to deal with plaintext matrix, then after the users receive the returned results, the correctness of these results can be verified effectively, and the performance analysis shows this protocol can effectively improve the efficiency of outsourcing cloud computing. Finally, an electronic trading framework for determinant outsourcing computing was proposed, which could be effectively applied to e-commerce and other fields.

outsourcing cloud computing, determinant calculation, verifiability

TP393

A

10.11959/j.issn.2096-109x.2016.00109

2016-09-10；

2016-10-23；通信作者：田有亮，youliangtian@163.com

國家自然科學基金資助項目（No.61363068）；貴州大學博士基金資助項目（No.2012-024）；貴州省教育廳科技拔尖人才支持基金資助項目（No.黔教合KY字[2016]060）

Foundation Items: The National Natural Science Foundation of China (No.61363068), Doctoral Fund Project in Guizhou University (No.2012-024), Science and Technology Top-notch Talent Support Project in Guizhou Province Department of Education (No.Qian Education Combined KY word [2016]060)