一種用于小模數(shù)多項(xiàng)式乘法快速數(shù)論變換的擴(kuò)域方法*

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

1. 北京信息科學(xué)與技術(shù)國(guó)家研究中心, 北京100084

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

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

1 引言

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

使用快速數(shù)論變換進(jìn)行多項(xiàng)式環(huán)乘法時(shí), 多項(xiàng)式及其系數(shù)域的參數(shù)都需要滿足一定條件, 這對(duì)格密碼的設(shè)計(jì)帶來(lái)了很大限制. 要進(jìn)行快速數(shù)論變換, 多項(xiàng)式系數(shù)域的階N 必須滿足N ?1 是多項(xiàng)式長(zhǎng)度的倍數(shù), 因此當(dāng)模數(shù)小于多項(xiàng)式長(zhǎng)度時(shí)(如LAC[4]算法等), 格密碼算法就無(wú)法使用快速數(shù)論變換來(lái)進(jìn)行加速了. 為了解決這一問(wèn)題, 本文設(shè)計(jì)了一種多項(xiàng)式系數(shù)域的擴(kuò)域方法, 使得系數(shù)域的階數(shù)滿足數(shù)論變換的條件, 實(shí)現(xiàn)快速數(shù)論變換來(lái)加速多項(xiàng)式乘法的實(shí)現(xiàn).

本文主要貢獻(xiàn)如下:

(1) 設(shè)計(jì)一種擴(kuò)域構(gòu)造方案, 使小模數(shù)多項(xiàng)式乘法滿足數(shù)論變換的條件.

(2) 基于系數(shù)域擴(kuò)域, 設(shè)計(jì)復(fù)合基快速變換方法實(shí)現(xiàn)快速數(shù)論變換.

(3) 對(duì)R-LWE 體系的格密碼常用的小模數(shù)多項(xiàng)式環(huán)乘法應(yīng)用擴(kuò)域方法, 分析計(jì)算復(fù)雜度, 與未使用快速數(shù)論變換時(shí)的復(fù)雜度進(jìn)行對(duì)比, 論證擴(kuò)域法實(shí)現(xiàn)快速數(shù)論變換的有效性.

2 預(yù)備知識(shí)

2.1 符號(hào)定義

DIT 用于快速數(shù)論變換的時(shí)域抽取分治法

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

2.2 多項(xiàng)式環(huán)乘法

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

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

3 基2 快速數(shù)論變換實(shí)現(xiàn)多項(xiàng)式乘法

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

3.1 多項(xiàng)式的點(diǎn)值表示法與數(shù)論變換

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

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

使用點(diǎn)值表示法進(jìn)行多項(xiàng)式乘時(shí), 自變量取值序列或集合的選擇非常重要. 如果不能通過(guò)適當(dāng)?shù)淖宰兞咳≈敌蛄衼?lái)快速實(shí)現(xiàn)多項(xiàng)式和點(diǎn)值表示法的互相轉(zhuǎn)換, 使用點(diǎn)值表示法進(jìn)行多項(xiàng)式乘就沒(méi)有意義了.R-LWE 體系中多項(xiàng)式系數(shù)是有限域Zp中的元素, 因此利用有限域的性質(zhì)可以尋找一個(gè)Zp上的生成元r 滿足如下條件:

? r2n=1, 其中n 是多項(xiàng)式長(zhǎng)度;

? 當(dāng)0 ≤i,j <2n 且i ?=j 時(shí), ri?=rj.

3.2 使用折半定理實(shí)現(xiàn)快速數(shù)論變換

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

? n=2k, k 為正整數(shù)

? q =n ?C +1, C 為常數(shù)

? q 為素?cái)?shù)同時(shí)滿足這三個(gè)條件的參數(shù)取值組合很有限, 這也是R-LWE 體系算法的設(shè)計(jì)難點(diǎn)之一. 而像LAC 這樣的小模數(shù)R-LWE 算法更是無(wú)法實(shí)現(xiàn)快速數(shù)論變換, 因?yàn)槠淠?shù)小于多項(xiàng)式長(zhǎng)度, 不可能滿足q ?1 是n的倍數(shù)這一條件. 因此, 我們嘗試使用擴(kuò)域方法來(lái)進(jìn)行小模數(shù)多項(xiàng)式乘法的快速數(shù)論變換.

4 本文方法

小模數(shù)多項(xiàng)式乘法不能使用常規(guī)NTT 的原因是多項(xiàng)式系數(shù)域太小而無(wú)法構(gòu)造NTT 變換基, 因此我們可以嘗試構(gòu)造原系數(shù)域的擴(kuò)域, 擴(kuò)大系數(shù)域的階數(shù), 使其滿足條件. 多項(xiàng)式系數(shù)使用擴(kuò)域后, 由于其階N 無(wú)法滿足N ?1 是2 的冪次這一條件, 因此多項(xiàng)式的長(zhǎng)度也無(wú)法構(gòu)造成2 的冪次, 基2 快速變換無(wú)法進(jìn)行. 因此, 我們對(duì)多項(xiàng)式長(zhǎng)度進(jìn)行質(zhì)因子分解, 使用復(fù)合基快速NTT 變換來(lái)達(dá)到與基2 快速變換接近的指數(shù)級(jí)加速效果.

4.1 擴(kuò)域構(gòu)造方法及證明

設(shè)Zq為原多項(xiàng)式的系數(shù)域, 其中q 是一個(gè)小于多項(xiàng)式長(zhǎng)度N 的素?cái)?shù). 按照如下方法構(gòu)造Zq的擴(kuò)域ZPq:

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

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

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

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

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

(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) 依據(jù)ZPq上的乘法定義可知其滿足封閉性.

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

(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中存在一個(gè)子域與Zq同構(gòu). 這里我們?nèi)⊥瑯?gòu)子域?yàn)閆′q= {[a,0]|a ∈Zq}, 同構(gòu)映射為σ(a)=[a,0].

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

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

擴(kuò)域構(gòu)造完成后, 其階必須要大于原系數(shù)域的階, 這樣才能比原系數(shù)域支持更長(zhǎng)的多項(xiàng)式數(shù)論變換.表1 列出了q 取128 至256 之間的素?cái)?shù)時(shí), ZPq域的階數(shù)及生成元r 的參考取值.

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

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

4.2 復(fù)合基快速數(shù)論變換

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

圖2 8 點(diǎn)NTT 快速變換DIT 拆分示意圖Figure 2 DIT of 8 points’ fast NTT

圖3 8 點(diǎn)NTT 快速變換DIF 拆分示意圖Figure 3 DIF of 8 points’ fast NTT

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

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

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

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

圖4 15 點(diǎn)NTT 快速變換DIT 蝶形圖Figure 4 Butterfly chart of DIT of 15 points’ fast NTT

5 效果驗(yàn)證

使用快速NTT 變換進(jìn)行多項(xiàng)式環(huán)乘法的流程圖如圖5 所示. 該計(jì)算過(guò)程由兩個(gè)正變換、一個(gè)逆變換和一個(gè)點(diǎn)值乘法組成, 其中點(diǎn)值乘法的復(fù)雜度是O(n)(n 為多項(xiàng)式長(zhǎng)度). 由于模乘是多項(xiàng)式環(huán)乘法中最消耗計(jì)算資源的運(yùn)算單元, 因此我們以模乘數(shù)目作為指標(biāo)來(lái)進(jìn)行性能比對(duì). 首先, 直接法實(shí)現(xiàn)的多項(xiàng)式乘法消耗的模乘數(shù)目為L(zhǎng)M= n2. 基2 快速變換中每個(gè)變換花費(fèi)的模乘數(shù)目是2n log2n, 因此總的模乘數(shù)目是n+6n log2n. 類似地, 基k 快速變換中每個(gè)變換花費(fèi)的模乘數(shù)目是2(k ?1)n logkn. 對(duì)于復(fù)合基變換來(lái)說(shuō), 我們構(gòu)造一個(gè)等效底數(shù)β, 使其模乘數(shù)目滿足通式2(β ?1)n logβn. 這個(gè)等效底數(shù)與多項(xiàng)式長(zhǎng)度的質(zhì)因子分解有關(guān), 分解出的質(zhì)因子越大則β 越大. 對(duì)于擴(kuò)域法進(jìn)行的快速變換, 每個(gè)擴(kuò)域模乘相當(dāng)于4 個(gè)原素?cái)?shù)域的模乘(參見第4.1 節(jié)). 因此, 使用擴(kuò)域復(fù)合基快速數(shù)論變換的多項(xiàng)式乘法花費(fèi)的模乘數(shù)目公式如下:

以LAC 算法的模數(shù)251 為例, 表2 中列出了多項(xiàng)式長(zhǎng)度N 取不同值時(shí)擴(kuò)域快速變換的加速效果. 可以看出, 擴(kuò)域法能夠?qū)Χ囗?xiàng)式環(huán)乘法的加速起到一定作用. 在加密算法常用的多項(xiàng)式長(zhǎng)度范圍內(nèi)能提供數(shù)倍的加速效果, 而在多項(xiàng)式長(zhǎng)度取該模數(shù)支持的最大值時(shí), 可提供數(shù)十倍的效果.

圖5 快速NTT 法實(shí)現(xiàn)多項(xiàng)式乘的步驟Figure 5 Steps of polynomial multiplication with fast NTT

表2 模數(shù)q=251 時(shí)擴(kuò)域快速NTT 實(shí)現(xiàn)多項(xiàng)式乘法的理論加速效果Table 2 Theoretic accelerating effect of fast NTT on extension field with q=251

6 總結(jié)

本文探索了小模數(shù)多項(xiàng)式乘法使用數(shù)論變換進(jìn)行加速的可行性. 我們?cè)O(shè)計(jì)了一種多項(xiàng)式系數(shù)域的擴(kuò)域方法, 并推導(dǎo)了復(fù)合基快速數(shù)論變換的拆分公式, 使得小模數(shù)多項(xiàng)式乘法也能夠使用快速數(shù)論變換來(lái)進(jìn)行加速. 通過(guò)編寫代碼驗(yàn)證, 證明其相比直接法實(shí)現(xiàn)的多項(xiàng)式乘, 能夠提供一定的加速效果, 在特定場(chǎng)景下有較好效果.