[發(fā)明專利]一種應(yīng)用在格密碼加密的多項(xiàng)式乘法計(jì)算方法

在審

• 申請?zhí)枺?/td>: 202211238942.4
• 申請日: 2022-10-14
• 公開（公告）號(hào): CN115454380A
• 公開（公告）日: 2022-12-09
• 發(fā)明（設(shè)計(jì)）人: 黃海;陳洋;于斌;劉志偉;趙石磊
• 申請（專利權(quán)）人: 哈爾濱理工大學(xué)
• 主分類號(hào): G06F7/523
• 分類號(hào): G06F7/523;G06F7/544;G06F17/14;G06F17/15
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發(fā)明提出了一種應(yīng)用在格密碼加密的多項(xiàng)式乘法計(jì)算方法。該方法通過K?RED的NTT/INTT多項(xiàng)式乘法計(jì)算方法，可以更快地進(jìn)行模乘操作；設(shè)計(jì)一種調(diào)和的NTT和INTT方法，節(jié)省了負(fù)包卷積算法中的預(yù)處理和后處理步驟，也消除了K?RED帶來的模乘因子的影響，有效地減少了NTT算法的計(jì)算復(fù)雜度。

技術(shù)領(lǐng)域

本發(fā)明屬于后量子加密技術(shù)領(lǐng)域，具體涉及一種應(yīng)用在格密碼加密的多項(xiàng)式乘法計(jì)算方法。

背景技術(shù)

隨著量子計(jì)算機(jī)的問世，傳統(tǒng)的公鑰加密體制如RSA、ECC逐漸被Shor算法破解，這會(huì)致使保密信息的安全性大大降低。目前，針對抗量子計(jì)算方面，人們做了大量研究工作。現(xiàn)有的抗量子加密協(xié)議主要應(yīng)用到了基于格、基于編碼、基于格、基于超奇異同源等理論，其中受到廣泛關(guān)注的是基于格的加密算法，在基于格的后量子密碼中，多項(xiàng)式乘法是其中極為耗時(shí)的操作，普通的多項(xiàng)式乘法的算法復(fù)雜度為O(N²)，并且需要對多項(xiàng)式維度進(jìn)行0填充，但是基于數(shù)論變換(Number Theoretic Transform，NTT)的多項(xiàng)式乘法計(jì)算可以將計(jì)算復(fù)雜度降低到O(NlogN)。與傳統(tǒng)的在實(shí)數(shù)域進(jìn)行的多項(xiàng)式乘法不同的是，格密碼中的多項(xiàng)式乘法是在多項(xiàng)式環(huán)Z_g/xⁿ+1下進(jìn)行計(jì)算的，環(huán)中的q對應(yīng)后量子加密協(xié)議中的模數(shù)，并且多項(xiàng)式的每個(gè)系數(shù)范圍在0到q之間，n為多項(xiàng)式的系數(shù)個(gè)數(shù)，一般取為2的冪次，q滿足q＝1mod 2n，ω_n為模數(shù)q的n階單位原根，γ_2n為模數(shù)q的2n次單位原根并且滿足對兩個(gè)n維的多項(xiàng)式進(jìn)行運(yùn)算時(shí)，基于負(fù)包卷積(Negative Wrapped Convolution，NWC)算法的NTT多項(xiàng)乘法可以避免0填充，但是要對多項(xiàng)式乘法的兩個(gè)輸入進(jìn)行預(yù)處理，并且在逆數(shù)論變換(Inverse Number Theoretic Transform，INTT)后對向量進(jìn)行后處理。

給定兩個(gè)多項(xiàng)式，如下式(1)(2)所示：

基于NWC乘法的運(yùn)算步驟如下：

1.對輸入的兩個(gè)多項(xiàng)式向量乘以進(jìn)行預(yù)處理，

2.對向量的元素分別執(zhí)行NTT變換，根據(jù)NTT變換公式得到兩個(gè)NTT域中的向量A＝(A₀，A₁，...，A_n-1)，B＝(B₀，B₁，...，B_n-1)；

3.對兩個(gè)NTT域中的向量進(jìn)行對應(yīng)點(diǎn)乘操作得到C，即C＝(A₀B₀，A₁B₁，...，A_n-1B_n-1)＝(C₀，C₁，...，C_n-1)；

4.根據(jù)INTT的公式對C進(jìn)行逆NTT變換，即得到

5.對向量中的元素分別乘以進(jìn)行后處理，最后得到目的向量

發(fā)明內(nèi)容

本發(fā)明克服了上述技術(shù)的不足，提供了一種應(yīng)用在格密碼加密的多項(xiàng)式乘法計(jì)算方法，旨在解決在格密碼中模數(shù)不同條件下的NTT和INTT的快速運(yùn)算，以及引入的預(yù)處理和后處理的運(yùn)算開銷問題。

第一方面，本發(fā)明實(shí)施例提供了一種基于K-RED模乘運(yùn)算方法，主要是針對模數(shù)為12289的多項(xiàng)式乘法進(jìn)行模乘運(yùn)算，主要包括：