方陣冪可驗證安全云計算外包方案研究

1、方陣冪可驗證安全云計算外包方案研究重慶大學碩士學位論文（學術(shù)學位）學生姓名：劉午陽 指導教師：廖曉峰教 授 專業(yè)：計算機系統(tǒng)結(jié)構(gòu) 學科門類：工學重慶大學計算機學院二 O 一五年四月Research on the Scheme of Verifiable and Secure Cloud Computation Outsourcing of Square Matrix PowerA Thesis Submitted to Chongqing University in Partial Fulfillment of the Requirement for theMasters Degree of

2、EngineeringBy Wuyang LiuSupervised by Prof. Xiaofeng Liao Specialty: Computer ArchitectureCollege of Computer Science of Chongqing University, Chongqing, China.April, 2015摘要為了解決計算能力有限的對象（用戶）所面臨的大維數(shù)方陣的高次冪計算問題， 作者利用云計算平臺（云服務端），提出了一個方陣冪可驗證安全云計算外包方 案。該方案中包含兩個不同的云計算外包協(xié)議，它們分別是基于單云外包模型的 方陣冪可驗證安全云計算外包協(xié)議（S-S

3、MP 協(xié)議）和基于雙云外包模型的方陣冪 可驗證安全云計算外包協(xié)議（D-SMP 協(xié)議）。在 S-SMP 協(xié)議中，用戶首先構(gòu)造一個隨機置換，再結(jié)合克羅內(nèi)克函數(shù)，生成 一個非奇異方陣，并求得其逆矩陣，這兩個方陣即為密鑰；用戶用此密鑰完成對 原方陣的加密，然后將方陣冪中的指數(shù)和加密所得方陣一起發(fā)送給云端；云端完 成加密所得方陣的求冪運算，并將計算所得方陣返回給用戶；用戶使用持有的密 鑰解密云端返回的方陣，并隨機選取若干解密所得方陣中的元素與相應的由用戶 自己計算所得的正確值進行對比，以驗證解密所得方陣是否正確。在 D-SMP 協(xié)議中，用戶首先利用與 S-SMP 中同樣的方法構(gòu)造兩組密鑰（每組 密鑰包含

4、一個非奇異方陣及其逆矩陣）；用戶用這兩組密鑰分別對原方陣進行加 密，得到兩個加密后的方陣，然后將加密所得的兩個方陣和原有的指數(shù)分發(fā)給兩 個不同的云端；每個云端各自完成所接收到的加密所得方陣的求冪運算，并將計 算所得方陣返回給用戶；用戶使用持有的兩組密鑰解密相應云端返回的方陣，并 對解密所得的兩個方陣進行對比，以驗證解密所得方陣是否正確。經(jīng)過理論分析可知：S-SMP 和 D-SMP 協(xié)議均滿足外包協(xié)議的四個基本要求， 即正確性、安全性、可驗證性和高效性。在對 S-SMP 協(xié)議和 D-SMP 協(xié)議分別進 行仿真的實驗中，將方陣冪問題分為方陣階數(shù)固定指數(shù)變化和指數(shù)固定方陣階數(shù) 變化兩種情形單獨進行，

5、每種情形下計算方陣冪時又分別采用了定義法和二分法 這兩種不同的方法。實驗結(jié)果表明，與用戶自身完成原方陣冪計算任務相比，以 上兩種形式的方陣冪在不同的云計算外包方式下均能大幅減少用戶的計算耗時， 獲得較好的外包性能，且除了方陣階數(shù)固定指數(shù)變化型方陣冪在單云外包模型二 分法情形以外，其它情形下的云計算外包性能均隨著方陣維數(shù)和指數(shù)的增加而提 高。關(guān)鍵詞：方陣冪，云計算，安全外包計算，可驗證，隨機置換ABSTRACTComputing the high power of huge-dimension square matrix is a hard job for those entities (cli

6、ents) with limited compute capability, therefore, a verifiable and secure cloud computing outsourcing scheme of square matrix power is designed based on the cloud computing platform. In the scheme, two different cloud computing outsourcing protocols are involved. One is the verifiable and secure clo

7、ud computing outsourcing protocol of square matrix power based on single cloud outsourcing model (S-SMP), and the other is the verifiable and secure cloud computing outsourcing protocol of square matrix power based on double cloud outsourcing model (D-SMP).In the S-SMP protocol, the client firstly c

8、onstructs a random permutation and generates a secret key which includes a non-singular square matrix and its inverse matrix by combining the permutation with the Kronecker function. Secondly, the original square matrix is encrypted with the secret key by the client, and then the encrypted matrix is

9、 sent to the cloud along with the original exponent. After completing the calculation of the encrypted square matrix power, the cloud returns the result to the client. On receiving the returned result, the client decrypts it with the secret key and compares the elements that are randomly chosen by t

10、he client with the accurate values computed by the client himself correspondingly to verify the correctness of the result.In the D-SMP protocol, the client firstly constructs two groups of secret keys using the same method as in S-SMP protocol and each group contains a non-singular square matrix and

11、 its inverse. Secondly, the original square matrix is encrypted separately with the different secret key by the client, and then the result matrices of the encryption are dispatched to two different clouds along with the original exponent. After completing the calculation of the encrypted square mat

12、rix power, each cloud returns the result to the client. On receiving the returned results, the client decrypts them with the corresponding secret key and compares the elements of the decryption results correspondingly to verify the correctness of the result.Theoretical analysis shows that the protoc

13、ol meets the requirements of outsourcing protocol well, which includes correctness, security, verifiability and high efficiency. In the simulation experiments of S-SMP protocol and D-SMP protocol, square matrix power are divided into two aspects: dimension fixed exponent changing and exponent fixed

14、dimension changing. At the same time, the computation of square matrix powerare conducted in two ways: the definition method and the dichotomy method. Finally, the experiment result illustrates that outsourcing computation of both cases of square matrix power, compared with the client completing the

15、 original job himself, can substantially reduce the time consumption of the client and derive a desirable outsourcing performance under each protocol of S-SMP and D-SMP. Except the single cloud outsourcing of square matrix power with dimension fixed exponent changing using dichotomy method, the clou

16、d computation outsourcing performance of the others becomes better with the increase of dimension and exponent.Keywords: square matrix power, cloud computing, secure outsourcing computing, verifiable, random permutation目錄中文摘要I英文摘要II1 緒論11.1 研究背景與意義11.1.1 云計算21.1.2 外包計算51.1.3 安全云計算外包協(xié)議51.2 外包計算技術(shù)研究現(xiàn)狀

17、61.3 主要貢獻及內(nèi)容安排82 基礎(chǔ)知識介紹92.1 研究涉及的相關(guān)概念92.1.1 方陣與方陣冪92.1.2 克羅內(nèi)克函數(shù)92.1.3 隨機置換92.2 可驗證安全云計算外包模型102.2.1 單云外包模型102.2.2 雙云外包模型112.3 可驗證安全云計算外包協(xié)議構(gòu)成122.4 可驗證安全云計算外包協(xié)議特性122.5 研究涉及的幾個算法132.5.1 隨機置換構(gòu)造算法132.5.2 可逆方陣及其逆矩陣構(gòu)造算法142.5.3 方陣冪計算算法152.6 本論文研究相關(guān)的幾項證明172.7 本章小結(jié)193 方陣冪的傳統(tǒng)解法203.1 歸納法求解方陣冪203.2 二項式定理法203.3 乘法

18、結(jié)合律法213.4 相似對角化法223.5 Hamilton-Cayley 定理法233.6 初等變換法233.7 分塊對角矩陣法243.8 本章小結(jié)244 方陣冪可驗證安全云計算外包協(xié)議254.1 問題描述254.2 單云外包模型下的方陣冪可驗證安全云計算外包協(xié)議254.2.1 協(xié)議內(nèi)容描述264.2.2 協(xié)議要素分析274.3 雙云外包模型下的方陣冪可驗證安全外包云計算協(xié)議284.3.1 協(xié)議內(nèi)容描述294.3.2 協(xié)議要素分析304.4 本章小結(jié)325 仿真實驗結(jié)果與分析335.1 仿真實驗平臺介紹335.2 仿真實驗中的參數(shù)定義335.3 S-SMP 協(xié)議實驗結(jié)果與分析345.3.1

19、S-SMP 協(xié)議仿真實驗結(jié)果345.3.2 S-SMP 協(xié)議仿真實驗結(jié)果分析355.4 D-SMP 協(xié)議實驗結(jié)果與分析365.4.1 D-SMP 協(xié)議仿真實驗結(jié)果365.4.2 D-SMP 協(xié)議仿真實驗結(jié)果分析375.5 單/雙云模型下外包結(jié)果綜合分析385.5.1 指數(shù)固定方陣階數(shù)變化型方陣冪外包結(jié)果分析385.5.2 方陣階數(shù)固定指數(shù)變化型方陣冪外包結(jié)果分析395.6 本章小結(jié)436 結(jié)語與展望446.1 結(jié)語446.2 展望44致謝46參考文獻47附錄47A. 作者在攻讀學位期間發(fā)表的論文目錄471 緒論“云計算”的概念由谷歌的 CEO 埃里克施密特在 2006 年 8 月 9 日搜索引

20、擎大 會上首次提出。此概念提出之后，立即在學術(shù)界和工業(yè)界引起了巨大轟動，以至 于云計算成為了當前發(fā)展十分迅速的新興產(chǎn)業(yè)，甚至有人將它視為繼微型計算機、 互聯(lián)網(wǎng)之后的第三次信息技術(shù)革命。從信息技術(shù)歷史發(fā)展的角度來看，云計算是互聯(lián)網(wǎng)技術(shù)發(fā)展、優(yōu)化和融合的 產(chǎn)物。它能為整個社會的信息化提供一種全新的服務模式，給人類的社會生活帶 來巨大變革，因而促使信息化經(jīng)濟時代早日到來。對于云計算所提供的全新的服務模式，具體來說是一種基于訪問權(quán)控制的按 使用量付費的服務模式，這種模式的特點在于它能提供可用的、便捷的、按需的 網(wǎng)絡訪問，讓云用戶得以共享已經(jīng)優(yōu)化配置的計算資源池（共享池中的計算資源 包括：網(wǎng)絡、服務器、

21、存儲、應用軟件、服務等），而且用戶只需要與云服務供 應商完成較少的交互，即可立即享有這些資源，完成自己的任務。鑒于云計算強大的計算和服務能力，以及未來發(fā)展的巨大潛力，現(xiàn)如今越來 越多的國家把云計算的發(fā)展提升到了國家戰(zhàn)略層面，并作出了較長遠的規(guī)劃。就 我國而言，云計算作為新一代的信息技術(shù)已經(jīng)被納入到十二五規(guī)劃重點扶植的戰(zhàn) 略新興產(chǎn)業(yè)當中，各級政府、有關(guān)機構(gòu)和社會各界均對此高度重視并開始積極的 探索，以百度、阿里巴巴、騰訊為首的互聯(lián)網(wǎng)公司均已推出云計算服務類產(chǎn)品。一般來說，只要有信息的傳遞與共享，那么其中信息的安全問題便是一個不 得不考慮的問題。在云計算服務中，云用戶和云服務供應商之間需要進行數(shù)據(jù)

22、交 互，再加上云計算在社會信息化進程中的重要戰(zhàn)略地位，因此云計算安全性也就 顯得格外重要。另外，云計算的安全性不僅是廣大云用戶選擇云計算服務時首要 考慮的因素，而且是云計算產(chǎn)業(yè)實現(xiàn)健康穩(wěn)定和可持續(xù)發(fā)展的基礎(chǔ)。充分考慮云 計算中的安全問題，切實提高云計算的安全性不僅將增強云計算服務供應商自己 的信心，提升云用戶對云計算服務供應商的信賴，促進云計算產(chǎn)業(yè)的成熟和發(fā)展， 還將極大地推動網(wǎng)絡安全領(lǐng)域技術(shù)的發(fā)展及其應用。本論文所研究的課題就是云 計算服務中眾多的安全問題之一。1.1 研究背景與意義可驗證安全云計算外包協(xié)議研究的背景是云計算和外包計算，本節(jié)將對云計 算和外包計算分別進行介紹，并闡明可驗證安全

23、云計算外包協(xié)議研究的意義。1.1.1 云計算云計算是繼分布式計算、網(wǎng)格計算和對等計算之后的一種新興的計算模式。 而云計算中所謂的“云”即是計算機群，其中的每個群又可能包括幾十萬，甚至上百 萬臺計算機。由于云計算具有資源租用、服務外包和應用托管等特點，因而迅速 成為計算機和信息技術(shù)發(fā)展的前沿課題。在云計算已然成為一個大家耳熟能詳?shù)?詞匯的今天，對于云計算的定義，各界始終沒能達成一致意見，不同的機構(gòu)對于 云計算往往有著不同的認識和定義，在這眾說紛“云”的說法中，最典型的兩個定義 如下：美國國家標準與技術(shù)研究院（National Institute of Standards and Technolo

24、gy, NIST）認為：云計算是一個模型，整個模型可以方便地按需訪問一個可配置的計 算資源（如：網(wǎng)絡、存儲設(shè)備、服務器、應用程序，以及個性化服務）的公共集。 公共集中的這些資源可以被快速提供和發(fā)布，同時實現(xiàn)管理成本的最小化或服務 提供商干預的最小化。中國電子學會云計算專家委員會認為：云計算是一種基于互聯(lián)網(wǎng)的大眾參與 的計算模式，其計算資源（包括存儲能力、計算能力、交互能力等）是動態(tài)、可 伸縮、虛擬化的，以服務的方式提供，可以方便地實現(xiàn)分享和交互，并形成群體 智能。雖然不同機構(gòu)對云計算有著不同的理解，但是從以上兩個典型的云計算定義 中可看出：云計算既是一種服務，也是一種技術(shù)，甚至還是一種商業(yè)模式

25、。具體 來說，云計算是一種將池化的機群計算資源通過互聯(lián)網(wǎng)向內(nèi)外部用戶提供按需服 務的 IT 產(chǎn)業(yè)新業(yè)務、新技術(shù)，是傳統(tǒng) IT 領(lǐng)域和通信領(lǐng)域技術(shù)的進步，也是需求推 動與商業(yè)模式轉(zhuǎn)變相輔相成的結(jié)果。即便云計算在概念上不完全統(tǒng)一，其實現(xiàn)方 式亦可各不相同，但是從整體上看，云計算仍具備許多共性：通過應用虛擬化、 分布式處理、在線軟件技術(shù)，將計算、存儲、網(wǎng)絡等基礎(chǔ)設(shè)備及搭建在其上的開 發(fā)平臺、裝有的軟件等抽象為可運營、可管理的資源，然后通過互聯(lián)網(wǎng)為云用戶 提供動態(tài)的按需的個性化服務?？傮w來說，云計算具有以下特征： 以網(wǎng)絡為中心云計算中所含的組件及其整體結(jié)構(gòu)均由網(wǎng)絡連接在一 起，且“云”本身也存在于網(wǎng)絡

26、之中，同時“云”也通過網(wǎng)絡向用戶提供服務。 以服務為提供方式與傳統(tǒng)的一次性買斷有形產(chǎn)品不同，用戶可以根據(jù) 自身的需求從云服務供應商得到多層次個性化的服務；云服務供應商可以從一大 片云中分割出一部分，或者將“云”中的不同組件進行組合，由此塑造出形態(tài)各異的 云以滿足不同云用戶的個性化需求。 資源的池化與透明化對于云服務供應商而言，底層各種資源（如：計 算/存儲/網(wǎng)絡/邏輯資源等）的異構(gòu)性（如果存在某種異構(gòu)性）被屏蔽，邊界被打破，所有資源可以被統(tǒng)一管理、調(diào)度，形成所謂的“資源池”，從而實現(xiàn)為用戶提供按需 的服務；對于用戶而言，這些資源是完全透明的，“資源池”的容量是無限大的，用 戶也無須了解資源池復

27、雜的內(nèi)部結(jié)構(gòu)、具體的實現(xiàn)方法和精確的地理分布，只需 要關(guān)心自己的需求能否得到滿足。 高擴展性與高可靠性高可擴展性使得“云”的規(guī)?？梢詣討B(tài)伸縮，既能 滿足應用和用戶增長的需求，也可以有效避免資源的浪費，節(jié)省“云”的開銷；高可 靠性要求“云”具備較強的容錯容災和數(shù)據(jù)恢復的能力，使得“云”能長久穩(wěn)定的為廣 大用戶提供服務。云計算要實現(xiàn)快速靈活安全高效地滿足海量用戶的不同需求， 必須具有非常先進和十分完善的底層架構(gòu)，因此足夠大的容量，足夠好的伸縮性， 足夠快的業(yè)務響應速度，以及足夠健全的故障冗余機制是云計算體系架構(gòu)中不可 或缺的要素；對商業(yè)化運營來說，靈活的計費系統(tǒng)和層次化的 SLA 也是必不可少 的

28、。 成本低廉 由于“云”具備特殊的容錯容災機制，因此“云”中各個節(jié)點的成本通常比較低廉，且“云”的自動化集中式統(tǒng)一管理使得云用戶不需要負擔數(shù)據(jù)中心高昂的運維成 本，所以不僅云計算自身的單位構(gòu)建成本比傳統(tǒng)高性能計算的單位構(gòu)建成本低， 而且“購買服務，按量計費”的云計算消費模式不僅提高了云用戶的效率，也大大節(jié) 省了云用戶的計算成本。從云計算的定義和特征來看，云計算與傳統(tǒng)的高性能計算是有所不同的，相 比而言，傳統(tǒng)的高性能計算是一種解決高難度計算問題的技術(shù)，而云計算不僅僅 是一種技術(shù)，還是一種商業(yè)模式；傳統(tǒng)的高性能計算通常只為某個或某些機構(gòu)服 務，而云計算卻對內(nèi)/外開放服務于大眾。之所以如此，可以說是

29、技術(shù)革新、需求 推動和服務模式轉(zhuǎn)變?nèi)呔C合作用的結(jié)果。首先，云計算的構(gòu)成主要基于中低端 硬件（如 x86 體系的服務器），其核心技術(shù)在于開放式的架構(gòu)（如：可共享的異 構(gòu)存儲系統(tǒng)、分布式的并行計算平臺、豐富多樣的開源項目、開放式的業(yè)務交互 平臺等），因此云計算能夠提供開放式的服務，適于為大眾服務；其次，云計算 用戶的需求是人們對于低成本、高效率、高可靠性的個性化應用的需求，這種需 求具有普遍性，正是這種需求促使云計算最終落地生根；最后，云計算的商業(yè)模 式的特點在于以網(wǎng)絡為中心和按需付費，這種模式為實現(xiàn)技術(shù)滿足需求開辟出一 條道路，按需付費最終使得云計算能面向全社會推廣開來。云計算也有別于個人終端

30、計算，相比較之下，云計算以其豐富的應用、簡易 的操作、隨時隨地的在線服務和低廉的成本較個人終端計算有著天然和絕對的優(yōu) 勢。另外，云計算的體系架構(gòu)不僅降低了服務的費用，同時也降低了對用戶終端 的要求，用戶終端可以是計算機、智能手機、以及其他智能手持終端，且用戶端使用的操作系統(tǒng)也不再那么重要，只要用戶終端能夠與互聯(lián)網(wǎng)相連，能運行瀏覽 器即可。與此同時，用戶能享有的應用卻得到了極大的豐富，再也不用為了打開 某種格式的文件而安裝一款新的軟件，再也不用頻繁地進行軟件的更新升級，因 此，用戶與云服務供應商之間，用戶與用戶之間的信息共享也將變得更加便捷。分布式應用程序、SOAP、HTTPS、Web 2.0P

31、aaS APISaaSPaaS對于如此強大的云計算，就目前而言，其體系架構(gòu)如圖 1.1 所示，具體來說主 要有三類：Google Docs S Microsoft LiveGoogle: App Engine F Microsoft AzureGoogle:GFS、 BigTable、 MapReduce、Hadoop:HDFS、 HBase、MapReduceAmazon EC2 GoGridVmwar、Xen、Virtual Box、 PowerVM數(shù)據(jù)中心虛擬化計算機存儲器網(wǎng)絡設(shè)備IaaS物理資源云計算層次體系典型應用主要技術(shù)圖 1.1 云計算體系

32、架構(gòu)Fig 1.1 Architecture of cloud computing 基礎(chǔ)設(shè)施即服務（IaaS，Infrastructure as a Service）IaaS 是將計算、存儲、網(wǎng)絡以及搭建環(huán)境所需要的一些工具作為服務提供給 用戶使用，使得用戶能夠按需獲取 IT 基礎(chǔ)設(shè)施。該體系由計算機硬件、網(wǎng)絡、平 臺虛擬環(huán)境、計費規(guī)則、服務協(xié)議等構(gòu)成。其特點包括：把 IT 資源當作服務，基 礎(chǔ)設(shè)施可動態(tài)擴展，計費服務靈活多變，以及多重租賃性等。 平臺即服務（PaaS，Platform as Service）PaaS 是將分布式軟件的開發(fā)、測試以及部署的環(huán)境作為服務，通過互聯(lián)網(wǎng)提 供給用戶使用

33、。PaaS 的構(gòu)建既可以在 IaaS 的虛擬化資源池上，也可以在數(shù)據(jù)中心 的物理基礎(chǔ)設(shè)施之上。與 IaaS 相比，PaaS 可以為用戶提供許多的軟件服務，如中 間件、操作系統(tǒng)、數(shù)據(jù)庫、開發(fā)環(huán)境等，還允許用戶通過網(wǎng)絡遠程完成應用的開 發(fā)、配置和部署，而且部署完的應用最終就在云服務供應商的數(shù)據(jù)中心內(nèi)運行。 軟件即服務（SaaS，Software as a Service）SaaS 是一種利用互聯(lián)網(wǎng)來提供在線軟件服務的應用模式，SaaS 服務供應商通 過瀏覽器將自身服務器端所擁有的應用軟件提供給用戶，供用戶在線使用。SaaS 服務供應商為用戶提供了構(gòu)建信息系統(tǒng)所需的一系列資源和服務，具體包括：搭 建

34、信息系統(tǒng)所需的基礎(chǔ)設(shè)施和軟件運維平臺，系統(tǒng)部署的前期實施、系統(tǒng)運行的 后期維護等；用戶則只需要根據(jù)自身的實際需求，向 SaaS 服務供應商租賃相應服 務，即可利用互聯(lián)網(wǎng)使用信息系統(tǒng)，其最大的好處在于用戶因此可省去購買軟硬 件、建設(shè)機房、招聘 IT 人員等一系列耗時耗資的工作。SaaS 的特點包括：多重租 賃、個性化定制、靈活可擴展、價廉質(zhì)優(yōu)、在線工作，以及可配置等。1.1.2 外包計算所謂外包，是商業(yè)競爭隨著社會的發(fā)展而變得日漸激烈，以致企業(yè)為了能夠 在提高自己核心競爭力的同時盡可能的節(jié)省自身成本而產(chǎn)生的一種合作經(jīng)營方 式，在這種方式下，企業(yè)可將自身的非核心業(yè)務以合同業(yè)務管理或委托的方式交 給

35、其它企業(yè)代為完成。相比之下，外包計算就是將這種經(jīng)營模式移植到任務計算 領(lǐng)域而產(chǎn)生的。具體來說，外包計算的原理為：計算能力有限的用戶通過支付相 應的費用給第三方，將自身難以完成的計算任務經(jīng)由網(wǎng)絡委托給擁有海量計算資 源和強大計算能力的第三方來完成計算，用戶最終從第三方獲取任務的計算結(jié)果。 由此可見，外包計算是一種基于資源共享和多方交互的，具備即買即用特征的新 型計算模式。1.1.3 安全云計算外包協(xié)議從前面兩節(jié)對云計算和外包計算的介紹中可以看出，用戶享用云服務供應商 的各種服務其實質(zhì)就是將自己的需求外包給云服務供應商來實現(xiàn)。當用戶從云服 務供應商處享有計算服務時，其過程可簡單描述為：云用戶將自己

36、的計算任務信 息通過網(wǎng)絡發(fā)送給云服務供應商，云服務供應商在接收并明確任務要求后調(diào)度相 應的計算資源完成計算任務，計算完成后，云服務供應商將任務的計算結(jié)果通過 網(wǎng)絡返回給委托此任務的用戶。而本論文所研究的課題便是用戶從云服務供應商 處享有計算服務時的一些安全問題。云計算中安全問題的覆蓋面極廣，總體來說可以分為兩大類：云服務供應商 角度的安全和云用戶角度的安全。站在云服務供應商的角度分析，它所面臨的安 全風險主要有以下兩個方面： 服務可用性風險 由于在云計算服務中，用戶的數(shù)據(jù)和業(yè)務應用的數(shù)據(jù)均位于云計算的數(shù)據(jù)中心，當系統(tǒng)發(fā)生故障時，如何快速恢復用戶和業(yè)務應用的數(shù)據(jù)是云計算安全中的 一個重要問題，而

37、且由于云計算服務供應商服務面廣，因此云計算系統(tǒng)中集中存有海量數(shù)據(jù)，以致云計算中心容易成為各類黑客攻擊的目標。 用戶信息濫用與泄露風險 用戶在享用云計算服務時，用戶信息的存儲、處理和傳輸?shù)榷寂c云計算系統(tǒng)相關(guān)。如果云計算系統(tǒng)中發(fā)生用戶關(guān)鍵信息或隱私信息的丟失、竊取，那么不僅 對用戶來說是致命的，對于云服務供應商在業(yè)界的信譽損害也是巨大的，因此如 何確保云服務供應商內(nèi)部的訪問控制和安全管理機制能滿足客戶的安全要求，如 何實現(xiàn)有效的安全審計，如何實現(xiàn)對數(shù)據(jù)操作的安全監(jiān)管，如何有效避免云計算 系統(tǒng)中多用戶共存所帶來的潛在風險，都將是云計算系統(tǒng)所面臨的安全挑戰(zhàn)。站在用戶的角度，從云服務供應商處購買服務時，

38、用戶擔心的安全問題通常 有兩個： 個人隱私信息被泄露或利用 用戶在與云服務供應商進行交互時，難免需要將自己的一些重要（如用戶資料中的隱私信息、信息服務中的一些敏感信息）信息告知云服務供應商，因此這 些信息在云計算系統(tǒng)中可能被其它用戶竊取，或者云服務供應商試圖從這些信息 中綜合分析出用戶的其它信息，甚至云服務供應商為了謀取自身更多的利益，將 用戶的這些關(guān)鍵信息出售給其它機構(gòu)。 享有服務的質(zhì)量得不到保障 雖然云服務端具備較為健全的容錯容災機制，但是仍不能完全保證系統(tǒng)不出現(xiàn)故障或錯誤，如果故障或錯誤發(fā)生，且云計算系統(tǒng)并未檢測到這一事件，將致 使用戶購買的服務在錯誤的基礎(chǔ)上繼續(xù)進行，最終使得用戶蒙受經(jīng)

39、濟損失。此外， 云服務供應商作為一個商業(yè)機構(gòu)，追求利益的最大化自然是其運營的根本宗旨， 在此宗旨的驅(qū)動下，云服務供應商可能為了節(jié)省自己的成本，不誠信的完成用戶 委托的任務，進而返回用戶一個任意的處理結(jié)果。因此，為了更進一步保護用戶信息的安全，避免用戶因為云服務端的故障或 不誠信的服務而蒙受巨大損失，針對用戶的實際需求，設(shè)計一個可驗證的安全云 計算外包協(xié)議顯得尤為重要。在協(xié)議中，通常將用戶的任務信息經(jīng)加密后再告知 給云服務供應商，然后云服務供應商完成對加密后任務的處理并將處理結(jié)果返回 給用戶，用戶收到云服務供應商返回的結(jié)果后，先將此結(jié)果解密，然后驗證解密 后結(jié)果的正確性。通過加密，進一步保護用戶

40、信息的安全；通過結(jié)果驗證，使用 戶達到識別云服務供應商的一些不端行為，避免自身損失的目的。1.2 外包計算技術(shù)研究現(xiàn)狀由于用戶的實際需求有千萬種，很難用一項技術(shù)或一個方案來解決所有任務 的安全云計算外包問題，因此在研究中通常針對一類問題，采用適合的加密方法設(shè)計一個相應的安全外包方案。到目前，國內(nèi)外學者針對不同的實際問題，采用 多種多樣的方法，提出了很多的具體可行的外包方案。下面按照外包所針對的具 體內(nèi)容分類，依次簡單介紹目前在各個領(lǐng)域所取得的外包技術(shù)成果。線性與非線性問題的外包技術(shù)。此處的線性與非線性問題主要包含線性方程 組求解問題、線性規(guī)劃問題和非線性規(guī)劃問題。2011 年，Wang1等針對

41、大規(guī)模的 線性方程組求解問題提出了一個單云模型下的可驗證安全云計算外包方案。同樣 在 2011 年，Wang2等針對線性規(guī)劃問題提出一個切實可行的可驗證安全云計算外 包方案。對于非線性規(guī)劃問題，Bhavsingh3等和 Madhura4等設(shè)計出一個安全云計 算外包方案。模冪運算外包技術(shù)是當前外包技術(shù)研究中最熱門的話題。Hohenberger5等利 用兩個不可信但互不通信的加密輔助程序U1 和U 2 ，對底數(shù)和指數(shù)均任意的模冪運 算提出一個可驗證的安全外包計算方案，在該方案中，利用 Cramer-Shoup 加密方法6將底數(shù)和指數(shù)對U 和U 隱藏起來，同時U 和U 互不通信的前提條件更進一121

42、2步保證了數(shù)據(jù)的隱私性；Ma7等針對底數(shù)固定指數(shù)變化和指數(shù)固定底數(shù)變化這兩 種情形的模冪運算，分別設(shè)計了一個同形式（同一底數(shù)或同一指數(shù)情形）模冪運 算的批量安全云計算外包方案，此協(xié)議在理論上確保了外包的安全性和效率，但 是缺少結(jié)果正確性驗證部分，即協(xié)議不具有可驗證性；這一不足在 Liu8等提出的 復合模冪運算的可驗證安全云計算外包方案中到了解決，該方案中包含了兩個子 協(xié)議，子協(xié)議一描述了單個模冪運算的可驗證安全云計算外包方案，而子協(xié)議二 則是在子協(xié)議一的基礎(chǔ)上實現(xiàn)了復合模冪運算（冪運算中的底數(shù)和指數(shù)均可任意） 的批量可驗證安全云計算外包；2014 年 Chen9等又提出了一個新的基于雙云模型

43、的模冪運算可驗證安全云計算外包方案，此方案與過去的方案相比，在確保安全 的同時，具有更好的結(jié)果校驗機制，而且能達到更高的效率。關(guān)于矩陣運算安全外包的研究。早在 1996 年，Atallah10等就矩陣乘法（包括 方陣相乘和非方陣相乘）、矩陣求逆運算，分別提出了基于隨機置換和隱藏維數(shù) 這兩種加密方法的外包方案，只不過對于每種計算，相應方案均沒有結(jié)果驗證環(huán) 節(jié)；Lei11等提出一個矩陣求逆運算的可驗證安全云計算外包協(xié)議，協(xié)議中利用克 羅內(nèi)克（Kornecker）函數(shù)和隨機置換巧妙構(gòu)造密鑰矩陣并完成加密，利用蒙特卡 洛（Monte Carlo）驗證算法驗證計算結(jié)果的正確性，以此將加密和結(jié)果驗證環(huán)節(jié)

44、的復雜度均降低到 O(n2 ) ；Hu12等利用盲化技術(shù)，為矩陣乘積、矩陣行列式、矩陣求逆分別設(shè)計了一個切實可行的安全可驗證云計算外包協(xié)議。Ren13等也提出一 個矩陣行列式安全外包協(xié)議，與文獻12的方案相比，該方案將待外包矩陣作為一 個整體加密后外包給云服務供應商計算，而文獻12的方案則先根據(jù)行列式按行（列）展開的法則將待外包矩陣分解成多個矩陣后分別加密，再將加密后的多個矩陣外包給云服務供應商計算。另外，Zhang14等也提出一個矩陣乘法的可驗證安 全云計算外包協(xié)議，但所用的加密方法和驗證方法與文獻12中的不一樣。序列比較外包技術(shù)研究方面，Atallah15等利用序列分割技術(shù)和序列長度隱藏

45、技術(shù)，提出一個安全的序列比較外包方案；Feng16等利用編輯路徑變換技術(shù)，以 及加密布爾電路和同態(tài)加密理論的融合，提出一個新的序列比較可驗證安全外包 方案。在生物計算領(lǐng)域亦有許多序列比較類問題，因此外包計算和生物計算相結(jié) 合，產(chǎn)生出了許多新的應用，如基于網(wǎng)格環(huán)境的序列匹配1718、基于有限自動機 的 DNA 搜索安全外包方案19，以及利用海明距離統(tǒng)計法驗證結(jié)果正確性的大規(guī)模 生物計算外包方案20等。除此之外，外包技術(shù)在其它領(lǐng)域也有一定的應用，如在圖像處理方面有法醫(yī) 圖像識別21、圖像重建22、圖像形狀特征提取23，科學計算24，多方計算25,加密 布爾電路評估26，同態(tài)函數(shù)反轉(zhuǎn)27，最短距離問

46、題28等。1.3 主要貢獻及內(nèi)容安排本論文的主要貢獻在于：1）對方陣冪計算問題的傳統(tǒng)解法進行了歸納總結(jié)； 2）針對實際應用中常常面臨的大維數(shù)方陣的高次冪計算問題，設(shè)計出相應的可驗 證安全云計算外包方案；3）對所設(shè)計的外包方案在正確性、安全性、可驗證性和 效率方面分別進行了深入的分析；4）對提出的外包方案進行了實驗仿真，以實際 的仿真結(jié)果證明此方案的可行性，并評估其實際性能。本論文的安排如下：第 1 章為緒論，主要介紹了云計算、外包計算和外包計 算的概念，闡述了設(shè)計安全外包計算方案的意義，以及目前安全外包技術(shù)的研究 現(xiàn)狀；第 2 章是研究相關(guān)基礎(chǔ)知識回顧，主要包括方陣冪、克羅內(nèi)克函數(shù)的概念， 隨

47、機置換的概念和構(gòu)造算法，可逆方陣及其逆矩陣的構(gòu)造算法，方陣冪的計算算 法，以及幾個結(jié)論的證明；第 3 章對方陣冪的傳統(tǒng)求解方法進行了總結(jié)；第 4 章 具體介紹了方陣冪可驗證安全外包云計算方案的具體內(nèi)容，包括基于單云/雙云模 型的可驗證安全外包協(xié)議的內(nèi)容和對每個協(xié)議的正確性、安全性、可驗證性、效 率的理論分析；第 5 章展示了外包方案所包括的兩個協(xié)議的仿真實驗結(jié)果，并對 每個協(xié)議的結(jié)果加以分析；之后依次是本論文的總結(jié)與展望、致謝和參考文獻； 最后是附錄 A，為本人在碩士研究生期間所發(fā)表的論文列表。2 基礎(chǔ)知識介紹2.1 研究涉及的相關(guān)概念本節(jié)主要回顧了方陣冪外包方案研究中所涉及的概念，具體包括方

48、陣、方陣 冪、克羅內(nèi)克函數(shù)和隨機置換。下面對這些概念依次作簡單的介紹。2.1.1 方陣與方陣冪 什么是方陣 在了解什么是方陣之前，先了解什么是矩陣。根據(jù)線性代數(shù)29中所述，矩陣的定義如下：定義 2.1 由 m n 個數(shù) aij (i = 1, 2, m; j = 1, 2,n) 排成的 m 行 n 列的數(shù)表a11a12a1n A = a21a22a2n （2.1）am1am 2amn 稱為 m 行 n 列矩陣 A ，簡稱 m n 矩陣 A ，記作 Amn 。 因此方陣可定義為：定義 2.2 行數(shù)與列數(shù)都等于 n 的矩陣 A 稱為 n 階矩陣 A 或 n 階方陣 A 。n 階方 陣 A 也記作

49、An 。 什么是方陣冪定義 2.3 若矩陣 A 為 n 階方陣，那么 m 個方陣 A 相乘則稱為 n 階方陣 A 的 mAAAm個次冪，記作 Am 。即：Am =（2.2）2.1.2 克羅內(nèi)克函數(shù)克羅內(nèi)克函數(shù)得名于德國數(shù)學家利奧波德克羅內(nèi)克。根據(jù)維基百科30中所述，克羅內(nèi)克函數(shù)的自變量（輸入值）一般是兩個整數(shù)，如果兩者相等，則其輸 出值為 1，否則為 0?？肆_內(nèi)克函數(shù)一般簡寫為d x, y ，因此該函數(shù)亦可描述為：d=1,x, y0,x = y x y（2.3）2.1.3 隨機置換置換代表的是一種映射關(guān)系。設(shè) S = 1, 2, n -1, n，s 是 S 上的一個置換，即意味著s 是 S 到

50、自身的一一映射。映射關(guān)系隨機的置換稱為隨機置換。隨機置 換在組合數(shù)學31和群論32中均有廣泛的研究。采用柯西（Cauchy）的兩行表示法，n pn 第一行列出置換下的原像，第二行列出置換下的像，則 S 上的隨機置換 p 可以表 示為：p = 12（2.4） p1 p2n n 其中：令 p (i) = pi (i = 1, 2,n) ，表示 i 在 p 下的像為 pi 。當滿足 p (i) = i 時，此 時的置換稱為恒等置換，記作 I ，即：1 2I = 1 2（2.5）2.2 可驗證安全云計算外包模型可驗證安全云計算外包模型通常分為單云可驗證安全云計算外包模型（以下 簡稱單云外包模型）、雙云

51、可驗證安全云計算外包模型（以下簡稱雙云外包模型）， 以及多云可驗證安全云計算外包模（簡稱多云外包模型）型三種，它們的主要區(qū) 別在于外包計算的過程中，用戶所交互的云服務端的數(shù)目不同。由于多云外包模 型與雙云外包模型廣義上來講屬于同類，因此本論文的研究主要針對單云外包模 型和雙云外包模型。下面依次介紹單云和雙云外包模型的具體構(gòu)成和相應的外包 計算工作流程。2.2.1 單云外包模型密鑰發(fā)生器加密發(fā)生于密鑰K密鑰K解密 & 驗證原任務T加密后任務ET任務處理云服務端云用戶原任務結(jié)果R處理結(jié)果ER圖 2.1 單云外包模型Fig 2.1 Outsourcing model of single cloud單

52、云外包模型如圖 2.1 所示。模型的主體由云用戶實體（包括各類手機、電腦 等智能終端）和云計算服務端構(gòu)成。單云外包模型中的云服務端只有一個，即在 每次的外包云計算中，用戶只與一個云服務端進行交互，但每次外包計算時用戶 可以選擇不同的云服務端。單云外包模型下，用戶將自身任務外包給云服務端完成的具體流程為： 用戶在本地利用私有密鑰 K 將需要外包的計算任務T 進行加密，得到加密 后的任務 ET ； 用戶將加密后的任務 ET 經(jīng)由網(wǎng)絡發(fā)送給云服務端； 云服務端接收到用戶發(fā)送的任務 ET 并明確任務需求后，調(diào)度相應資源， 完成對任務 ET 的處理，得到相應的處理結(jié)果 ER ； 云服務端將處理結(jié)果 ER

53、 通過網(wǎng)絡返回給用戶； 用戶接收到云服務端返回的處理結(jié)果 ER 后，利用私有密鑰 K 對 ER 進行解 密，得到解密后的結(jié)果 R ； 用戶驗證 R 的正確性，若正確則接受云服務端返回的結(jié)果 ER ，且原任務T的正確結(jié)果即為 R ，否則拒絕服務端返回的結(jié)果 ER 。2.2.2 雙云外包模型 密鑰發(fā)生器加密密鑰Ki密鑰Ki解密&驗證原任務T加密后任務ETi發(fā)生于CS1CS2原任務結(jié)果R處理結(jié)果ERi圖 2.2 雙云外包模型Fig 2.2 Outsourcing model of double cloud雙云外包模型如圖 2.2 所示。模型中的主體為云用戶實體和兩個不同的云服務 端 CS1 和 CS

54、2 ?；诖四Ｐ偷耐獍朴嬎阒?，用戶每次進行外包計算時，需要同時 與 CS1 和 CS2 進行交互，但每次外包計算前，用戶可以重新選擇兩個不同的云服務端。雙云外包模型下，用戶將自身任務外包給云服務端完成的具體流程如下： 用戶在本地利用私有密鑰 Ki 將需要外包的計算任務T 進行加密，得到相應 的加密后的任務 ETi ； 用戶將加密后的任務 ETi 經(jīng)由網(wǎng)絡分發(fā)給云服務端 CSi ； 云服務端 CSi 接收到用戶發(fā)送的任務 ETi 后，調(diào)用相應的資源，完成對任務ETi 的處理，得到相應的處理結(jié)果 ERi ； 云服務端 CSi 將處理結(jié)果 ERi 通過網(wǎng)絡返回給用戶； 用戶接收到云服務端返回的處理

55、結(jié)果 ERi 后，利用私有密鑰 Ki 對 ERi 進行 解密，得到解密后的結(jié)果 Ri ； 用戶驗證結(jié)果的正確性。若解密所得 Ri 相等，則表明各個云服務端返回的 結(jié)果正確，此時用戶接受各個云服務端返回的結(jié)果 ERi ，且原任務T 的正確結(jié)果即 為 R ，其中 R = Ri ；否則用戶拒絕云服務端返回的結(jié)果 ERi 。2.3 可驗證安全云計算外包協(xié)議構(gòu)成由單云外包模型和雙云外包模型下的可驗證安全云計算外包流程可知，無論是 單云還是雙云模型下，可驗證安全云計算外包協(xié)議均可由五部分構(gòu)成。它們分別 是：密鑰產(chǎn)生、任務加密、任務處理、結(jié)果解密和結(jié)果驗證。其中每一部分的主 要工作如下： 密鑰產(chǎn)生。通過秘鑰發(fā)生器，產(chǎn)生用來加密原始任務的密鑰（該密鑰通常 為用戶私有）； 任務加密。用戶利用自己產(chǎn)生的私有密鑰，在本地完成對原始任務的加密 工作，并得到加密后的任務； 任務處理。云服務端接收到用戶委托的任務之后，調(diào)用相關(guān)資源，按用戶 要求完成對任務的處理，得到相應的處理結(jié)果； 結(jié)果解密。用戶接收到云服務端返回的任務處理結(jié)果后，利用手持的私有 密鑰，對處理結(jié)果進行解密，得到解密后的結(jié)果； 結(jié)果驗證。用戶根據(jù)與任務和外包環(huán)境相適應的結(jié)果驗證算法，完成對解 密結(jié)果正確性的驗證。以上五個組成部分中，除了任務處理是由云服務端完成外，其余均由用戶自 身完成。2.4 可驗