一種用于小模數多項式乘法快速數論變換的擴域方法*

殷彥昭, 烏力吉, 張向民, 徐 科, 楊 維

1. 北京信息科學與技術國家研究中心, 北京100084

2. 清華大學 微電子學研究所, 北京100084

3. 中興通訊股份有限公司, 深圳518057

1 引言

在基于R-LWE[1]原理的格密碼中, 多項式環乘法是最為關鍵的基礎運算, 也是算法設計和實現時最需要進行優化的運算模塊. 如果不進行優化, 則多項式乘法的復雜度為O(n2), 其中n 是多項式長度. 多項式乘法的高復雜度會嚴重拖慢密碼算法的運行速度, 占用大量開銷, 因此大多數基于R-LWE 的格密碼算法使用快速數論變換來進行加速. 該方法利用多項式系數的有限域特性, 構造多項式時域和頻域的相互變換關系, 將多項式乘法在時域的卷積變為頻域上的點積, 并利用折半定理實現快速數論變換, 從而大幅提升多項式環乘法的運算速度. NTRU[2]、NewHope[3]等格密碼算法都是采用該方法進行多項式乘法的快速實現.

使用快速數論變換進行多項式環乘法時, 多項式及其系數域的參數都需要滿足一定條件, 這對格密碼的設計帶來了很大限制. 要進行快速數論變換, 多項式系數域的階N 必須滿足N ?1 是多項式長度的倍數, 因此當模數小于多項式長度時(如LAC[4]算法等), 格密碼算法就無法使用快速數論變換來進行加速了. 為了解決這一問題, 本文設計了一種多項式系數域的擴域方法, 使得系數域的階數滿足數論變換的條件, 實現快速數論變換來加速多項式乘法的實現.

本文主要貢獻如下:

(1) 設計一種擴域構造方案, 使小模數多項式乘法滿足數論變換的條件.

(2) 基于系數域擴域, 設計復合基快速變換方法實現快速數論變換.

(3) 對R-LWE 體系的格密碼常用的小模數多項式環乘法應用擴域方法, 分析計算復雜度, 與未使用快速數論變換時的復雜度進行對比, 論證擴域法實現快速數論變換的有效性.

2 預備知識

2.1 符號定義

DIT 用于快速數論變換的時域抽取分治法

DIF 用于快速數論變換的頻域抽取分治法

2.2 多項式環乘法

R-LWE 體系中的多項式乘法定義在多項式環上. 構造多項式環時, 首先需要為多項式的系數選擇一個有限域, 一般是選擇一個特征為q 的素域. 然后, 再選擇模多項式f(x), 定義環上多項式乘法為g(x)×h(x)=g(x)h(x)mod f(x), 加法亦同, 加完之后需要模掉f(x). 由此, 由系數為Zq域元素的多項式和上述加法乘法組成多項式環, 記為Rq=Zq[x]/f(x).

現有的R-LWE 算法體系多采用f(x) = xn+1 作為多項式環的模多項式. 由于模去階數為n 的多項式f(x) 后, 原多項式的最高次項為xn?1, 因此模xn+1 環上多項式長度最大為n. 設多項式系數的模數為q, 三個多項式g(x)、h(x)、r(x) 分別如式(1)、式(2)和式(3)所示, 則多項式環乘法r(x)=g(x)h(x)中各多項式系數的關系如式(4)所示, 稱之為回環乘法結構. 該乘法結構是本文所研究的多項式乘法基礎表達式.

3 基2 快速數論變換實現多項式乘法

觀察如式(4)所示的多項式乘法公式, 可以發現該表達式與數字信號處理中的循環卷積非常相似. 因此, 依據傅里葉變換中的“時域卷積對應頻域相乘” 這一特性, 將多項式表示為類似于信號頻譜的點值表示法, 將兩個多項式的點值表示相乘之后再變換回原多項式, 可以進行乘法的快速實現. 將多項式變換為點值表示法的過程稱為數論變換(NTT)[5], 其反過程稱為逆數論變換(INTT). 在特殊的取值下, 利用類似快速傅里葉變換的折半定理, 便可將數論變換的復雜度降低至O(n log n), 其中n 為多項式長度.

3.1 多項式的點值表示法與數論變換

我們知道, n ?1 次函數f(x) 上的n 個不同點可以唯一確定這個函數, 即唯一確定該函數的n 個系數. 同理, 長度為n 的多項式f(x) 也可以由n 組不同的點值對{xi,f(xi)} 唯一確定. 如果兩個多項式用一組相同的自變量求出點值對, 則這兩個多項式相乘的結果可以直接用點值對中自變量不變,因變量相乘來表示, 即f(x) ?g(x) 的點值表示法為{xi,f(xi) ?g(xi)}. 定義f(x) 在自變量序列為X = {xi|i = 0,1,2,··· ,n ?1} 下的點值序列為F = {Fi|Fi= f(xi)}, 則使用點值表示法進行的多項式乘如算法1 所示.

算法1 使用點值法進行多項式乘Input: 多項式g(x),h(x), 自變量取值序列{xi}Output: r(x) = g(x)?h(x)1 求g(x) 的點值表示法Gi = g(xi)2 求h(x) 的點值表示法Hi = h(xi)3 計算r(x) 的點值表示法Ri = Gi ?Hi 4 由點值表示形式R = {R0,R1,··· ,Rn?2,Rn?1} 求解多項式r(x)

使用點值表示法進行多項式乘時, 自變量取值序列或集合的選擇非常重要. 如果不能通過適當的自變量取值序列來快速實現多項式和點值表示法的互相轉換, 使用點值表示法進行多項式乘就沒有意義了.R-LWE 體系中多項式系數是有限域Zp中的元素, 因此利用有限域的性質可以尋找一個Zp上的生成元r 滿足如下條件:

? r2n=1, 其中n 是多項式長度;

? 當0 ≤i,j <2n 且i ?=j 時, ri?=rj.

3.2 使用折半定理實現快速數論變換

雖然快速數論變換法能夠提供對數量級的加速效果, 但并非所有多項式乘法都可以使用這種方法. 進行數論變換本身就對多項式及系數域的模數有一定要求, 而實現快速數論變換的要求則更為嚴苛. 首先,要生成數論變換的變換基{xi}, 就需要尋找生成元r, 而根據數論知識, 要滿足r 的條件, 則有限域的模數q 必須滿足q ?1 是多項式長度n 的倍數. 又由于最佳效果的快速數論變換要求多項式長度為2 的冪次,據此可以得到快速數論變換對多項式長度和模數的要求:

? n=2k, k 為正整數

? q =n ?C +1, C 為常數

? q 為素數同時滿足這三個條件的參數取值組合很有限, 這也是R-LWE 體系算法的設計難點之一. 而像LAC 這樣的小模數R-LWE 算法更是無法實現快速數論變換, 因為其模數小于多項式長度, 不可能滿足q ?1 是n的倍數這一條件. 因此, 我們嘗試使用擴域方法來進行小模數多項式乘法的快速數論變換.

4 本文方法

小模數多項式乘法不能使用常規NTT 的原因是多項式系數域太小而無法構造NTT 變換基, 因此我們可以嘗試構造原系數域的擴域, 擴大系數域的階數, 使其滿足條件. 多項式系數使用擴域后, 由于其階N 無法滿足N ?1 是2 的冪次這一條件, 因此多項式的長度也無法構造成2 的冪次, 基2 快速變換無法進行. 因此, 我們對多項式長度進行質因子分解, 使用復合基快速NTT 變換來達到與基2 快速變換接近的指數級加速效果.

4.1 擴域構造方法及證明

設Zq為原多項式的系數域, 其中q 是一個小于多項式長度N 的素數. 按照如下方法構造Zq的擴域ZPq:

? 元素集合: {[a,b]|a ∈Zq,b ∈Zq};

? 加法規則: [a,b]+[c,d]=[a+c,b+d];

? 乘法規則: [a,b]×[c,d]=[ac ?bd,ad+bc].下面我們將給出這種構造方法的證明. 首先, 證明ZPq是一個域.

? 證明{ZPq,+} 是交換群:

(1) 依據ZPq上的加法定義可知其滿足封閉性和結合律.

(2) {ZPq,+} 上存在唯一單位元(即ZPq的零元)[0,0]: [0,0]+[a,b]=[0+a,0+b]=[a,b].

(3) {ZPq,+} 上任意元素存在逆元: ?[a,b]=[?a,?b].

(4) ZPq上加法滿足交換律: [a,b]+[c,d]=[a+c,b+d]=[c+a,d+b]=[c,d]+[a,b].

? 證明{ZPq?{[0,0]},×} 是交換群:

(1) 依據ZPq上的乘法定義可知其滿足封閉性.

(2) ZPq上乘法滿足結合律:

(3) {ZPq?{[0,0]},×} 上存在唯一單位元[1,0]: [1,0]×[a,b]=[1a ?0b,0a+1b]=[a,b]

(4) {ZPq?{[0,0]}} 中任意元素[a,b] 存在乘法逆元[a,b]?1=[a(a2+b2)?1,?b(a2+b2)?1]

(5) ZPq上乘法滿足交換律: [a,b]×[c,d]=[ac ?bd,ad+bc]=[ca ?db,cb+da]=[c,d]×[a,b]

? 證明{ZPq,+,×} 滿足乘法分配律:

然后證明ZPq中存在一個子域與Zq同構. 這里我們取同構子域為Z′q= {[a,0]|a ∈Zq}, 同構映射為σ(a)=[a,0].

? 加法同構: σ(a)+σ(b)=[a+b,0]=σ(a+b)

? 乘法同構: σ(a)×σ(b)=[ab ?0,0a+0b]=[ab,0]=σ(ab)

擴域構造完成后, 其階必須要大于原系數域的階, 這樣才能比原系數域支持更長的多項式數論變換.表1 列出了q 取128 至256 之間的素數時, ZPq域的階數及生成元r 的參考取值.

表1 由小模數素域生成擴域時不同模數下的部分參數Table 1 Some parameters of different modulus while generating extension field with small modulus field

從表中可以看出, 素數域可以用擴域方法提高階數, 從q 提升至N = q2, 且可從擴域中找到階數為N ?1 的生成元. 這其中有部分參數取值(如q = 251 等) 可以為實際的多項式乘數論變換提供變換基.我們注意到, 雖然擴域生成元r 的階數N ?1 無法構造為2 的冪次, 但在部分參數取值下擴域階數仍然可以分解成比較小的質因子, 從而實現快速數論變換. 在下一節中, 我們介紹使用混合拆分的方法來實現擴域下的快速數論變換.

4.2 復合基快速數論變換

當多項式長度是2 的冪次時, 可以通過不斷進行折半的方法實現快速數論變換, 稱為基2 快速變換；而當多項式長度可以分解成多個不同的質因子時, 同樣可以通過3 等分、5 等分等方式進行快速變換, 稱為復合基快速數論變換. 與FFT 類似, 拆分方式分為時域拆分(DIT) 和頻域拆分(DIF) 兩種, 其中時域拆分從計算結果出發進行拆分, 頻域拆分則是從輸入數據出發進行拆分. 式(7)是使用DIT 方法的折半定理公式, 式(8)則是使用DIF 方法的折半定理公式. 圖2 和圖3 展示了這兩種方法局部蝶形圖的區別.

圖2 8 點NTT 快速變換DIT 拆分示意圖Figure 2 DIT of 8 points’ fast NTT

圖3 8 點NTT 快速變換DIF 拆分示意圖Figure 3 DIF of 8 points’ fast NTT

對于FFT 來說, 由于離散傅里葉變換和逆變換的對稱性, 正變換和逆變換DIT 的公式結構相同, 正變換和逆變換DIF 的公式結構也相同. 但對于NTT 來說, 正變換和逆變換的公式并不是對稱的(注意式(5)和式(6)中r 的存在), 因此正變換和逆變換的DIT 和DIF 公式各不相同, 我們總共需要推導4 個拆分公式. 設將長度為n 的變換分解為a 個長度為n′的子變換, 則這四個拆分公式分別如式(9)、式(10)、式(11)、式(12)所示, 其推導過程見附錄.

(2) 正變換DIF: 拆分成a 個子變換, 第b 個子變換的輸入值為則有

(4) 逆變換DIF: 拆分成a 個子變換, 第b 個子變換的輸入值為, 則有

反復使用這種變換拆分方法可以將一個數論變換或逆變換拆成數級乘累加結構的蝶形圖. 例如, 長度為45的NTT 變換可以拆成3 個15 點的子變換, 每個子變換又可以拆成3 個5 點的子變換. 這種拆分方法與圖1 所示的基2 快速變換類似, 只不過基2 快速變換每次只拆成兩個子變換, 而復合基快速變換的拆分是根據多項式長度的質因子分解進行拆分. 圖4 給出了一個15 點NTT 用DIT 方式拆分成兩級乘累加結構的蝶形圖(未標注乘加系數). 由于每級乘累加結構的乘法計算量正比于(a ?1)n(n 是多項式總長度, a 是拆分數), 因此我們在選擇多項式長度時需要盡可能選擇能夠分解為較小質因子的值.

圖4 15 點NTT 快速變換DIT 蝶形圖Figure 4 Butterfly chart of DIT of 15 points’ fast NTT

5 效果驗證

使用快速NTT 變換進行多項式環乘法的流程圖如圖5 所示. 該計算過程由兩個正變換、一個逆變換和一個點值乘法組成, 其中點值乘法的復雜度是O(n)(n 為多項式長度). 由于模乘是多項式環乘法中最消耗計算資源的運算單元, 因此我們以模乘數目作為指標來進行性能比對. 首先, 直接法實現的多項式乘法消耗的模乘數目為LM= n2. 基2 快速變換中每個變換花費的模乘數目是2n log2n, 因此總的模乘數目是n+6n log2n. 類似地, 基k 快速變換中每個變換花費的模乘數目是2(k ?1)n logkn. 對于復合基變換來說, 我們構造一個等效底數β, 使其模乘數目滿足通式2(β ?1)n logβn. 這個等效底數與多項式長度的質因子分解有關, 分解出的質因子越大則β 越大. 對于擴域法進行的快速變換, 每個擴域模乘相當于4 個原素數域的模乘(參見第4.1 節). 因此, 使用擴域復合基快速數論變換的多項式乘法花費的模乘數目公式如下:

以LAC 算法的模數251 為例, 表2 中列出了多項式長度N 取不同值時擴域快速變換的加速效果. 可以看出, 擴域法能夠對多項式環乘法的加速起到一定作用. 在加密算法常用的多項式長度范圍內能提供數倍的加速效果, 而在多項式長度取該模數支持的最大值時, 可提供數十倍的效果.

圖5 快速NTT 法實現多項式乘的步驟Figure 5 Steps of polynomial multiplication with fast NTT

表2 模數q=251 時擴域快速NTT 實現多項式乘法的理論加速效果Table 2 Theoretic accelerating effect of fast NTT on extension field with q=251

6 總結

本文探索了小模數多項式乘法使用數論變換進行加速的可行性. 我們設計了一種多項式系數域的擴域方法, 并推導了復合基快速數論變換的拆分公式, 使得小模數多項式乘法也能夠使用快速數論變換來進行加速. 通過編寫代碼驗證, 證明其相比直接法實現的多項式乘, 能夠提供一定的加速效果, 在特定場景下有較好效果.