全同態(tài)加密的相關算法研究.pdf

1、伴隨網絡技術研究和信息社會的發(fā)展，云計算、委托計算等新興計算模式得到了廣泛應用。在這些計算模式中，個人或企業(yè)（客戶）將自有數(shù)據(jù)交付給數(shù)據(jù)處理服務供應商，由供應商完成客戶所要求的數(shù)據(jù)處理任務。這些計算模式極大提升了客戶對信息數(shù)據(jù)的處理能力，有效降低客戶在信息基礎設施上的投資。但是云計算、委托計算的應用也面臨一個很重要的挑戰(zhàn)，即如何在信息數(shù)據(jù)處理中確?？蛻魯?shù)據(jù)的隱私。作為數(shù)據(jù)隱私保護的重要手段，傳統(tǒng)加密體制因為受限于加密后得到的密文，無法進

2、一步處理，使得傳統(tǒng)加密體制無法應用到云計算、委托計算中。如何能夠在云計算、委托計算等新興計算模式中有效保護數(shù)據(jù)安全，已經成為一個迫切的現(xiàn)實需求。
　　全同態(tài)加密是指經同態(tài)加密所得到的密文，在不經解密的前提下，任何一方都可以對密文進行處理，且滿足密文緊致性要求。加密方案的同態(tài)性是指，對密文執(zhí)行的計算任務等同于對相應明文執(zhí)行相同的計算任務。這一特性使得全同態(tài)加密在云計算、委托計算等諸多領域有著良好的應用前景，越來越多的學者投入到其理論

3、和應用的研究中。全同態(tài)加密方案的構造方法不斷更新，陸續(xù)出現(xiàn)了多個優(yōu)化方案，算法效率有了一定的提升。但是現(xiàn)有全同態(tài)加密方案多存在密鑰生成算法復雜度過高，密鑰規(guī)模過大，批處理方案受限于比特明文空間等問題，上述問題的存在使得全同態(tài)加密在實際應用上面臨嚴峻挑戰(zhàn)。如何構造更加高效、具備實用性的全同態(tài)加密方案，成為當前全同態(tài)加密研究的重點。
　　本論文從密鑰算法構造、提升算法效率、明文空間擴展等角度對全同態(tài)加密進行了深入研究，提出了快速密鑰生

4、成算法、高效整數(shù)同態(tài)加密方案和基于整數(shù)明文空間的批處理同態(tài)加密方案，并和相關的工作進行了比較。本論文主要包括以下幾個貢獻:
　　1.密鑰生成算法的改進。就目前來看，Gentry類型全同態(tài)加密方案，特別是其密鑰生成算法的復雜度過高。在該類型的全同態(tài)加密方案中，早先的密鑰生成算法的思想是:隨機生成理想格的一個格基作為私鑰，并要求所生成的格基滿足預先定義的代數(shù)要求，為得到私鑰需要多次執(zhí)行密鑰生成算法?，F(xiàn)有的全同態(tài)加密算法的密鑰生成算法因

5、其過高的計算復雜度，距離實際應用尚有一定距離。針對這一問題，提出了一種新的構造思路:在密鑰生成之前，預先確定方案同態(tài)電路的乘法深度，利用同態(tài)電路乘法深度和私鑰格基特征值的數(shù)值關系確定特征值的取值范圍。隨后依據(jù)特征值的取值范圍，利用蓋爾圓定理生成私鑰格基，并將得到的格基作為私鑰，求取該格基的HNF作為方案的公鑰。密鑰生成算法不是預先隨機生成格基，而是依據(jù)預先確定的電路深度來求取密鑰，取代了以往方案中生成私鑰格多采用隨機生成然后再去驗證的思

6、路，有效提升了密鑰生成算法效率。
　　2.提升算法效率?；谡麛?shù)的全同態(tài)加密方案，該類型方案所存在的問題在于其過大的公鑰規(guī)模、密文規(guī)模，計算復雜度過高?；谡麛?shù)環(huán)這一簡單的代數(shù)結構，本文提出了一個高效同態(tài)加密方案。首先構造一個私鑰同態(tài)加密方案。隨后提出了一個密文清洗程序，該程序以新鮮密文作為輸入，輸出對同一明文加密的密文，該密文稱為清洗密文。清洗密文所含噪聲相比較新鮮密文的噪聲更小，可支持對該密文做更多的同態(tài)計算，增加了方案的同態(tài)

7、計算能力。在不影響安全性和計算效率的前提下，將私鑰同態(tài)加密方案轉換成一個公鑰同態(tài)加密方案。和之前的相關工作相比，所構造方案的公鑰規(guī)模、密文規(guī)模均得到了較大降低，有效提升了算法效率。所提方案為一個部分同態(tài)加密方案，從實際應用角度看，部分同態(tài)加密方案算法復雜度低，可以滿足絕大多數(shù)應用場景。
　　3.擴展明文空間，降低密文膨脹率。密文膨脹率過大也是當前全同態(tài)加密方案存在的一個問題，這使得密文在通過網絡傳輸時占用大的帶寬，限制了全同態(tài)加密