[發明專利]一種全同態加密密文除法實現方法

有效

• 申請號: 201710056966.0
• 申請日: 2017-01-22
• 公開（公告）號: CN106850183B
• 公開（公告）日: 2019-12-27
• 發明（設計）人: 蔣林智;王曉芳
• 申請（專利權）人: 蔣林智
• 主分類號: H04L9/00
• 分類號: H04L9/00;H04L9/08
• 代理公司: 51220 成都行之專利代理事務所(普通合伙)
• 代理人: 溫利平

1.一種全同態加密密文除法實現方法，其特征在于，包括以下步驟：

(1)、將需要上傳到云服務器的數據編碼為多項式，多項式的系數為0或1，以滿足全同態加密要求；

(2)、首先，用戶本地對需要在云服務器進行除法計算的兩個數據p₁、p₂的多項式q₁(x)、q₂(x)分別進行全同態加密，得到的密文分別為E(q₁(x))、E(q₂(x))，其中：

E(q₁(x))＝a₀+a₁x+…+a_m-1x^m-1

E(q₂(x))＝b₀+b₁x+…+b_n-1x^n-1 (1)；

其中，E表示基于NTRU的全同態加密，密文E(q₁(x))也為多項式，a₁～a_m-1為多項式的系數；密文E(q₂(x))也為多項式，b₁～b_n-1為多項式的系數；x為多項式的自變量；

然后，計算冪指數j，冪指數j為整數，并且使得數據p₂的滿足

2^j-1≤p₂≤2^j (2)；

最后，得到加密密文E(q₁(x))、E(q₂(x))以及冪指數j上傳至云服務器；

(3)、快速傅里葉變換的密文計算

在云服務器中，構建一個快速傅里葉變換密文計算函數DFT_ω,T(E(q(x))，用于計算加密密文E(q(x))在每個T次本原單位元根ω處的密文，ω^T＝1，T為2的整數次冪，加密密文E(q(x))為多項式，表示為：

E(q(x))＝c₀+c₁x+…+c_w-1x^w-1；

其中，c₁～c_w-1為多項式的系數，所述T<w/2；

對于加密密文E(q(x))的快速傅里葉變換的密文計算為：

3.1)、如果T＝1，則直接返回加密密文E(q(x))的多項式各項系數，多項式各項系數組成一個向量，作為加密密文E(q(x))在每個T次本原單位元根處的密文，表示為DFT_ω,T(E(q(x))；

3.2)、如果T≠1，則：

3.2.1)、計算加密密文E(q(x))的第t項和t+T/2項密文的和，其中，t＝0,1,2,…,T-1，得到計算結果：

3.2.2)、計算加密密文E(q(x))的第t項和t+T/2項密文的差，其中，t＝0,1,2,…,T-1，得到計算結果：

3.2.3)、將步驟3.2.1)獲得的結果中的t項分別與T次本原單位元根ω的t次冪相乘求和，得到計算結果：

3.2.4)、對計算結果D(x)、F(x)分別進行離散傅里葉變換，即：

DFT_ω,T:D(x)→(D(1),D(ω),D(ω²)，…，D(ω^T-1))

DFT_ω,T:F(x)→(F(1),F(ω),F(ω²)，…，F(ω^T-1)) (6)；

這樣得到兩個向量(D(1),D(ω),D(ω²)，…，D(ω^T-1))、(F(1),F(ω),F(ω²)，…，F(ω^T-1))；

3.2.5)、將步驟3.2.4)得到的兩個向量的分量進行交叉，構成一個新的向量，即加密密文E(q(x))在每個T次本原單位元根處的密文，表示為DFT_ω,T(E(q₁(x))，即：

DFT_ω,T(E(q(x))＝(D(1),F(1),D(ω),F(ω),…D(ω^T-1),F(ω^T-1)) (7)；

(4)、密文乘積計算

在云服務器中，根據步驟(3)構建的快速傅里葉變換密文計算函數，得到任意兩個多項式q′(x)、E(q″(x))的密文乘積E(q′(x))E(q″(x))為：

(5)、計算多項式E(r(x))

在云服務器中，根據以下步驟計算多項式E(r(x))：

5.1)、如果加密密文E(q₁(x))的次數小于加密密文E(q₂(x))的次數，則直接返回E(r(x))＝E(q₁(x))；

5.2)、如果加密密文E(q₁(x))的次數大于等于加密密文E(q₂(x))的次數，則：

5.2.1)、令k為加密密文E(q₁(x))減去加密密文E(q₂(x))得到的多項式的冪次；

5.2.2)、計算加密密文E(q₁(x))的逆(即多項式的逆)，記為即：

其中，k₁是加密密文E(q₁(x))的冪次，計算時，將作為公式(8)中的q′(x)，作為公式(8)中的q″(x)，按照公式(8)進行計算；

計算加密密文E(q₂(x))的逆(即多項式的逆)，記為即：

其中，k₂是加密密文E(q₂(x))的冪次，計算時，將作為公式(8)中的q′(x)，作為公式(8)中的q″(x)，按照公式(8)進行計算；

5.2.3)、計算多項式E^*(h(x))

多項式E^*(h(x))等于模(mod)x^k+1；

5.2.4)、計算多項式E(r(x))

E(r(x))＝E(q₁(x))-E(h(x))E(q₂(x)) (11)；

其中：

E(h(x))＝rev_kE^*(h(x)) (12)；

計算時，將E(h(x))作為公式(8)中的E(q′(x))，E(q₂(x))作為公式(8)中的q″(x)，按照公式(8)進行計算；

(6)、在云服務器中，根據以下公式，計算數據p₂的倒數密文：

Eⁱ(r(x))＝(E(r(x)))ⁱ (13)；

其中，z為冪次；

(7)、在云服務器中，根據以下公式，計算出：

然后，發送回用戶。