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

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

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

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

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

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

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

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