淺析基于可驗證計算的可信云計算優(yōu)秀論文

1 引 言

　　云計算作為一種新興的網(wǎng)絡(luò)計算商業(yè)服務(wù)模式，使得用戶可以隨時在遠(yuǎn)端的云服務(wù)器存儲數(shù)據(jù)和運行程序.但這種新興的計算模式在給用戶帶來諸多便利性的同時，也帶來了一些新的安全挑戰(zhàn).用戶可能擔(dān)心云計算平臺本身的安全性，比如云平臺漏洞和錯誤配置、管理員的惡意行為等等，而這都可能直接導(dǎo)致用戶數(shù)據(jù)的完整性和隱私性受到危害，導(dǎo)致用戶應(yīng)用程序無法正確執(zhí)行.這就產(chǎn)生了一個問題：用戶如何相信云提供商執(zhí)行的程序結(jié)果是正確的?如何確保存儲在遠(yuǎn)端的數(shù)據(jù)的完整性和私密性?檢測遠(yuǎn)程服務(wù)器返回的結(jié)果是否正確的傳統(tǒng)解決方案有以下幾種：

　　(1)采用審計的方法，即隨機選取服務(wù)器執(zhí)行的一小部分程序進行驗證，這就可能發(fā)生錯誤執(zhí)行的程序沒有被服務(wù)器驗證的情況，所以說這種方法必須假設(shè)錯誤執(zhí)行的程序的發(fā)生頻率是很小的;

　　(2)利用可信硬件和遠(yuǎn)程證明來保證遠(yuǎn)程服務(wù)器運行的程序是正確的，但是這種方法必須假設(shè)云提供商是完全可信的，由于硬件基礎(chǔ)設(shè)施是在云提供商的控制之下，如果云提供商內(nèi)部人員惡意控制了可信硬件(如CPU、TPM)，就無法保障云提供商運行的程序的機密性和可驗證性.而且還需要假設(shè)存在一個可信鏈，而運行時可信鏈的建立在可信計算領(lǐng)域依然是一個難題.事實上，在實際的云計算應(yīng)用場景中這兩個假設(shè)通常是無法滿足的.在云計算場景中，用戶無法完全相信云提供商，即使用戶出于聲譽的考慮相信云提供商本身，也無法相信其內(nèi)部管理人員;

　　(3)采用冗余計算的方法，用戶可以讓多個遠(yuǎn)程服務(wù)器把相同的程序執(zhí)行多次，然后檢測他們返回的結(jié)果是否一致.但這在云計算中也是行不通的，云計算中的軟硬件平臺配置通常是相同的，而這違背了冗余計算中錯誤必須是不相關(guān)的假設(shè)，且遠(yuǎn)程服務(wù)器很容易竄通，合謀返回一個錯誤的程序執(zhí)行結(jié)果.

　　而可證明數(shù)據(jù)持有(Provable Data Possession，PDP)方法和可恢復(fù)證明(Proof of Retrievability，POR)方法可以用來確保存儲在遠(yuǎn)端的數(shù)據(jù)的完整性，避免云提供商刪除和篡改數(shù)據(jù).相比PDP方法，POR除了能確保數(shù)據(jù)的完整性之外，還能確保數(shù)據(jù)的可恢復(fù)性，但是PDP和POR無法確保在云提供商端執(zhí)行的程序的正確性.另一方面，基于復(fù)雜性理論的交互式證明系統(tǒng)(Interactive Proof system，IPs)和概率可驗證證明系統(tǒng)(Probabilistically Checkable Proof system，PCPs)以及密碼學(xué)理論構(gòu)造的可驗證計算協(xié)議能以很高的正確率檢測出遠(yuǎn)程服務(wù)器返回的程序執(zhí)行結(jié)果是否正確并且不需要對遠(yuǎn)程服務(wù)器(云提供商)做任何假設(shè).可驗證計算協(xié)議致力于設(shè)計驗證者與證明者之間的協(xié)議，協(xié)議允許在計算能力上相對較弱的驗證者(如云計算中的用戶)將其程序發(fā)送到一個計算能力強大的，但不可信的證明者(例如云提供商)，并要求證明者執(zhí)行其發(fā)送的程序.所設(shè)計的協(xié)議應(yīng)確保證明者不但返回程序的執(zhí)行結(jié)果給驗證者，并且使得驗證者相信這個程序執(zhí)行結(jié)果是正確的.其主要目標(biāo)是使得服務(wù)器在發(fā)送程序執(zhí)行結(jié)果的同時提供程序正確執(zhí)行的證據(jù)，而用戶驗證證據(jù)的過程必須要比用戶自己執(zhí)行程序的開銷小(當(dāng)然有時由于資源比如存儲的限制，用戶根本無法自己執(zhí)行程序，在這種情況下是指和假設(shè)用戶有足夠的資源執(zhí)行程序時的開銷相比要小)。

　　2 問題描述和協(xié)議設(shè)計原則問題描述：

　　驗證者V把程序f和輸入變量x發(fā)送給證明者P，P計算f(x)，并把f(x)賦值給變量y，返回y給V，然后V 和P 以如下方式進行交互：

　　(1)如果y=f(x)，那么P 應(yīng)該能向V 證明y的正確性，即使得V 接受y.其中，證明可以通過回答V 提出的一些問題完成，也可以通過給V 提供一個證書完成.

　　(2)如果y≠f(x)，V 能以很高的概率拒絕接受y.可驗證計算協(xié)議的設(shè)計必須滿足3個基本原則：(1)協(xié)議應(yīng)該使得驗證者的開銷比其在本地執(zhí)行程序f(x)的開銷要低，但可以允許證明者為達(dá)到協(xié)議的目標(biāo)產(chǎn)生合理的開銷，因為提供運行程序的正確性保障本身就需要用戶付出一定的代價，在云計算實際場景中，表現(xiàn)為云提供商可能會對需要提供程序正確執(zhí)行證據(jù)的用戶收取額外的費用;

　　(2)不能假設(shè)證明者完全遵守協(xié)議，也就是說證明者可能是惡意的，這和云計算中不能假設(shè)云提供商是完全可信的實際場景也是十分吻合的;

　　(3)f 應(yīng)該是通用程序，然而在具體的協(xié)議設(shè)計中，可能需要對f 表示的程序做一些假設(shè)，從而通過限制可驗證計算協(xié)議適用的應(yīng)用程序種類使得協(xié)議的性能達(dá)到實際應(yīng)用場景的要求，但是可驗證計算協(xié)議的設(shè)計原則依然是盡量能表示通用程序.

　　通常的安全保障工具比如說病毒檢測關(guān)注的都是不正確的行為的識別和防范，可驗證計算協(xié)議則有所不同，其不關(guān)心證明者可能的不正確行為，比如犯了什么錯誤，出現(xiàn)了什么故障等等，而只關(guān)心其執(zhí)行程序的結(jié)果是否是正確的，卻無法推測程序錯誤執(zhí)行的原因.這和云計算中用戶對于程序執(zhí)行的要求也是相符的.

　　3 協(xié)議流程和關(guān)鍵

　　3.1 可驗證計算協(xié)議流程

　　可驗證計算協(xié)議的流程主要包括編譯處理和證明系統(tǒng)，具體流程如圖1所示.首先是編譯處理階段，驗證者V 和證明者P 將高級語言(比如C 語言)編寫的程序轉(zhuǎn)換成一組布爾電路集(根據(jù)協(xié)議的不同，也可以是其他計算模型比如算術(shù)電路集或者約束集等).接下來，P 和V 進行一系列協(xié)議交互，不失一般性，這里用布爾電路集C表示程序f.V 把輸入變量x傳輸給P，P 計算C，輸出程序執(zhí)行結(jié)果y和C正確執(zhí)行的一組軌跡{C，x，y｝給V，{C，x，y｝也稱為C的一個可滿足性賦值z.其中，C正確執(zhí)行的一組軌跡是指C的輸入線路被賦值為x，輸出線路被賦值為f(x)時，電路集中所有電路門的賦值集合.在程序執(zhí)行的過程中，證明者P 獲得了正確計算電路的執(zhí)行軌跡{C，x，y｝.如果P 聲稱的輸出y是不正確的，即y不等于f(x)，那么對于{C，x，y｝，就不可能存在一個有效的執(zhí)行軌跡(電路C正確計算的一個證明).因此，如果P 能夠?qū)C，x，y｝構(gòu)建一個有效的執(zhí)行軌跡，那么就一定能使得驗證者V 相信它返回的結(jié)果是正確的.顯然，電路正確計算過程中的各個門的賦值本身就能說明存在有效的執(zhí)行軌跡.但是，如果需要V 依次驗證所有電路門在計算電路過程中的值，進而確定程序是否正確執(zhí)行，這個工作量和V 本地執(zhí)行f 是相當(dāng)?shù)模@就違背了可驗證計算協(xié)議設(shè)計的基本原則.所以，圖中第步就需要證明者對程序執(zhí)行軌跡編碼，生成一個很長的字符串，并使得不同的執(zhí)行軌跡生成的編碼在所有不同的位置的取值是不相同的.這樣，驗證者就可以通過檢查隨機選擇的編碼的特定的位置的取值，來驗證執(zhí)行軌跡的有效性，進而對返回的結(jié)果采取特定的測試來確定證明者返回的結(jié)果是否正確.

　　3.2 可驗證計算協(xié)議的理論依據(jù)

　　理解可驗證計算協(xié)議的原理和流程關(guān)鍵在于理解兩個等價關(guān)系，如3.1節(jié)所述，可驗證計算協(xié)議的流程主要包括編譯處理和證明系統(tǒng).其中，編譯處理階段，編譯器完成高級語言程序到電路集或者約束集(可以看做方程組)等計算模型的轉(zhuǎn)化，其實現(xiàn)的理論依據(jù)在于等價關(guān)系：程序執(zhí)行的正確性等價于電路集或者約束集可滿足問題.