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

孫霓剛 陳宣任 朱浩然

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

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

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

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

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

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

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

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

1? 數(shù)學背景

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

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

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

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

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

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

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

[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]階的兩個多項式，定義多項式上的（*）為： [px*qx=i=0n+mcixi];其中，[ci=r+s=iar?bs]。

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

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

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

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

3） 定義[γ]為公鑰的比特長度。

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

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

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

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

[2ri（x）]。

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

2.2? 加密算法（Encrypt）

將明文[m]進行預處理，將明文信息表示成多項式的形式，從而使得明文信息可以編碼進入多項式[mp（x）]中。將明文[m]表示成二進制的形式，[m]的二進制數(shù)從高位到低位，每一位的位數(shù)分別與多項式[mp（x）]的最高次項到最低次項的每一項的階數(shù)相對應，其每一位的值分別代表多項式[mp（x）]的最高次項到最低次項的每一項的系數(shù)。加密之前的預處理將明文改寫成多項式的形式，這樣加密時就可以直接對多項式[mp（x）]進行加密，方便加密過程的進行。[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ù)學背景中寫到的倍數(shù)間同余的性質(zhì)可知，因為[rk=z?sk]，[c（x）≡c（x）modrk]，所以[c（x）≡][c（x）modsk]，也就是說，[c]和[c]關(guān)于[sk]是同余的，那么在解密過程中，因為模[sk]的值相等，所以再次模2的值一定相等，所以重加密之后的值，解密之后的結(jié)果和原密文相等，證畢。

4? 實例證明

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

1） 對[mp1（x）]進行加密，加密過程為：[c1（x）=mp1（x）+2?r1（x）+i∈s1sk?di（x）+2?ri（x）]，其他多項式和私鑰[sk]在參數(shù)生成算法中根據(jù)參數(shù)的取值范圍隨機生成。[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]。將這些多項式代入加密算法中進行計算可得：[c1（x）=94 335x2+63 427x+18 703]。

2） 對[mp2（x）]進行加密，私鑰[sk]與加密[mp1（x）]相同，加密過程為：[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]。

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

3） 驗證解密的正確性。

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

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

4） 驗證加法同態(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]，對其進行解密運算，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)性驗證完畢。

5） 驗證乘法同態(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]，對每一項的系數(shù)進行模813再模2的運算進行解密，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)性驗證完畢，至此，同態(tài)性驗證完畢。

5? 結(jié)? 語

本文構(gòu)建了一個基于整數(shù)多項式環(huán)上的非對稱全同態(tài)加密方案，該方案是一個可以對明文和密文進行批處理的全同態(tài)加密方案。在該方案的重加密算法中無需進行同態(tài)加密，這與其他的全同態(tài)加密方案相比是一個顯著的優(yōu)勢。因為在重加密算法中，同態(tài)解密是一個復雜度相當高的算法，因為本文構(gòu)建的方案無需進行同態(tài)解密，所以在很大程度上降低了運算復雜度，提高了效率。

參考文獻

[1] 陳智罡，王箭，宋新霞.全同態(tài)加密研究[J].計算機應用研究，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] 羅炳聰，柳青，馬遠，等.具有較短公鑰的批處理整數(shù)上的全同態(tài)加密方案[J].計算機應用研究，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.