[發明專利]基于二元截斷多項式環的無噪音全同態公鑰加密方法

有效

• 申請號: 201710602150.3
• 申請日: 2017-07-21
• 公開（公告）號: CN107317669B
• 公開（公告）日: 2019-11-26
• 發明（設計）人: 王保倉;周立國
• 申請（專利權）人: 西安電子科技大學
• 主分類號: H04L9/00
• 分類號: H04L9/00;H04L9/08
• 代理公司: 61205 陜西電子工業專利中心
• 代理人: 韋全生;王品華<國際申請>=<國際公布>

1.一種基于二元截斷多項式環的無噪音全同態公鑰加密方法，包括如下步驟：

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

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

(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個整數a_l、b_l和a_ij，l＝1,2,3,4，i,j＝0,1,2，并由這些整數構造三個二元多項式f₁(x,y)、f₂(x,y)和f₃(x,y)：

f₁(x,y)＝x³+a₁xy+a₂x+a₃y+a₄，

f₂(x,y)＝y³+b₁xy+b₂x+b₃y+b₄，

(2.4)用戶采用三個二元多項式f₁(x,y)、f₂(x,y)和f₃(x,y)，分別計算三個含有公共根(a,b)的二元多項式g₁(x,y)、g₂(x,y)和g₃(x,y)：

g₁(x,y)≡f₁(x,y)-f₁(a,b)≡x³+a₁xy+a₂x+a₃y+a′₄(mod p)，

g₂(x,y)≡f₂(x,y)-f₂(a,b)≡y³+b₁xy+b₂x+b₃y+b′₄(mod p)，

其中，a′₄、b′₄和a′₀₀分別為二元多項式g₁(x,y)、g₂(x,y)和g₃(x,y)的常數項；

(2.5)用戶在剩余類環中均勻且隨機選取17個整數c_l、d_l和c_ij，l＝1,2,3,4，i,j＝0,1,2，并由這些整數構造三個二元多項式h₁(x,y)、h₂(x,y)和h₃(x,y)：

h₁(x,y)＝x³+c₁xy+c₂x+c₃y+c₄，

h₂(x,y)＝y³+d₁xy+d₂x+d₃y+d₄，

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

F₁(x,y)＝x³+e₁xy+e₂x+e₃y+e₄，

F₂(x,y)＝y³+z₁xy+z₂x+z₃y+z₄，

其中，e_l、z_l和e_ij分別為二元多項式F₁(x,y)、F₂(x,y)和F₃(x,y)的系數，且l＝1,2,3,4，i,j＝0,1,2；

(2.7)由二元多項式F₁(x,y)、F₂(x,y)、F₃(x,y)和RSA模數N，構造加密公鑰pk_E＝(N,F₁(x,y),F₂(x,y),F₃(x,y))，同時由二元多項式F₁(x,y)、F₂(x,y)和RSA模數N，構造密文同態計算公鑰pk_H＝(N,F₁(x,y),F₂(x,y))；

(2.8)用戶采用二元多項式F₁(x,y)和F₂(x,y)，構造元素為關于變量x,y次數不超過2、系數屬于剩余類環最多含有9項的二元多項式的二元截斷多項式環其中，模N的剩余類環上的二元多項式環為

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

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

(3.2)用戶采用概率加密參數r_t和加密公鑰pk_E，分別對t條明文M_t進行概率加密：用戶計算并采用二元多項式F₁(x,y)、F₂(x,y)和RSA模數N對計算結果取模，得到t個屬于二元截斷多項式環的二元多項式C_t(x,y)，并將其作為t條明文M_t對應的密文；

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

(5)云服務器對密文進行同態計算：

(5.1)云服務器根據用戶需求，從t條密文C_t(x,y)中選擇明文M₁、M₂、M′₁和M′₂對應的密文C₁(x,y)、C₂(x,y)、C′₁(x,y)和C′₂(x,y)，其中，明文M₁、M₂、M′₁和M′₂相同或不同；

(5.2)云服務器采用密文同態計算公鑰pk_H，對密文C₁(x,y)和C₂(x,y)進行同態加法計算：云服務器計算C₁(x,y)+C₂(x,y)，并采用二元多項式F₁(x,y)、F₂(x,y)和RSA模數N對計算結果取模，得到屬于二元截斷多項式環的二元多項式C₊(x,y)，并將其作為密文C₁(x,y)和C₂(x,y)的加法同態密文；

(5.3)云服務器采用密文同態計算公鑰pk_H，對密文C′₁(x,y)和C′₂(x,y)進行同態加法計算：云服務器計算C′₁(x,y)C′₂(x,y)，并采用二元多項式F₁(x,y)、F₂(x,y)和RSA模數N對計算結果取模，得到屬于二元截斷多項式環的二元多項式C_×(x,y)，并將其作為密文C′₁(x,y)和C′₂(x,y)的乘法同態密文；

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

(6.1)用戶采用解密私鑰sk，對密文C₁(x,y)和C₂(x,y)對應的加法同態密文C₊(x,y)進行解密，得到加法同態密文C₊(x,y)對應的明文M₊＝M₁+M₂，其中，解密公式為：

M₊≡C₊(a,b)(mod p)；

(6.2)用戶采用解密私鑰sk，對密文C′₁(x,y)和C′₂(x,y)對應的乘法同態密文C_×(x,y)進行解密，得到乘法同態密文C_×(x,y)對應的明文M_×＝M′₁M′₂，其中，解密公式為：

M_×≡C_×(a,b)(mod p)。