一類整數(shù)上有效的全同態(tài)加密方案.pdf

1、全同態(tài)加密方案(FullyHomomorphicEncryption)，曾被稱為隱私同態(tài)，可以實現(xiàn)在不解密密文的情況下對密文用門電路進行處理得到一個新密文，對該新密文進行解密與對相應(yīng)的明文做同樣處理的結(jié)果相等。1978年，Rivest，Adleman和Dertouzous在RSA加密方案提出不久之后，根據(jù)RSA加密方案[2]是一種乘法同態(tài)的加密方案，提出的全同態(tài)的加密思想[1]:一個包括有效評估算法Evaluateε的加密方案ε，對任意

2、有效的公鑰pk，任意門電路C（不僅僅包括RSA中的乘法門電路）以及任意的密文ψi←Encryptε(pk，πi)，可以輸出ψ←Evaluateε(pk，C,ψ1，…,ψt)，這是在公鑰pk下對C（π1，…，πt）的有效加密。
　　基于全同態(tài)的加密思想可以構(gòu)造全同態(tài)加密方案實現(xiàn)在沒有解密密鑰的前提下對加密的數(shù)據(jù)進行任意計算，來保護用戶的隱私。該加密方案可以有效的運用在云計算、隱私查詢、物聯(lián)網(wǎng)、電子商務(wù)等領(lǐng)域中，以保護用戶的數(shù)據(jù)隱私。

3、盡管全同態(tài)加密方案具有良好的性質(zhì)，國內(nèi)外學(xué)者也對其做了大量的研究，但所提出的方案很難做到對任意深度的門電路或任意次數(shù)多項式的處理。
　　直到2009年，Gentry基于理想格困難問題，利用Bootstrappable思想和重加密技術(shù)構(gòu)造出第一個全同態(tài)加密方案[3]。根據(jù)Gerry構(gòu)造全同態(tài)加密方案的思路，越來越多的研究者不斷提出新的全同態(tài)加密方案。現(xiàn)在的全同態(tài)加密構(gòu)造方案大致分為三類[8]:第一類，Gentry基于理想格困難問題構(gòu)

4、造的最初的全同態(tài)加密方案[3];第二類，Dijk等人提出的基于整數(shù)上運算的全同態(tài)加密方案[5]，簡稱DGHV全同態(tài)加密方案;第三類，Brakerski和Vaikuntanathan等人提出的基于LWE和RLWE困難問題的全同態(tài)加密方案[9，10]。
　　2010年，Dijk和Gentry等人提出了一個基于整數(shù)運算上的全同態(tài)加密方案[5]，被稱為DGHV方案。該方案在簡單的代數(shù)結(jié)構(gòu)上進行研究，完全基于整數(shù)上的基本運算，將明文的1比特

5、加密為一個大整數(shù)。并將該方案的安全性規(guī)約到近似GCD困難問題和SSIP困難問題。
　　2011年，Coron和Mandal等人針對DGHV方案中存在的公鑰占用空間大的問題進行了改進，用二次形式生成公鑰代替最初DGHV方案中線性形式的生成公鑰，將所需的公鑰大小從(O)（λ10）降低到(O)（λ7）[7]，并將改進方案的安全性規(guī)約到基于多變量的近似GCD困難問題。
　　2013年，Coron和Lepoint等人針對DGHV方案的

6、密文膨脹率高的問題進行了改進，利用中國剩余定理，將多個明文比特加密為一個密文，實現(xiàn)DGHV方案的批處理功能[8]，將DGHV方案中的密文膨脹率從(O)（λ5）降低到(O)（λ3）
　　本文主要針對DGHV方案的密文膨脹率問題提出另外一種改進方案，利用{0，1}k數(shù)域上的相關(guān)知識，將k個明文比特轉(zhuǎn)化為(0，…，2k-1)上的整數(shù)，對整數(shù)進行加密，實現(xiàn)DGHV方案的批處理功能。將DGHV方案中密文形式c=q·p+2·r+m，轉(zhuǎn)換為c=

7、q·p+2k·r+m，其中p為私鑰，q為一個大隨機整數(shù)，r為一個小隨機整數(shù)（噪音）。通過將改進方案中的安全參數(shù)λ'設(shè)置為λ+k，其中λ為DGHV方案中的安全參數(shù)，使得改進方案滿足正確的同態(tài)解密，從而構(gòu)造出一類整數(shù)上有效的全同態(tài)加密方案。與加密k個比特的DGHV方案相比，該改進方案可以將密文的大小從(O)（k·λ10）降低到(O)((λ+k)10)，相應(yīng)的公鑰大小從(O)(λ10)增加到(O)((λ+k)10)，私鑰大小從(O)(λ2)增