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