隱私計(jì)算與密碼學(xué)
數(shù)據(jù)已經(jīng)成為數(shù)字經(jīng)濟(jì)時(shí)代最重要的生產(chǎn)要素，成為企業(yè)和機(jī)構(gòu)的核心資產(chǎn)，而數(shù)據(jù)價(jià)值的體現(xiàn)則是數(shù)據(jù)的隱私保護(hù)。傳統(tǒng)的面向靜態(tài)數(shù)據(jù)保護(hù)的安全手段已經(jīng)無(wú)法滿足數(shù)據(jù)在跨企業(yè)、跨機(jī)構(gòu)之間流通的需求。
隱私計(jì)算作為新興技術(shù)為數(shù)據(jù)的安全流動(dòng)提供了新的可能性，即使在數(shù)據(jù)融合、計(jì)算的過(guò)程中，也可以保證數(shù)據(jù)的隱私。
密碼學(xué)是隱私計(jì)算技術(shù)一個(gè)重要的方向，其中使用較為廣泛的幾個(gè)領(lǐng)域?yàn)榘踩喾接?jì)算(secure Multi-Party Computation)，同態(tài)加密(Homomorphic Encryption)和零知識(shí)證明(Zero-Knowledge Proof)。這三種密碼學(xué)技術(shù)分別適用于不同的場(chǎng)景，技術(shù)上也有不同的優(yōu)劣勢(shì)，因此在具體的解決方案中往往采用多種技術(shù)的組合，以在不同的環(huán)境下滿足不同的需求。
安全多方計(jì)算(MPC)是由圖靈獎(jiǎng)獲得者姚期智院士于1982年提出的概念。通過(guò)將近40年的發(fā)展，在理論和工程上都得到了長(zhǎng)足的進(jìn)步。以秘密分享（Secret Sharing）、混淆電路（Garbled Circuit）和不經(jīng)意傳輸（Oblivious Transfer）等技術(shù)為主的MPC協(xié)議中（從廣義的概念上來(lái)看，同態(tài)加密和零知識(shí)證明也可以歸于安全多方計(jì)算的范疇），往往網(wǎng)絡(luò)通信上的代價(jià)要大于計(jì)算的代價(jià)。在合適的網(wǎng)絡(luò)條件下基于上述技術(shù)的MPC協(xié)議的實(shí)際性能也能滿足許多實(shí)際的需求。
同態(tài)加密(HE)是Ron Rivest、Leonard Adleman以及Michael L.Dertouzo在1978年提出的概念。與傳統(tǒng)的加密算法的區(qū)別在于，除了加密和解密算法之外，還支持同態(tài)計(jì)算算法——可以在密文上進(jìn)行計(jì)算，計(jì)算后解密可等價(jià)于先解密后計(jì)算。同態(tài)加密具有非常多的應(yīng)用，一個(gè)典型的應(yīng)用就是安全外包計(jì)算，如下圖。由于同態(tài)加密對(duì)于網(wǎng)絡(luò)通信的要求較低，因此也可以做為MPC的一個(gè)組件來(lái)支持不同的協(xié)議。
同態(tài)計(jì)算有多種分類，其中包括加法同態(tài)加密（只能支持加法的同態(tài)操作，比如Paillier）、乘法同態(tài)加密（只能支持乘法的同態(tài)操作，比如ElGamal）、深度受限的同態(tài)加密（可以同時(shí)支持加法和乘法，但是電路的深度有限制，比如BGV/BFV/CKKS/TFHE等）和全同態(tài)加密（可以支持所有的計(jì)算，加法和乘法，同時(shí)深度不受限制，比如BGV/BFV/CKKS/TFHE+Boostrapping）。
全同態(tài)加密（Fully Homomophic Encryption）一直被稱為密碼學(xué)的圣杯，直到2009年才由Craig Gentry給出第一個(gè)基于格理論的方案。此后幾乎所有的全同態(tài)加密方案都是在該框架下進(jìn)行優(yōu)化和改良。在Craig Gentry的開創(chuàng)性工作之上，（全）同態(tài)加密方案在算法性能上有了極大的提升，并且已經(jīng)開始應(yīng)用到隱私機(jī)器學(xué)習(xí)、深度學(xué)習(xí)等領(lǐng)域。
雖然算法上的性能有了很大提高，但是同態(tài)加密的計(jì)算復(fù)雜度仍然非常高。與明文的操作相比，密文同態(tài)的操作要超出4-5個(gè)數(shù)量級(jí)。如何從硬件的角度對(duì)同態(tài)加密算法進(jìn)行加速已經(jīng)成為非常迫切的需求，性能的提升也直接推動(dòng)同態(tài)加密在各類復(fù)雜場(chǎng)景的應(yīng)用。
數(shù)論變換NTT
幾乎現(xiàn)在所有的具備復(fù)雜同態(tài)計(jì)算能力的（全）同態(tài)加密算法都是基于格理論（Lattice）的。其安全性均可基于Learning With Error（LWE）或者Ring Learning With Error（RLWE）這兩類困難問(wèn)題上。
從表現(xiàn)來(lái)看，這類同態(tài)加密算法的基本操作都會(huì)涉及到維數(shù)較大的整系數(shù)多項(xiàng)式的加法和乘法。對(duì)于基本操作的性能提升，可以直接提升整個(gè)加密方案的性能，甚至提升倍數(shù)還具有放大效應(yīng)。
平凡的算法計(jì)算兩個(gè)N次多項(xiàng)式的加法的復(fù)雜度為O(N)，乘法的復(fù)雜度為O(N2)，因此多項(xiàng)式乘法是基本操作中更耗性能一個(gè)操作。為提升多項(xiàng)式乘法的計(jì)算性能，常用的做法是采用數(shù)論變換（Number-Theoretic Transform，NTT），可以將乘法的復(fù)雜度降為O(NlogN)。
NTT實(shí)際上是傅立葉變換（FFT）的一個(gè)變種，其優(yōu)勢(shì)在于可以直接對(duì)整數(shù)進(jìn)行處理，無(wú)需考慮浮點(diǎn)數(shù)中的存儲(chǔ)以及精度問(wèn)題。另外對(duì)大整數(shù)（針對(duì)同態(tài)的場(chǎng)景）的運(yùn)算可以通過(guò)中國(guó)剩余定理轉(zhuǎn)換為多個(gè)獨(dú)立的小素?cái)?shù)的NTT，因此該算法也非常適合FPGA的并行優(yōu)化。
NTT的FPGA加速
NTT中最重要的部分為蝶形運(yùn)算。為在FPGA中實(shí)現(xiàn)蝶形運(yùn)算，矩陣元設(shè)計(jì)專門的處理單元（Processing Element，PE）以及與之匹配的交換網(wǎng)絡(luò)，結(jié)合狀態(tài)機(jī)等組成一個(gè)完整的NTT模塊。多個(gè)NTT模塊通過(guò)連接器（connector）與片外存儲(chǔ)（off chip memory）DDR進(jìn)行交互。除此之外，矩陣元在初版的NTT加速的框架中，進(jìn)行了以下幾點(diǎn)的優(yōu)化：
·驅(qū)動(dòng)層、接口層進(jìn)行了優(yōu)化，使用了QDMA等方法，極大地降低了數(shù)據(jù)在Host端與FPGA端的傳輸耗時(shí)。目前傳輸時(shí)間可只占整個(gè)計(jì)算時(shí)間的70%左右，可以預(yù)期還有持續(xù)優(yōu)化的空間。
·針對(duì)多NTT模組，通過(guò)大量測(cè)試，獲取不同數(shù)量NTT模組并行時(shí)系統(tǒng)的性能數(shù)據(jù)。最后確定了資源占用/性能提升最為合適的模組數(shù)目，矩陣元硬件加速框架目前含有4個(gè)NTT模組，每個(gè)NTT模組含有16個(gè)PE。
·在FPGA端，多NTT模組并行時(shí)對(duì)片外存儲(chǔ)（off chip memory）的操作會(huì)產(chǎn)生讀寫沖突。NTT模組數(shù)目越多，讀寫沖突越嚴(yán)重。矩陣元在這方面也做了相應(yīng)的優(yōu)化處理，減少讀寫沖突。
矩陣元硬件加速框架采用Xilinx Alveo U250加速卡，Host端CPU為Intel(R)Core(TM)i5-6200U CPU 2.30GHz。目前的性能數(shù)據(jù)如下。其中N為多項(xiàng)式維度，模數(shù)為51比特的q=0x7FFFFFFFE0001UL，CPU的NTT實(shí)現(xiàn)使用目前較快的軟件庫(kù)NFLlib：https://github.com/quarkslab/NFLlib
系統(tǒng)資源占用數(shù)據(jù)如下：
LUT:Look-Up Table查找表
LUTRAM:Look-Up Table Random Access Memory查找表內(nèi)存
FF:Flip Flop觸發(fā)器
BRAM:Block Random Access Memory塊內(nèi)存
URAM:Ultra RAM Ultra內(nèi)存
DSP：Digital Signal Processor數(shù)字信號(hào)處理器
整體而言，當(dāng)前版本的NTT計(jì)算FPGA加速倍數(shù)在25倍左右。從目前的狀態(tài)來(lái)看，還可以在算法和工程上繼續(xù)繼續(xù)優(yōu)化，特別是在數(shù)據(jù)傳輸時(shí)間上進(jìn)行優(yōu)化，資源的使用也可進(jìn)一步減少，并行化進(jìn)一步提高等等。
后續(xù)規(guī)劃
NTT只是（全）同態(tài)加密算中最為基礎(chǔ)、最為底層的操作。矩陣元在初版NTT的基礎(chǔ)上將持續(xù)優(yōu)化基礎(chǔ)算子的性能。同時(shí)將逐步實(shí)現(xiàn)更為高階的操作，比如加密、解密和同態(tài)操作，最終實(shí)現(xiàn)對(duì)（全）同態(tài)加密的整體硬件加速支持，并應(yīng)用在隱私機(jī)器學(xué)習(xí)、深度學(xué)習(xí)等同態(tài)加密的相關(guān)場(chǎng)景中，滿足性能要求。最終矩陣元的（全）同態(tài)加密硬件加速將配合Rosetta隱私AI計(jì)算框架，一起提供完備的軟硬一體化解決方案。
