[發(fā)明專利]一種基于基22

在審

• 申請?zhí)枺?/td>: 202110060895.8
• 申請日: 2021-01-18
• 公開（公告）號: CN112799634A
• 公開（公告）日: 2021-05-14
• 發(fā)明（設(shè)計）人: 劉偉強;姚衎;張雨晴;王成華
• 申請（專利權(quán)）人: 南京航空航天大學(xué)
• 主分類號: G06F7/523
• 分類號: G06F7/523
• 代理公司: 南京蘇高專利商標(biāo)事務(wù)所(普通合伙) 32204
• 代理人: 顏盈靜

本發(fā)明公開了一種基于基2²MDC NTT結(jié)構(gòu)的高性能環(huán)多項式乘法器，包括用于進行NTT變換的多路延遲轉(zhuǎn)接電路；所述多路延遲轉(zhuǎn)接電路為四輸入輸出通路結(jié)構(gòu)，其由y級處理單元構(gòu)成，每級處理單元均包括一個蝶形單元、多個具有不同延時周期的數(shù)據(jù)延時單元、多個用于存儲NTT變換所需的旋轉(zhuǎn)因子的存儲單元和一個用于按照NTT算法將數(shù)據(jù)按正確時序往下傳遞的交換單元；本發(fā)明通過高基的NTT算法減少NTT變換的級數(shù)，在硬件實現(xiàn)時達到了減少時間周期以及高吞吐率的效果，同時簡化控制單元。

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

本發(fā)明涉及格密碼環(huán)多項式乘法，提出了一種基于基2²MDC NTT結(jié)構(gòu)的高性能環(huán)多項式乘法器。

背景技術(shù)

在量子計算機誕生之后，現(xiàn)有的RSA、橢圓曲線等公鑰密碼體制的安全性將可能會被動搖，但格密碼學(xué)的安全性基于最壞情況下的格上困難問題，所以其安全性有很強的保證，能夠抵抗量子計算機的攻擊。此外，格密碼學(xué)上的計算非常簡單，對于理想格和模格，所有算法都在多項式環(huán)中進行，許多情況下只需要多項式乘積模累加運算。

常規(guī)的多項式乘法不用考慮數(shù)域問題，但是在環(huán)上的多項式對多項式的系數(shù)和次數(shù)都有限制，例如給定兩個環(huán)上的多項式a(x)和b(x)，設(shè)R_q＝Z_q[x]/(xⁿ+1)是多項式環(huán)，其中n是2的冪，q為模值：

對于環(huán)上的多項式對系數(shù)大小受模值q限制，次數(shù)不超過n。

當(dāng)兩個環(huán)上的多項式相乘時，得到的多項式也要做相應(yīng)處理使：

c(x)∈R_q＝Z_q[x]/(xⁿ+1) (3)

多項式乘法有幾種有效的算法，而數(shù)論變換(Number Theoretic Transform，NTT)算法因其O(nlogn)的擬線性時間復(fù)雜度相比于其他算法更加高效、快速，是一種廣泛應(yīng)用于基于格密碼的算法。NTT算法實際上是FFT的一個變體，相比FFT，其替代了復(fù)雜的浮點數(shù)和復(fù)數(shù)乘法的計算。因此，NTT算法的所有計算被執(zhí)行在有限域或多項式環(huán)R_q中，并且在FFT中的復(fù)數(shù)選擇因子用整數(shù)代替，減少了存儲空間。為了滿足n階元素，模數(shù)q必須選擇一個質(zhì)數(shù)，且滿足q≡1mod 2n。

對于NTT變化，多項式a(x)的系數(shù)a₀,a₁,a₂,...,a_n-1,a_n被轉(zhuǎn)換為對于NTT正變換：

逆NTT(INTT)的操作是還原NTT的值，其變換規(guī)則如下：

變換式中的＝_n為旋轉(zhuǎn)因子，當(dāng)兩個n點的多項式相乘時，在f(x)＝xⁿ+1約簡前，有2n個系數(shù)，需要對每個多項式系數(shù)填充n個零，為了減少這個方法的開銷，使用負包裹技術(shù)，用φ²＝ωmod q，旋轉(zhuǎn)因子的平方根進行預(yù)處理和后處理直接得到最終的系數(shù)，c(x)＝a(x)*b(x)。NTT算法操作步驟如下：

1、對a(x)和b(x)中的系數(shù)進行預(yù)處理，即a＝a_i×φⁱ,b＝b_i×φⁱ。

2、將預(yù)處理后的系數(shù)進行NTT變換，即

3、多項式和對應(yīng)系數(shù)相乘，即

4、對多項式進行NTT逆變換，即

5、后處理多項式c(x)，即c_i×φ^-i。