方陣冪可驗(yàn)證安全云計(jì)算外包方案研究

1、方陣冪可驗(yàn)證安全云計(jì)算外包方案研究重慶大學(xué)碩士學(xué)位論文（學(xué)術(shù)學(xué)位）學(xué)生姓名：劉午陽(yáng) 指導(dǎo)教師：廖曉峰教 授 專(zhuān)業(yè)：計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 學(xué)科門(mén)類(lèi)：工學(xué)重慶大學(xué)計(jì)算機(jī)學(xué)院二 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摘要為了解決計(jì)算能力有限的對(duì)象（用戶(hù)）所面臨的大維數(shù)方陣的高次冪計(jì)算問(wèn)題， 作者利用云計(jì)算平臺(tái)（云服務(wù)端），提出了一個(gè)方陣冪可驗(yàn)證安全云計(jì)算外包方 案。該方案中包含兩個(gè)不同的云計(jì)算外包協(xié)議，它們分別是基于單云外包模型的 方陣冪可驗(yàn)證安全云計(jì)算外包協(xié)議（S-S

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

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

5、每種情形下計(jì)算方陣冪時(shí)又分別采用了定義法和二分法 這兩種不同的方法。實(shí)驗(yàn)結(jié)果表明，與用戶(hù)自身完成原方陣冪計(jì)算任務(wù)相比，以 上兩種形式的方陣冪在不同的云計(jì)算外包方式下均能大幅減少用戶(hù)的計(jì)算耗時(shí)， 獲得較好的外包性能，且除了方陣階數(shù)固定指數(shù)變化型方陣冪在單云外包模型二 分法情形以外，其它情形下的云計(jì)算外包性能均隨著方陣維數(shù)和指數(shù)的增加而提 高。關(guān)鍵詞：方陣冪，云計(jì)算，安全外包計(jì)算，可驗(yàn)證，隨機(jī)置換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 云計(jì)算21.1.2 外包計(jì)算51.1.3 安全云計(jì)算外包協(xié)議51.2 外包計(jì)算技術(shù)研究現(xiàn)狀

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

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

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

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

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

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

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

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

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

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

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

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

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

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

31、aaS APISaaSPaaS對(duì)于如此強(qiáng)大的云計(jì)算，就目前而言，其體系架構(gòu)如圖 1.1 所示，具體來(lái)說(shuō)主 要有三類(lèi)：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ù)中心虛擬化計(jì)算機(jī)存儲(chǔ)器網(wǎng)絡(luò)設(shè)備IaaS物理資源云計(jì)算層次體系典型應(yīng)用主要技術(shù)圖 1.1 云計(jì)算體系

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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