基於二元截斷多項式環的無噪音全同態公鑰加密方法與流程

2023-06-21 18:17:41 4

本發明涉及一種全同態加密方法，具體涉及一種基於二元截斷多項式環的無噪音全同態公鑰加密方法，可應用於雲計算、大數據等數據委託計算服務，提供重要數據的存儲、訪問、統計、挖掘等全程密態隱私保護。

背景技術：

隨著數字信息的爆炸式增長和個人與組織對這些信息的依賴性不斷增強，大規模資料庫逐漸成為整個信息系統的中心，數據成為最重要的資產。對於大規模數據的使用，資料庫往往以委託計算的方式外包給第三方，但是存在信息洩露的風險，這需要對資料庫進行加密以保護數據的隱私性。然而，一般性的數據加密操作會對明文的數據結構進行本質上的破壞，使得密態數據喪失了信息再處理功能。因此，需要一種能在加密數據上進行有效計算的加密方法。

全同態加密作為一種加密形式，它允許用戶對密文進行特定的代數運算得到仍是加密的結果，將其解密與對應的明文進行相同代數運算所得到的結果一樣。換言之，這項技術令用戶可以在已加密的數據上進行任意多次的加法和乘法操作，從而得出相應明文的計算結果所對應的密文，而在整個處理過程中無需對數據進行解密。其意義在於，真正從根本上解決了數據委託計算服務中數據的隱私保護和密態數據的信息再處理之間相互衝突的技術瓶頸問題。一般來說，一種全同態加密方法主要包含參數設置、密鑰獲取、加密、解密和密文同態計算這五個步驟。

目前出現的同態加密方案可分為三種類型：部分同態加密、淺同態加密和全同態加密。部分同態加密只能夠實現某一種代數運算(加或乘)；淺同態加密雖能同時實現密文的加法運算和乘法運算，但是運算次數有限，這樣使得部分同態加密和淺同態加密的計算功能受限，無法滿足實際需求。和淺同態加密相比，全同態加密不受密文運算次數的限制，同時根據在密文中是否引入噪音可分為有噪音全同態加密和無噪音全同態加密。值得注意的是，現有的可證明安全的全同態公鑰加密方法在密文中均引入了噪音，因此，在密文同態計算階段，隨著電路層數增加，同態計算的密文中的噪音會逐漸積累，而當噪聲累積到超過門限值時，就需繁瑣的步驟對密文進行更新，這樣使得密文同態計算過程效率低，同時還存在著因密文和密鑰過長導致浪費存儲空間和通信帶寬的技術問題。例如，zhangp等人在會議《internationalconferenceoncloudcomputing&intelligencesystems》上發表了題目為「anacceleratedfullyhomomorphicencryptionschemeovertheintegers」的論文(2016:419-423)，公開了一種改進的全同態公鑰加密方法，該方法的實現過程是先構造一種淺同態公鑰加密方法，並利用公鑰壓縮技術和中國剩餘定理來降低公鑰尺寸和密文尺寸；而後，再利用壓縮解密電路技術將這個淺同態公鑰加密方法轉換為一種全同態公鑰加密方法，即在密文同態計算的過程中，當同態計算的密文中的噪聲累積到門限值時，利用壓縮和自舉技術對密文進行更新，從而達到支持任意次同態計算的目的。該全同態公鑰方法的缺點在於，雖然利用公鑰壓縮技術和中國剩餘定理降低了密鑰和密文的尺寸，但其尺寸仍舊過大，極大的浪費了存儲空間及通信帶寬，同時，該方法在密文同態計算過程中需要對密文進行更新，步驟繁瑣、效率低。

技術實現要素：

本發明的目的在於克服上述現有技術存在的缺陷，提出了一種基於二元截斷多項式環的無噪音全同態公鑰加密方法，用於解決現有技術中存在的密鑰和密文過長且密文同態計算效率低的技術問題。

為實現上述目的，本發明採取的技術方案包括如下步驟：

(1)參數設置：用戶根據自身安全需求設置安全參數k，並定義明文空間m＝{0,1}k-1為所有k-1比特長整數的集合，其中，k≥1024；

(2)用戶獲取解密私鑰sk、加密公鑰pke和密文同態計算公鑰pkh，並構造二元截斷多項式環實現步驟為：

(2.1)用戶在安全參數k的控制下，隨機生成兩個k比特長的大素數p和q，並計算rsa模數n，n＝pq，再分別構造模p意義下的剩餘類環模q意義下的剩餘類環和模n意義下的剩餘類環

(2.2)用戶在剩餘類環中均勻且隨機選取兩個整數a和b，並與大素數p一起構成解密私鑰sk＝(a,b,p)；

(2.3)用戶在剩餘類環中均勻且隨機選取17個整數ai、bi和aij，i＝1,2,3,4，i,j＝0,1,2，並由這些整數構造三個二元多項式f1(x,y)、f2(x,y)和f3(x,y)：

f1(x,y)＝x3+a1xy+a2x+a3y+a4，

f2(x,y)＝y3+b1xy+b2x+b3y+b4，

(2.4)用戶採用三個二元多項式f1(x,y)、f2(x,y)和f3(x,y)，分別計算三個含有公共根(a,b)的二元多項式g1(x,y)、g2(x,y)和g3(x,y)：

g1(x,y)≡f1(x,y)-f1(a,b)≡x3+a1xy+a2x+a3y+a4′(modp)，

g2(x,y)≡f2(x,y)-f2(a,b)≡y3+b1xy+b2x+b3y+b4′(modp)，

其中，a4′、b4′和a0′0分別為二元多項式g1(x,y)、g2(x,y)和g3(x,y)的常數項；

(2.5)用戶在剩餘類環中均勻且隨機選取17個整數ci、di和cij，i＝1,2,3,4，i,j＝0,1,2，並由這些整數構造三個二元多項式h1(x,y)、h2(x,y)和h3(x,y)：

h1(x,y)＝x3+c1xy+c2x+c3y+c4，

h2(x,y)＝y3+d1xy+d2x+d3y+d4，

(2.6)用戶利用中國剩餘定理，獲取三個定義在剩餘類環上且含有公共根(a,b)的二元多項式f1(x,y)、f2(x,y)和f3(x,y)：

f1(x,y)＝x3+e1xy+e2x+e3y+e4，

f2(x,y)＝y3+z1xy+z2x+z3y+z4，

其中，ei、zi和eij分別為二元多項式f1(x,y)、f2(x,y)和f3(x,y)的係數，且i＝1,2,3,4，i,j＝0,1,2；

(2.7)由二元多項式f1(x,y)、f2(x,y)、f3(x,y)和rsa模數n，構造加密公鑰pke＝(n,f1(x,y),f2(x,y),f3(x,y))，同時由二元多項式f1(x,y)、f2(x,y)和rsa模數n，構造密文同態計算公鑰pkh＝(n,f1(x,y),f2(x,y))；

(2.8)用戶採用二元多項式f1(x,y)和f2(x,y)，構造元素為關於變量x,y次數不超過2、係數屬於剩餘類環最多含有9項的二元多項式的二元截斷多項式環其中，模n的剩餘類環上的二元多項式環為

(3)用戶對明文進行概率加密，實現步驟為：

(3.1)用戶根據需求選擇t條明文mt∈m，並均勻且隨機選取t個概率加密參數其中，t≥2；

(3.2)用戶採用概率加密參數rt和加密公鑰pke，分別對t條明文mt進行概率加密：用戶計算並採用二元多項式f1(x,y)、f2(x,y)和rsa模數n對計算結果取模，得到t個屬於二元截斷多項式環的二元多項式ct(x,y)，並將其作為t條明文mt對應的密文；

(4)用戶對密文ct(x,y)進行解密：用戶採用解密私鑰sk，對各明文mt對應的密文ct(x,y)分別進行解密，得到t條密文ct(x,y)對應的不同明文mt；

(5)雲伺服器對密文進行同態計算：

(5.1)雲伺服器根據用戶需求，從t條密文ct(x,y)中選擇明文m1、m2、m1′和m2′對應的密文c1(x,y)、c2(x,y)、c1′(x,y)和c2′(x,y)，其中，明文m1、m2、m1′和m2′相同或不同；

(5.2)雲伺服器採用密文同態計算公鑰pkh，對密文c1(x,y)和c2(x,y)進行同態加法計算：雲伺服器計算c1(x,y)+c2(x,y)，並採用二元多項式f1(x,y)、f2(x,y)和rsa模數n對計算結果取模，得到屬於二元截斷多項式環的二元多項式c+(x,y)，並將其作為密文c1(x,y)和c2(x,y)的加法同態密文；

(5.3)雲伺服器採用密文同態計算公鑰pkh，對密文c1′(x,y)和c2′(x,y)進行同態加法計算：雲伺服器計算c1′(x,y)c2′(x,y)，並採用二元多項式f1(x,y)、f2(x,y)和rsa模數n對計算結果取模，得到屬於二元截斷多項式環的二元多項式c×(x,y)，並將其作為密文c1′(x,y)和c2′(x,y)的乘法同態密文；

(6)用戶對同態密文進行解密：

(6.1)用戶採用解密私鑰sk，對密文c1(x,y)和c2(x,y)對應的加法同態密文c+(x,y)進行解密，得到加法同態密文c+(x,y)對應的明文m+＝m1+m2，其中，解密公式為：

m+≡c+(a,b)(modp)；

(6.2)用戶採用解密私鑰sk，對密文c1′(x,y)和c2′(x,y)對應的乘法同態密文c×(x,y)進行解密，得到乘法同態密文c×(x,y)對應的明文m×＝m1′m2′，其中，解密公式為：

m×≡c×(a,b)(modp)。

本發明與現有技術相比，具有以下優點：

1、本發明由於在加密和密文同態計算過程中，引入二元多項式對計算結果進行取模，使得多項式在乘法計算過程中項數不會增加，從而控制了密文的增長，所有密文及密鑰長度均為常數級，與現有技術相比，極大的降低了密文及密鑰所需的存儲空間和通信帶寬。

2、本發明由於在加密過程中，使用含有公共根的三個多項式對明文進行概率加密，而未引入噪音，從而避免了現有的有噪音全同態加密方法在密文同態計算中繁瑣的密文刷新過程，與現有技術相比，有效的提高了密文同態計算過程的效率。

附圖說明

附圖1為本發明的實現流程圖。

具體實施方式

以下結合附圖和具體實施例，對本發明進行進一步詳細說明。

參照附圖1，基於二元截斷多項式環的無噪音全同態公鑰加密方法，實現步驟為：

步驟1)參數設置：用戶根據自身安全需求設置安全參數k，並定義明文空間m＝{0,1}k-1為所有k-1比特長整數的集合，其中，k＝1024；

步驟2)用戶獲取解密私鑰sk、加密公鑰pke和密文同態計算公鑰pkh，並構造二元截斷多項式環實現步驟為：

步驟2.1)用戶在安全參數k的控制下，隨機生成兩個k比特長的大素數p和q，並計算rsa模數n，n＝pq，再分別構造模p意義下的剩餘類環模q意義下的剩餘類環和模n意義下的剩餘類環

步驟2.2)用戶在剩餘類環中均勻且隨機選取兩個整數a和b，並與大素數p一起構成解密私鑰sk＝(a,b,p)；

步驟2.3)用戶在剩餘類環中均勻且隨機選取17個整數ai、bi和aij，i＝1,2,3,4，i,j＝0,1,2，並由這些整數構造三個二元多項式f1(x,y)、f2(x,y)和f3(x,y)：

f1(x,y)＝x3+a1xy+a2x+a3y+a4，

f2(x,y)＝y3+b1xy+b2x+b3y+b4，

步驟2.4)用戶採用三個二元多項式f1(x,y)、f2(x,y)和f3(x,y)，分別計算三個含有公共根(a,b)的二元多項式g1(x,y)、g2(x,y)和g3(x,y)：

g1(x,y)≡f1(x,y)-f1(a,b)≡x3+a1xy+a2x+a3y+a4′(modp)，

g2(x,y)≡f2(x,y)-f2(a,b)≡y3+b1xy+b2x+b3y+b4′(modp)，

其中，a4′、b4′和a0′0分別為二元多項式g1(x,y)、g2(x,y)和g3(x,y)的常數項；

本步驟所述二元多項式g1(x,y)、g2(x,y)和g3(x,y)含有公共根(a,b)，其原因在於：用戶將整數a和整數b帶入二元多項式g1(x,y)、g2(x,y)和g3(x,y)中，計算g1(a,b)≡f1(a,b)-f1(a,b)≡0(modp)，g2(a,b)≡f2(a,b)-f2(a,b)≡0(modp)，g3(a,b)≡f3(a,b)-f3(a,b)≡0(modp)，由此可得二元多項式g1(x,y)、g2(x,y)和g3(x,y)分別滿足g1(a,b)≡0(modp)、g2(a,b)≡0(modp)和g3(a,b)≡0(modp)，即二元多項式g1(x,y)、g2(x,y)和g3(x,y)含有公共根(a,b)。

步驟2.5)用戶在剩餘類環中均勻且隨機選取17個整數ci、di和cij，i＝1,2,3,4，i,j＝0,1,2，並由這些整數構造三個二元多項式h1(x,y)、h2(x,y)和h3(x,y)：

h1(x,y)＝x3+c1xy+c2x+c3y+c4，

h2(x,y)＝y3+d1xy+d2x+d3y+d4，

步驟2.6)用戶利用中國剩餘定理，獲取三個定義在剩餘類環上且含有公共根(a,b)的二元多項式f1(x,y)、f2(x,y)和f3(x,y)：

f1(x,y)＝x3+e1xy+e2x+e3y+e4，

f2(x,y)＝y3+z1xy+z2x+z3y+z4，

其中，ei、zi和eij分別為二元多項式f1(x,y)、f2(x,y)和f3(x,y)的係數，且i＝1,2,3,4，i,j＝0,1,2，其計算公式分別為：

i＝1,2,3時，ei≡ai(modp),ei≡ci(modq)，e4≡a4′(modp),e4≡c4(modq)，

i＝1,2,3時，zi≡bi(modp),zi≡di(modq)，z4≡b4′(modp),z4≡d4(modq)，

i,j＝0,1,2，且當i,j不同時為0時，eij≡aij(modp),eij≡cij(modq)，

e00≡a0′0(modp),e00≡c00(modq)；

本步驟中利用中國剩餘定理對二元多項式f1(x,y)、f2(x,y)和f3(x,y)的係數按如上方式進行計算，實質上是要求所獲取的二元多項式f1(x,y)、f2(x,y)和f3(x,y)分別滿足：

f1(x,y)≡g1(x,y)(modp),f1(x,y)≡h1(x,y)(modq)，

f1(x,y)≡g1(x,y)(modp),f1(x,y)≡h1(x,y)(modq)，

f1(x,y)≡g1(x,y)(modp),f1(x,y)≡h1(x,y)(modq)，

同時，由步驟(2.4)中二元多項式g1(x,y)、g2(x,y)和g3(x,y)分別滿足g1(a,b)≡0(modp)、g2(a,b)≡0(modp)和g3(a,b)≡0(modp)可知，本步驟獲取的三個二元多項式f1(x,y)、f2(x,y)和f3(x,y)將分別滿足f1(a,b)≡0(modp)、f2(a,b)≡0(modp)和f3(a,b)≡0(modp)，即二元多項式f1(x,y)、f2(x,y)和f3(x,y)含有公共根(a,b)。

步驟2.7)由二元多項式f1(x,y)、f2(x,y)、f3(x,y)和rsa模數n，構造加密公鑰pke＝(n,f1(x,y),f2(x,y),f3(x,y))，同時由二元多項式f1(x,y)、f2(x,y)和rsa模數n，構造密文同態計算公鑰pkh＝(n,f1(x,y),f2(x,y))；

步驟2.8)用戶採用二元多項式f1(x,y)和f2(x,y)，構造元素為關於變量x,y次數不超過2、係數屬於剩餘類環最多含有9項的二元多項式的二元截斷多項式環其中，模n的剩餘類環上的二元多項式環為

步驟3)用戶對明文進行概率加密，實現步驟為：

步驟3.1)用戶根據需求選擇t條明文mt∈m，並均勻且隨機選取t個概率加密參數其中，t≥2；

步驟3.2)用戶採用概率加密參數rt和加密公鑰pke，分別對t條明文mt進行概率加密：用戶計算並採用二元多項式f1(x,y)、f2(x,y)和rsa模數n對計算結果取模，得到t個屬於二元截斷多項式環的二元多項式ct(x,y)，並將其作為t條明文mt對應的密文；

步驟4)用戶對密文ct(x,y)進行解密：用戶採用解密私鑰sk，對各明文mt對應的密文ct(x,y)分別進行解密，得到t條密文ct(x,y)對應的不同明文mt，其中，解密公式為：

mt≡ct(x,y)(modp)；

本發明能夠正確解密的原理在於：在加密過程中，用戶計算並採用二元多項式f1(x,y)、f2(x,y)和rsa模數n對的計算結果進行取模，得到屬於二元截斷多項式環的二元多項式ct(x,y)，並將其作為明文mt對應的密文，因此存在三個二元多項式e1(x,y)、e2(x,y)和e3(x,y)，使得如下等式成立：

同時，由步驟(2.6)可知，二元多項式f1(x,y)、f2(x,y)和f3(x,y)分別滿足f1(a,b)≡0(modp)、f2(a,b)≡0(modp)和f3(a,b)≡0(modp)，由此可得f1(a,b)e1(a,b)≡0(modp)、f2(a,b)e2(a,b)≡0(modp)和由步驟(2.1)中n＝pq可知，n≡0(modp)，進而有nf3(a,b)≡0(modp)，所以，在解密時，用戶將整數a和整數b代入密文ct(x,y)中，計算最終可正確解密得到密文ct(x,y)對應的明文mt。

步驟5)雲伺服器對密文進行同態計算：

步驟5.1)雲伺服器根據用戶需求，從t條密文ct(x,y)中選擇明文m1、m2、m1′和m2′對應的密文c1(x,y)、c2(x,y)、c1′(x,y)和c2′(x,y)，其中，明文m1、m2、m1′和m2′相同或不同；

步驟5.2)雲伺服器採用密文同態計算公鑰pkh，對密文c1(x,y)和c2(x,y)進行同態加法計算：雲伺服器計算c1(x,y)+c2(x,y)，並採用二元多項式f1(x,y)、f2(x,y)和rsa模數n對計算結果取模，得到屬於二元截斷多項式環的二元多項式c+(x,y)，並將其作為密文c1(x,y)和c2(x,y)的加法同態密文；

步驟5.3)雲伺服器採用密文同態計算公鑰pkh，對密文c1′(x,y)和c2′(x,y)進行同態加法計算：雲伺服器計算c1′(x,y)c2′(x,y)，並採用二元多項式f1(x,y)、f2(x,y)和rsa模數n對計算結果取模，得到屬於二元截斷多項式環的二元多項式c×(x,y)，並將其作為密文c1′(x,y)和c2′(x,y)的乘法同態密文；

在加密、密文同態加法計算和密文同態乘法計算過程中，用戶均採用二元多項式f1(x,y)＝x3+e1xy+e2x+e3y+e4、f2(x,y)＝y3+z1xy+z2x+z3y+z4和rsa模數n分別對c1(x,y)+c2(x,y)和c1′(x,y)c2′(x,y)的計算結果進行取模，也就是說，碰到x3，將x3替換為-(e1xy+e2x+e3y+e4)，碰到y3，將y3替換為-(z1xy+z2x+z3y+z4)，而後採用rsa模數n對所有的係數取模，最終可分別得到屬於二元截斷多項式環的關於變量x,y次數均不超過2、係數屬於剩餘類環最多含有9項的二元多項式ct(x,y)、c+(x,y)和c×(x,y)，並將其分別作為明文mt的密文、密文c1(x,y)和c2(x,y)的加法同態密文和密文c1′(x,y)和c2′(x,y)的乘法同態密文，由此可知所有密文的長度均為常數級。

步驟6)用戶對同態密文進行解密：

步驟6.1)用戶採用解密私鑰sk，對密文c1(x,y)和c2(x,y)對應的加法同態密文c+(x,y)進行解密，得到加法同態密文c+(x,y)對應的明文m+＝m1+m2，其中，解密公式為：

m+≡c+(a,b)(modp)；

本步驟中，用戶採用解密私鑰sk對加法同態密文c+(x,y)進行解密，最終正確解密，得到加法同態密文c+(x,y)對應的明文m+＝m1+m2，其推導過程為：

m+≡c+(a,b)(modp)≡(c1(a,b)+c2(a,b)(modn,f1(x,y),f2(x,y)))(modp)≡m1+m2(modp)＝m1+m2。

步驟6.2)用戶採用解密私鑰sk，對密文c1′(x,y)和c2′(x,y)對應的乘法同態密文c×(x,y)進行解密，得到乘法同態密文c×(x,y)對應的明文m×＝m1′m2′，其中，解密公式為：

m×≡c×(a,b)(modp)；

本步驟中，用戶採用解密私鑰sk對乘法同態密文c×(x,y)進行解密，最終正確解密，得到乘法同態密文c×(x,y)對應的明文m×＝m1′m2′，其推導過程為：

m×≡c×(a,b)(modp)≡(c1′(a,b)c2′(a,b)(modn,f1(x,y),f2(x,y)))(modp)≡m1′m2′(modp)＝m1′m2′。

以上描述僅是本發明的一個具體實例，顯然對於本領域的專業人士來說，在了解了本發明內容和原理後，都不可能在背離本發明原理、結構的情況下，進行形式和細節上的各種修正和改變，但是這些基於本發明思想修正和改變仍在本發明的權利要求保護範圍之內。