同態加密(HE)是Ron Rivest、Leonard Adleman以及Michael L. Dertouzo在1978年提出的概念。與傳統的加密演算法的區別在於，除了加密和解密演算法之外，還支援同態計算演算法——可以在密文上進行計算，計算後解密可等價於先解密後計算。同態加密具有非常多的應用，一個典型的應用就是安全外包計算，如下圖。由於同態加密對於網路通訊的要求較低，因此也可以做為MPC的一個元件來支援不同的協議。
同態計算有多種分類，其中包括加法同態加密（只能支援加法的同態操作，比如Paillier）、乘法同態加密（只能支援乘法的同態操作，比如ElGamal）、深度受限的同態加密（可以同時支援加法和乘法，但是電路的深度有限制，比如BGV/BFV/CKKS/TFHE等）和全同態加密（可以支援所有的計算，加法和乘法，同時深度不受限制，比如BGV/BFV/CKKS/TFHE + Boostrapping）。
全同態加密（Fully Homomophic Encryption）一直被稱為密碼學的聖盃，直到2009年才由Craig Gentry給出第一個基於格理論的方案。此後幾乎所有的全同態加密方案都是在該框架下進行最佳化和改良。在Craig Gentry的開創性工作之上，（全）同態加密方案在演算法效能上有了極大的提升，並且已經開始應用到隱私機器學習、深度學習等領域。
雖然演算法上的效能有了很大提高，但是同態加密的計算複雜度仍然非常高。與明文的操作相比，密文同態的操作要超出4-5個數量級。如何從硬體的角度對同態加密演算法進行加速已經成為非常迫切的需求，效能的提升也直接推動同態加密在各類複雜場景的應用。
數論變換NTT
幾乎現在所有的具備複雜同態計算能力的（全）同態加密演算法都是基於格理論（Lattice）的。其安全性均可基於Learning With Error（LWE）或者Ring Learning With Error（RLWE）這兩類困難問題上。
從表現來看，這類同態加密演算法的基本操作都會涉及到維數較大的整係數多項式的加法和乘法。對於基本操作的效能提升，可以直接提升整個加密方案的效能，甚至提升倍數還具有放大效應。
平凡的演算法計算兩個N次多項式的加法的複雜度為O(N)，乘法的複雜度為O(N2)，因此多項式乘法是基本操作中更耗效能一個操作。為提升多項式乘法的計算效能，常用的做法是採用數論變換（Number-Theoretic Transform，NTT），可以將乘法的複雜度降為O(NlogN)。
NTT實際上是傅立葉變換（FFT）的一個變種，其優勢在於可以直接對整數進行處理，無需考慮浮點數中的儲存以及精度問題。另外對大整數（針對同態的場景）的運算可以透過中國剩餘定理轉換為多個獨立的小素數的NTT，因此該演算法也非常適合FPGA的並行最佳化。
NTT的FPGA加速
NTT中最重要的部分為蝶形運算。為在FPGA中實現蝶形運算，矩陣元設計專門的處理單元（Processing Element，PE）以及與之匹配的交換網路，結合狀態機等組成一個完整的NTT模組。多個NTT模組透過聯結器（connector）與片外儲存（off chip memory）DDR進行互動。除此之外，矩陣元在初版的NTT加速的框架中，進行了以下幾點的最佳化：
· 驅動層、介面層進行了最佳化，使用了QDMA等方法，極大地降低了資料在Host端與FPGA端的傳輸耗時。目前傳輸時間可只佔整個計算時間的70%左右，可以預期還有持續最佳化的空間。
· 針對多NTT模組，透過大量測試，獲取不同數量NTT模組並行時系統的效能資料。最後確定了資源佔用/效能提升最為合適的模組數目，矩陣元硬體加速框架目前含有4個NTT模組，每個NTT模組含有16個PE。
· 在FPGA端，多NTT模組並行時對片外儲存（off chip memory）的操作會產生讀寫衝突。NTT模組數目越多，讀寫衝突越嚴重。矩陣元在這方面也做了相應的最佳化處理，減少讀寫衝突。
矩陣元硬體加速框架採用Xilinx Alveo U250加速卡，Host端CPU為Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz。目前的效能資料如下。其中N為多項式維度，模數為51位元的q=0x7FFFFFFFE0001UL，CPU的NTT實現使用目前較快的軟體庫NFLlib ：https://github.com/quarkslab/NFLlib
系統資源佔用資料如下：
LUT: Look-Up Table 查詢表
LUTRAM: Look-Up Table Random Access Memory 查詢表記憶體
FF: Flip Flop 觸發器
BRAM: Block Random Access Memory 塊記憶體
URAM: Ultra RAM Ultra 記憶體
DSP：Digital Signal Processor 數字訊號處理器
整體而言，當前版本的NTT計算FPGA加速倍數在25倍左右。從目前的狀態來看，還可以在演算法和工程上繼續繼續最佳化，特別是在資料傳輸時間上進行最佳化，資源的使用也可進一步減少，並行化進一步提高等等。
後續規劃
NTT只是（全）同態加密算中最為基礎、最為底層的操作。矩陣元在初版NTT的基礎上將持續最佳化基礎運算元的效能。同時將逐步實現更為高階的操作，比如加密、解密和同態操作，最終實現對（全）同態加密的整體硬體加速支援，並應用在隱私機器學習、深度學習等同態加密的相關場景中，滿足效能要求。最終矩陣元的（全）同態加密硬體加速將配合Rosetta隱私AI計算框架，一起提供完備的軟硬一體化解決方案。
