用于全同態(tài)加密的數(shù)論變換乘法蝶形運(yùn)算優(yōu)化及實(shí)現(xiàn)

華斯亮 張惠國 王書昶

(常熟理工學(xué)院 蘇州215500)

1 引言

云計(jì)算為我們提供了一個(gè)巨大的信息處理平臺(tái)，各種信息存儲(chǔ)于網(wǎng)絡(luò)，傳輸于網(wǎng)絡(luò)，處理于網(wǎng)絡(luò)，人們對(duì)數(shù)據(jù)安全和隱私保護(hù)的要求越來越高。如何在保護(hù)數(shù)據(jù)安全和用戶隱私的前提下完成安全計(jì)算，是云計(jì)算亟待解決的一個(gè)實(shí)際問題[1]。同態(tài)加密技術(shù)使人們可以在加密的數(shù)據(jù)中直接進(jìn)行諸如檢索、比較等操作，得出正確的結(jié)果，而在整個(gè)處理過程中無需對(duì)數(shù)據(jù)進(jìn)行解密。其意義在于，真正從根本上解決將數(shù)據(jù)及其操作委托給第三方時(shí)的保密問題[2]。

全同態(tài)加密(Fully Homomorphic Encryption,FHE)可以執(zhí)行任意次同態(tài)加法和同態(tài)乘法操作。許多密碼學(xué)家都將全同態(tài)加密思想置于與公鑰加密思想比肩的重要地位[3]。有研究報(bào)告預(yù)測(cè)，F(xiàn)HE在基因組學(xué)、健康、國家安全和教育等領(lǐng)域具有廣闊的潛在應(yīng)用前景[4]。自2009年Gentry[5]提出第1個(gè)FHE方案至今,全同態(tài)加密取得了長足的發(fā)展，但仍存在諸多的不足，特別是在計(jì)算效率、安全性以及全同態(tài)加密的應(yīng)用等方面。對(duì)于一個(gè)維度僅為2048的格基FHE，需要785006 bit(約10235500)的乘法。通過分析FHE算法的密碼庫中，每個(gè)函數(shù)的分析結(jié)果，計(jì)算的大多數(shù)執(zhí)行時(shí)間是大整數(shù)乘法(包括平方運(yùn)算)，消耗了FHE總執(zhí)行時(shí)間的53%～62%[6]。利用專用硬件加速大整數(shù)乘法，可以較大程度地提高FHE的計(jì)算效率，推進(jìn)FHE的市場(chǎng)化進(jìn)程。

為了加速FHE的運(yùn)算，Wang等人[11]提出用于全同態(tài)加密的大整數(shù)乘法架構(gòu)和實(shí)現(xiàn)。Feng等人[12]提出利用中國余數(shù)定理的雙模數(shù)論變換結(jié)構(gòu)，提升了數(shù)論變換的效率。施佺等人[13]和謝星等人[14]提出了兩級(jí)數(shù)論變換的結(jié)構(gòu)，提高轉(zhuǎn)換并行度。

本文從數(shù)論變換的快速算法出發(fā)，研究操作數(shù)移位后的“零填充”的空位特征，開展了數(shù)論變換乘法蝶形運(yùn)算的優(yōu)化工作。本文首先簡(jiǎn)單介紹數(shù)論變換和庫利–圖基快速變換分解，然后詳細(xì)給出蝶形運(yùn)算操作數(shù)合并算法和取模操作的快速算法，在此基礎(chǔ)上，提出數(shù)論變換基32運(yùn)算單元的硬件設(shè)計(jì)架構(gòu)并設(shè)計(jì)實(shí)現(xiàn)，最后給出了仿真驗(yàn)證的結(jié)果。

2 數(shù)論變換和庫利–圖基快速變換分解

從式(5)的分解可以看出，一個(gè)1048576點(diǎn)的數(shù)論變換可以被分解成4級(jí)基32運(yùn)算單元和旋轉(zhuǎn)因子乘法的運(yùn)算。其中旋轉(zhuǎn)因子可以事先計(jì)算好并存于ROM中，需要使用時(shí)直接讀取即可。基32蝶形運(yùn)算的計(jì)算量占數(shù)論變換乘法的90%以上，它的優(yōu)化對(duì)數(shù)論變換的效率至關(guān)重要。

3 蝶形運(yùn)算的操作數(shù)合并算法

3.1 基32運(yùn)算單元

本文中，蝶形運(yùn)算由基32運(yùn)算單元實(shí)現(xiàn)，基32運(yùn)算單元的計(jì)算如下

由于每個(gè)操作數(shù)中都有128位0，因此可以利用零元素，通過合并兼容的操作數(shù)來減少有效操作數(shù)的數(shù)量，從而可能會(huì)降低CSA樹的級(jí)數(shù)，減少復(fù)雜度和面積。例如，OP11是x11向左移位66 bit，其余位填充0后得到的。OP0和OP11中的有效數(shù)據(jù)位是不重疊的，可以把OP0和OP11組合產(chǎn)生一個(gè)新的操作數(shù)。本文探索了每個(gè)X k的操作數(shù)集合中的固有特征，并提出了一種有效的操作數(shù)歸約算法，以最大限度地減少蝶形運(yùn)算中的有效操作數(shù)。

3.2 操作數(shù)合并算法的提出

使用xn,m的好處是，將xn,m作為基32運(yùn)算單元的基本單元，可以增加合并操作數(shù)的自由度，從而找到一個(gè)減少操作數(shù)的優(yōu)化策略。例如對(duì)于零填充算法，OP0和OP1分別包含了x0和x1，兩操作數(shù)之間是有重疊的，即兩操作數(shù)是無法合并的。但是，如果把xn,m當(dāng)成新的操作數(shù)，x0,0和x1,0就是可以合并的。值得注意的是，x n的分割和xn,m的合并能夠很容易地用硬件實(shí)現(xiàn)，幾乎沒有硬件開銷。

在下節(jié)中，本文將直觀地在硬件上展示系統(tǒng)如何有效地執(zhí)行操作數(shù)合并過程。

3.3 操作數(shù)的分割和合并

根據(jù)以上的算法結(jié)果，如圖1所示，將每個(gè)64 bit輸入數(shù)據(jù)x n，最高2 bit填充0，分割成11個(gè)字，每個(gè)字包含6 bit。對(duì)于X0的特殊情況，操作數(shù)實(shí)際上是對(duì)齊的輸入數(shù)據(jù)。換句話說，每個(gè)操作數(shù)都是從輸入數(shù)據(jù)的11個(gè)連續(xù)字中派生得出的。由于新的96 bit操作數(shù)由16個(gè)字組成，前5個(gè)字被分配為0。

奇數(shù)輸出X1所需要的合并后的操作數(shù)，如圖2所示。合并后共有11個(gè)操作數(shù)，每個(gè)操作數(shù)由32個(gè)不同的輸入數(shù)據(jù)xn,m, 0≤n≤32，使用相同的字索引m, 0≤m<11合并而成。其余奇數(shù)輸出的操作數(shù)合并方法與X1類似，其區(qū)別在于向左循環(huán)移位時(shí)的位數(shù)不同。使用了操作數(shù)合并算法，192 bit的操作數(shù)從32個(gè)減少到了11個(gè)。

表1 操作數(shù)合并算法

對(duì)于偶數(shù)輸出X2，以2個(gè)字為周期合并操作數(shù)，合并后的結(jié)果如圖3所示。這里有兩組操作數(shù)，每組包括6個(gè)合并后的操作數(shù)。第1組包含了OP0至OP5；第2組包括OP6至OP11。每個(gè)新的192 bit操作數(shù)由32個(gè)字組成，它們來自16個(gè)不同的輸入數(shù)據(jù)，每個(gè)輸入數(shù)據(jù)提供兩個(gè)連續(xù)的字。其余除X0,X8,X16和X24以外的偶數(shù)輸出的操作數(shù)合并方法與X2類似，其區(qū)別在于向左循環(huán)移位時(shí)的位數(shù)不同，以及合并字的周期不同。在此情況下，192 bit操作數(shù)的數(shù)量從32減少到12。

對(duì)于偶數(shù)輸出X8，以8個(gè)字為周期合并操作數(shù)。合并后有4組操作數(shù)，每組包括4個(gè)合并后的操作數(shù)。每個(gè)新的192 bit操作數(shù)由32個(gè)字組成，它們來自4個(gè)不同的輸入數(shù)據(jù)，每個(gè)輸入數(shù)據(jù)提供4個(gè)連續(xù)的字。X16和X24的操作數(shù)合并方法與X8類似，其區(qū)別在于向左循環(huán)移位時(shí)的位數(shù)不同，以及合并字的周期不同。在此情況下，192 bit操作數(shù)的數(shù)量從32減少到16。

基32運(yùn)算單元的操作數(shù)合并前后的數(shù)量對(duì)比，如表2所示。基32運(yùn)算單元在合并前需要1024個(gè)操作數(shù)，在合并后僅需要400個(gè)操作數(shù)。

4 取模操作的快速算法

圖1 輸入數(shù)據(jù)x n的 分割

圖2 合并后X 1的操作數(shù)

圖3 合并后X 2的操作數(shù)

表2 基32運(yùn)算單元的操作數(shù)

(3)減法：因?yàn)?96modp=?1，所以x?y ≡x+296y(modp)，其中 296是常數(shù)的乘法系數(shù)。這樣，減法就轉(zhuǎn)換成了上述的乘法和加法，可以較為簡(jiǎn)便地計(jì)算。

特別地，對(duì)于X0的計(jì)算，操作數(shù)相加的中間結(jié)果只有96 bit，其取模操作更為簡(jiǎn)單。

5 硬件實(shí)現(xiàn)

圖4顯示了數(shù)論變換基32運(yùn)算單元的硬件框圖，包括操作數(shù)生成和合并模塊，模加模塊和取模模塊，這些模塊中應(yīng)用了上節(jié)推導(dǎo)的操作數(shù)合并算法和快速取模方法。基32運(yùn)算單元的輸入是32個(gè)64 bit數(shù)據(jù)，輸出是數(shù)論變換后的32個(gè)64 bit數(shù)據(jù)。

操作數(shù)生成和合并模塊主要應(yīng)用操作數(shù)合并算法，根據(jù)輸出序號(hào)的不同，將輸入數(shù)據(jù)切割、擴(kuò)展并合并為：(1)32個(gè)96 bit操作數(shù)，針對(duì)X0；(2)11個(gè)192 bit操作數(shù)，針對(duì)奇數(shù)序列；(3)16個(gè)192 bit操作數(shù)，針對(duì)X8,X16和X24；(4)12個(gè)192 bit操作數(shù)，針對(duì)剩余的偶數(shù)序列。

圖4 數(shù)論變換基32運(yùn)算單元的硬件框圖

圖5 輸入操作數(shù)的模加模塊

因?yàn)楹喜⒑蟮牟僮鲾?shù)數(shù)量不一，共有4種針對(duì)11,12,16和32輸入操作數(shù)的模加模塊，圖5展示了11輸入操作數(shù)和16輸入操作數(shù)的模加模塊。11輸入操作數(shù)和12輸入操作數(shù)加法中，應(yīng)用了192 bit的快速取模方法。X0的32輸入操作數(shù)，因從64 bit填充到了96 bit，其操作數(shù)的加法中間結(jié)果和最終結(jié)果都不會(huì)超過96 bit，加法計(jì)算中不需要取模操作。X8,X16和X24的16輸入操作數(shù)，高32 bit填充了0，其操作數(shù)的加法中間結(jié)果和最終結(jié)果都不會(huì)超過192 bit，加法計(jì)算中也不需要取模操作。

6 實(shí)現(xiàn)結(jié)果

本文提出的用于全同態(tài)加密的1M點(diǎn)數(shù)論變換乘法基32運(yùn)算單元的優(yōu)化算法和架構(gòu)，使用Verilog硬件描述語言編碼，結(jié)合軟件庫NTT Library[15]的結(jié)果進(jìn)行UVM驗(yàn)證。使用Synopsys Design Compiler在SMIC 90 nm RVT 0.9 V Slow工藝下進(jìn)行綜合，電路的最高工作頻率為600 MHz，運(yùn)算需要7個(gè)時(shí)鐘周期，面積為1.714 mm2，功耗202 mW。功耗的99%為動(dòng)態(tài)功耗，與頻率直接相關(guān)。FPGA選用了Xilinx Kintex UltraScale平臺(tái)和Vivado進(jìn)行綜合，電路的最高工作頻率為320 MHz，運(yùn)算需要7個(gè)時(shí)鐘周期，需要38.9k CLB LUTs,23.1k CLB Registers和1.24k CARRY8。為了與其他型號(hào)的FPGA對(duì)比，CLB LUTs可以折合成62.2k logic cells。

本文提出的優(yōu)化算法，可以擴(kuò)展到其他2的冪次方基的運(yùn)算單元上，可將基16和基32運(yùn)算單元的操作數(shù)減少到43.8%和39.1%，由操作數(shù)減少帶來的加法器所占的面積和關(guān)鍵路徑延時(shí)有相應(yīng)的減少。表3是本文結(jié)果與其他工作的對(duì)比。

表3 實(shí)現(xiàn)結(jié)果對(duì)比

7 結(jié)束語

本文利用操作數(shù)移位后的“零填充”的空位，合并數(shù)論變換乘法蝶形運(yùn)算的操作數(shù)，并采用快速取模，分別可將基16和基32運(yùn)算單元的操作數(shù)減少到43.8%和39.1%。在此基礎(chǔ)上，設(shè)計(jì)實(shí)現(xiàn)了數(shù)論變換基32運(yùn)算單元的硬件設(shè)計(jì)架構(gòu)。在SMIC 90 nm工藝下和Xilinx Kintex UltraScale FPGA平臺(tái)上的綜合結(jié)果顯示，電路的最高工作頻率為600 MHz和320 MHz，運(yùn)算需要7個(gè)時(shí)鐘周期，需要的資源分別為芯片面積1.714 mm2，以及38.9k CLB LUTs,23.1k CLB Registers和1.24k CARRY8。實(shí)驗(yàn)結(jié)果表明，該優(yōu)化算法提升了數(shù)論變換乘法蝶形運(yùn)算的計(jì)算效率。