一種基于整數(shù)多項(xiàng)式環(huán)上的非對(duì)稱(chēng)全同態(tài)加密方案

孫霓剛 陳宣任 朱浩然

摘? 要： 大數(shù)據(jù)時(shí)代下用戶(hù)數(shù)據(jù)的隱私安全面臨著重大威脅。全同態(tài)加密因其滿(mǎn)足云計(jì)算安全性需求的特性日益受到重視，所以同態(tài)加密算法成為保護(hù)云端數(shù)據(jù)的一種有效手段?；谡麛?shù)多項(xiàng)式環(huán)構(gòu)建了一種非對(duì)稱(chēng)的全同態(tài)加密方案，其中，包括密鑰生成算法、加密算法、解密算法、重加密算法、解密正確性證明以及同態(tài)性證明。該方案運(yùn)行一次KeyGen算法生成一次參數(shù)，即可以對(duì)批量的明文進(jìn)行加密運(yùn)算，也可以對(duì)批量的密文進(jìn)行同態(tài)運(yùn)算，加密效率和同態(tài)計(jì)算效率高，且該方案的安全性基于近似最大公約數(shù)問(wèn)題。

關(guān)鍵詞： 全同態(tài)加密; 整數(shù)多項(xiàng)式環(huán); 近似最大公約數(shù); 云計(jì)算; 同態(tài)性; 加密效率

中圖分類(lèi)號(hào)： TN915.08?34; TP309.7? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A? ? ? ? ? ? ? ? ? 文章編號(hào)： 1004?373X（2020）05?0086?06

An asymmetric fully homomorphic encryption scheme based on integer polynomial ring

SUN Nigang， CHEN Xuanren， ZHU Haoran

（School of Information Science & Engineering， Changzhou University， Changzhou 213000， China）

Abstract： Privacy security of user data are facing major threats in the era of big data. Fully homomorphic encryption has drawn more and more attention since it can satisfy the security requirements of cloud computing， thus， the homomorphic encryption algorithm has become an effective method to protect cloud data. An asymmetric fully homomorphic encryption scheme is constructed based on the integer polynomial ring， which contains the key generation algorithm， the encryption algorithm， the decryption algorithm， the re?encryption algorithm， the proof of decryption correctness and the proof of homomorphism. This scheme can encrypt batches of plaintext or perform homomorphic operations on batches of ciphertext by running key generation algorithm once and generating parameters once， thus the encryption efficiency and homomorphic calculation efficiency are high. The security of this scheme is on the basis of the approximate GCD （greatest common divisor）.

Keywords： fully homomorphic encryption; integer polynomial ring; approximate GCD; cloud computing; homomorphic performance; encryption efficiency

0? 引? 言

隨著“大數(shù)據(jù)時(shí)代”的來(lái)臨，云計(jì)算的不斷發(fā)展，云環(huán)境下用戶(hù)對(duì)儲(chǔ)存隱私數(shù)據(jù)的介質(zhì)產(chǎn)生了懷疑：服務(wù)器方面保密機(jī)制不夠完善，信譽(yù)無(wú)法保證，對(duì)隱私數(shù)據(jù)的安全構(gòu)成隱患的問(wèn)題不能被完全解決。因此，如何在保證用戶(hù)隱私數(shù)據(jù)安全的前提下，將其傳遞到網(wǎng)絡(luò)服務(wù)器端，成為討論和研究的熱門(mén)話題。選擇一個(gè)合適的加密算法對(duì)隱私數(shù)據(jù)進(jìn)行先解密再上傳，最終成為解決這一問(wèn)題的一個(gè)最為便捷、有效的手段。經(jīng)過(guò)不斷的研究、分析和實(shí)驗(yàn)，全同態(tài)加密算法脫穎而出，因其特性成為了最為合適的加密算法。全同態(tài)加密是一種可以讓任何人對(duì)加密后的密文做任意功能的運(yùn)算，得到的結(jié)果解密后，相當(dāng)于對(duì)明文進(jìn)行了等價(jià)運(yùn)算[1]的算法。在云計(jì)算中，有時(shí)候需要第三方對(duì)數(shù)據(jù)進(jìn)行處理，為了確保用戶(hù)數(shù)據(jù)的隱私安全，只能給第三方加密后的數(shù)據(jù)，與此同時(shí)，并不能告知第三方私鑰的值，這時(shí)全同態(tài)加密就起到了至關(guān)重要的作用。除了云計(jì)算方面，全同態(tài)加密方案也被應(yīng)用在其他的許多方面，例如，電子投票、隱私數(shù)據(jù)處理、加密搜索等。

文獻(xiàn)[2]根據(jù)RSA公鑰密碼體制部分運(yùn)算同態(tài)這一特性，提出了隱私全同態(tài)的概念，這也是隱私全同態(tài)這一概念首次被提出。這個(gè)概念提出后，國(guó)內(nèi)外研究人員針對(duì)這一問(wèn)題進(jìn)行了大量的研究[3?5]。

文獻(xiàn)[6]提出了第一個(gè)全同態(tài)加密方案，該方案分為兩部分：構(gòu)造一個(gè)somewhat（部分）同態(tài)加密方案，以及利用引用自舉電路使之成為全同態(tài)加密方案。由于該方案計(jì)算的復(fù)雜性，在實(shí)際布局中是不可行的。在此之后，文獻(xiàn)[7]將該方案在理想格上實(shí)現(xiàn)了。在構(gòu)建的新方案中，已經(jīng)對(duì)很多問(wèn)題進(jìn)行了顯著的優(yōu)化。然而該方案的運(yùn)算復(fù)雜度依舊很高，在保證安全性的設(shè)置下，格的維數(shù)[n=]32 768時(shí)，公鑰的尺寸約為2.3 GB，運(yùn)用高性能計(jì)算機(jī)進(jìn)行運(yùn)算，密鑰的生成時(shí)間為2.2 h，加密需要3 min，單次刷新密文[8]需要30 min。

文獻(xiàn)[9]提出了一個(gè)較為簡(jiǎn)單的全同態(tài)加密方案。該方案是基于整數(shù)環(huán)上的，而不是理想格上的，然而在將方案構(gòu)建完成后發(fā)現(xiàn)，該方案的公鑰尺寸與預(yù)期相比太大，以至于該方案無(wú)法實(shí)現(xiàn)。

文獻(xiàn)[10]提出了一個(gè)縮短全同態(tài)加密方案中公鑰尺寸的想法。同年，Stehle和Steinteld在文獻(xiàn)[10]提出方案的基礎(chǔ)上，進(jìn)一步縮短了公鑰尺寸。同年，Brakerski和Vaikuntanathan提出一個(gè)基于LWE困難度問(wèn)題來(lái)構(gòu)建全同態(tài)加密方案。

自隱私全同態(tài)概念提出以來(lái)，眾多學(xué)者分別基于理想格、LWE環(huán)和整數(shù)環(huán)等提出了許多不同的方案。這些分別基于不同環(huán)上的加密方案，經(jīng)過(guò)不斷的研究、分析和改進(jìn)，用不同的方法讓方案從部分同態(tài)實(shí)現(xiàn)全同態(tài)，也不斷地使用不同的方法來(lái)降低公鑰尺寸和提高加密效率。但是上述方案一次都只能對(duì)1 bit的明文或密文進(jìn)行處理。不同于眾多學(xué)者所研究的理想格、LWE以及整數(shù)環(huán)等，本文基于整數(shù)多項(xiàng)式環(huán)構(gòu)建了一個(gè)非對(duì)稱(chēng)的全同態(tài)加密方案，其中包含了參數(shù)的生成、加密算法、解密算法解密正確性和同態(tài)性的證明。本方案可以對(duì)批量的明文進(jìn)行加密，也可對(duì)批量的密文進(jìn)行同態(tài)運(yùn)算。在KeyGen階段，本方案參數(shù)的數(shù)量級(jí)較小，運(yùn)算復(fù)雜度低，且只需生成一次參數(shù)，即可實(shí)現(xiàn)對(duì)批量的明文進(jìn)行加密處理，降低了運(yùn)算復(fù)雜度，進(jìn)而提高了加密的效率。

1? 數(shù)學(xué)背景

1.1? 近似最大公約數(shù)問(wèn)題

給定一個(gè)隨機(jī)選擇的整數(shù)集[S={x0，x1，x2，…，xn}]，每一個(gè)[xi]都是接近于大素?cái)?shù)[p]，[p]是這些整數(shù)的近似公因子，尋找這個(gè)近似公因子[p]的問(wèn)題稱(chēng)為近似最大公約數(shù)問(wèn)題（Greatest Common Divisor，GCD）。

1.2? 多項(xiàng)式環(huán)的定義

[R]為一個(gè)環(huán)，定義[R[x]={a0+a1x+…+][anxnai∈R}]，其中，[x]是不確定的，[px=a0+a1x+…+][anxn]叫作在[R]上的關(guān)于[x]的多項(xiàng)式。

1.3? 多項(xiàng)式環(huán)上的一些性質(zhì)和結(jié)論

1） [p（x）=a0+a1x+…+anxn，an≠0，ai∈R]，那么[n]叫作多項(xiàng)式[p（x）]的階。

2） [p（x）=i=0naixi]，[qx=i=0mbixi]分別是[n]階，[m]階的兩個(gè)多項(xiàng)式，定義多項(xiàng)式上的“+”為：

[p（x）+qx=i=0max（n，m）（ai+bi）xi];其中，[ai=0]，[?i>n]，[bi=0]，[?i>m]。

3） [p（x）=i=0naixi]，[qx=i=0mbixi]分別是[n]階，[m]階的兩個(gè)多項(xiàng)式，定義多項(xiàng)式上的（*）為： [px*qx=i=0n+mcixi];其中，[ci=r+s=iar?bs]。

2? 非對(duì)稱(chēng)的整數(shù)多項(xiàng)式環(huán)上的全同態(tài)加密方案

2.1? 參數(shù)生成算法（KeyGen）

1） 定義安全參數(shù)為[?]。

2） 定義私鑰為[Sk]，[Sk]是長(zhǎng)度為[?]隨機(jī)生成的一個(gè)質(zhì)數(shù)。

3） 定義[γ]為公鑰的比特長(zhǎng)度。

4） 定義[ρ]為第一次加密后噪聲的比特長(zhǎng)度。

5） 定義[di（x）]為一個(gè)整數(shù)多項(xiàng)式，多項(xiàng)式的系數(shù)為[ai]，[di（x）]為密鑰生成階段隨機(jī)生成的，其中，[（ai）min≥0]，[（ai）max<2γsk]，也就是說(shuō)，[di（x）]每一項(xiàng)的系數(shù)的取值范圍為[0，2γsk]。

6） 定義[ri（x）]為一個(gè)整數(shù)多項(xiàng)式，多項(xiàng)式的系數(shù)為[bi]，[ri（x）]為密鑰生成階段隨機(jī)生成的，其中，[（bi）min>-2ρ]，[（bi）max<2ρ]，也就是說(shuō)，[ri（x）]的每一項(xiàng)系數(shù)的取值范圍為[-2ρ，2ρ]。

7） 定義[xi]為一個(gè)整數(shù)多項(xiàng)式，[xi=sk?di（x）+]

[2ri（x）]。

8） 定義一個(gè)集合[xi;xi=sk?di（x）+2ri（x）]，公鑰[pk]就是這個(gè)集合[xi]的子集，加密時(shí)隨機(jī)地從[xi]中選取一個(gè)子集合[S]。

2.2? 加密算法（Encrypt）

將明文[m]進(jìn)行預(yù)處理，將明文信息表示成多項(xiàng)式的形式，從而使得明文信息可以編碼進(jìn)入多項(xiàng)式[mp（x）]中。將明文[m]表示成二進(jìn)制的形式，[m]的二進(jìn)制數(shù)從高位到低位，每一位的位數(shù)分別與多項(xiàng)式[mp（x）]的最高次項(xiàng)到最低次項(xiàng)的每一項(xiàng)的階數(shù)相對(duì)應(yīng)，其每一位的值分別代表多項(xiàng)式[mp（x）]的最高次項(xiàng)到最低次項(xiàng)的每一項(xiàng)的系數(shù)。加密之前的預(yù)處理將明文改寫(xiě)成多項(xiàng)式的形式，這樣加密時(shí)就可以直接對(duì)多項(xiàng)式[mp（x）]進(jìn)行加密，方便加密過(guò)程的進(jìn)行。[Enc：c（x）=m（x）+2?r（x）+i∈ssk?di（x）+2ri（x）]，其中，[s]是{0，1，2，…}的子集。

2.3? 解密算法（Decrypt）

[Dec： m（x）=c（x）modskmod2]

2.4? 重加密算法（Recrypt）

定義[rk=z?sk]，重加密之后的密文為[c]，那么重加密算法為：[c（x）≡c（x）modrk]。重加密密文解密正確性證明：根據(jù)數(shù)學(xué)背景中寫(xiě)到的倍數(shù)間同余的性質(zhì)可知，因?yàn)閇rk=z?sk]，[c（x）≡c（x）modrk]，所以[c（x）≡][c（x）modsk]，也就是說(shuō)，[c]和[c]關(guān)于[sk]是同余的，那么在解密過(guò)程中，因?yàn)槟sk]的值相等，所以再次模2的值一定相等，所以重加密之后的值，解密之后的結(jié)果和原密文相等，證畢。

4? 實(shí)例證明

為使方案更加具有說(shuō)服力，在該部分介紹幾個(gè)實(shí)例，通過(guò)計(jì)算來(lái)證明該方案解密的正確性以及同態(tài)計(jì)算的正確性。任意選取兩個(gè)數(shù)作為明文[m1=6]，[m2=9]，將其表示成二進(jìn)制的形式[m1=0110]，[m2=1001]，對(duì)其進(jìn)行預(yù)處理，將其編碼為多項(xiàng)式，表示成多項(xiàng)式的形式[mp1（x）=x2+x]，[mp2（x）=x3+1]。

1） 對(duì)[mp1（x）]進(jìn)行加密，加密過(guò)程為：[c1（x）=mp1（x）+2?r1（x）+i∈s1sk?di（x）+2?ri（x）]，其他多項(xiàng)式和私鑰[sk]在參數(shù)生成算法中根據(jù)參數(shù)的取值范圍隨機(jī)生成。[sk=813]，[r1（x）=5x2+3x]，[di1（x）=51x2+73x]，[di2（x）=4x+23]，[di3（x）=65x2+x]，[ri1（x）=3x2]，[ri2（x）=5x2+2x]，[ri3（x）=x+2]。將這些多項(xiàng)式代入加密算法中進(jìn)行計(jì)算可得：[c1（x）=94 335x2+63 427x+18 703]。

2） 對(duì)[mp2（x）]進(jìn)行加密，私鑰[sk]與加密[mp1（x）]相同，加密過(guò)程為：[c2（x）=mp2（x）+2?r2（x）+][j∈s2sk?dj（x）+]

[2?rj（x）]，[r2（x）=3x2+x]，[dj1（x）=72x3+12]，[dj2（x）=31x2+]

[x+7]，[dj3（x）=21x+1]，[rj1（x）=x2+x]，[rj2（x）=][6x+5]，

[rj3（x）=3x2+1]。

將這些多項(xiàng)式代入加密算法中進(jìn)行計(jì)算可得：[c2（x）=58 537x3+25 217x2+17 902x+16 273]。

3） 驗(yàn)證解密的正確性。

上文已經(jīng)計(jì)算出[mp1（x）]加密后得到的[c1（x）]的值，解密算法為：[m（x）=c（x）modskmod2]，所以分別對(duì)[c1（x）]每一項(xiàng)的系數(shù)進(jìn)行先模813再模2的計(jì)算：94 335mod813mod2=1，63 427mod813mod2=1，18 703mod

813mod2=0，解密后的明文[m′p1（x）=x2+x]與[mp1（x）]相等，[m1]解密正確。對(duì)[c2（x）]每一項(xiàng)的系數(shù)也進(jìn)行同樣的模運(yùn)算，58 537mod813mod2=1，25 217mod813mod2=0，17 902mod813mod2=0，16 273mod813mod2=1，解密后的明文[m′p2（x）=x3+1]與[mp2（x）]相等，[m2]解密正確，至此，解密正確性驗(yàn)證完畢，能夠正確解密。

4） 驗(yàn)證加法同態(tài)性。

[c1（x）+c2（x）=94 335x2+63 427x+18 703+58 537x3+]

[25 217x2+17 902x+16 273 =? ? ? ? ? 58 537x3+119 552x2+]

[81 329x+][34 976]，對(duì)其進(jìn)行解密運(yùn)算，58 537mod 813mod2=1，119 552mod813mod2=1，81 329mod 813mod2=1，34 976mod813mod2=1，解密后的結(jié)果為：[x3+x2+x+1]。[mp1（x）+mp2（x）=x3+x2+x+1]，解密后的結(jié)果與其相等，所以加密同態(tài)性驗(yàn)證完畢。

5） 驗(yàn)證乘法同態(tài)性。

[c1（x）?c2（x）=（94 335x2+63 427x+18 703）?（58 537x3+]

[25 217x2+17 902x+16 273）? ? ? ? ?=? ? ? ? ?5 522 087 895x5+][6 091 671 994x4? +? ?4 383 041 341x3? ?+? ?3 142 217 160x2+]

[1 366 968 677x+304 353 919]，對(duì)每一項(xiàng)的系數(shù)進(jìn)行模813再模2的運(yùn)算進(jìn)行解密，5 522 087 895mod813mod2=1，6 091 671 994mod813mod2=1，4 383 041 340mod813 mod2=0，3 142 217 160mod813mod2=1，1 366 968 677mod 813mod2=1，304 353 919mod813mod2=0，解密后的結(jié)果為：[x5+x4+x2+x]，[mp1（x）?mp2（x）=x5+x4+x2+x]，[c1（x）?c2（x）]解密后的結(jié)果與其相等，所以乘法同態(tài)性驗(yàn)證完畢，至此，同態(tài)性驗(yàn)證完畢。

5? 結(jié)? 語(yǔ)

本文構(gòu)建了一個(gè)基于整數(shù)多項(xiàng)式環(huán)上的非對(duì)稱(chēng)全同態(tài)加密方案，該方案是一個(gè)可以對(duì)明文和密文進(jìn)行批處理的全同態(tài)加密方案。在該方案的重加密算法中無(wú)需進(jìn)行同態(tài)加密，這與其他的全同態(tài)加密方案相比是一個(gè)顯著的優(yōu)勢(shì)。因?yàn)樵谥丶用芩惴ㄖ?，同態(tài)解密是一個(gè)復(fù)雜度相當(dāng)高的算法，因?yàn)楸疚臉?gòu)建的方案無(wú)需進(jìn)行同態(tài)解密，所以在很大程度上降低了運(yùn)算復(fù)雜度，提高了效率。

參考文獻(xiàn)

[1] 陳智罡，王箭，宋新霞.全同態(tài)加密研究[J].計(jì)算機(jī)應(yīng)用研究，2014，31（6）：1624?1630.

[2] RIVEST R L， ADLEMAN L M， DERTOUZOS M L. On data banks and privacy homomorphisms [J]. Foundations of secure computation， 1978， 7（1）： 169?179.

[3] DOMINGO?FERRER J. A provably secure additive and multiplicative privacy homomorphism [C]// Proceedings of the Fifth International Conference on Information Security. Berlin： Springer?Verlag， 2002： 471?483.

[4] BRICKELL E F， YACOBI Y. On privacy homomorphisms （Extended abstract） [C]// Workshop on Advances in Cryptology?EuroCrypt. Amsterdam， The Netherlands： Springer?Verlag， 1987： 117?125.

[5] GENTRY， CRAIG. Fully homomorphic encryption using ideal lattices [C]// Proceedings of the Annual ACM Symposium on Theory of Computing. Bethesda， MD： ACM， 2009： 169?178.

[6] PFITZMANN B， WAIDNER M. Attacks on protocols for server?aided computation [C]// Workshop on the Theory and Application of Cryptographic Techniques. Berlin， Germany： Springer?Verlag， 1993： 153?162.

[7] GENTRY C， HALEVI S. Implementing Gentrys fully?homomorphic encryption scheme [C]// Proceedings of the 30th Annual International Conference on Theory and Applications of Cryptographic Techniques： Advances in Cryptology. Berlin： Springer?Verlag， 2011： 129?148.

[8] 羅炳聰，柳青，馬遠(yuǎn)，等.具有較短公鑰的批處理整數(shù)上的全同態(tài)加密方案[J].計(jì)算機(jī)應(yīng)用研究，2014，31（4）：1180?1184.

[9] DIJK M V， GENTRY C， HALEVI S， et al. Fully homomorphic encryption over the integers [C]// Advances in Cryptology?EUROCRYPT. Berlin： Springer， 2010： 24?43.

[10] CORON JEAN?S?BASTIEN， MANDAL AVRADIP， NACCACHE DAVID， et al. Fully homomorphic encryption over the integers with shorter public keys [C]// Conference on Advances in Cryptology. Santa Barbara， CA， USA： Springer?Verlag， 2011： 487?504.