簡述同態加密的發展歷程
前言
深度詳談系列是同態科技面向行業群體推出的專業性文章，旨在分享隱私計算及密碼學相關知識、增強行業群體之間的雙向交互性，打破專業壁壘、使得復雜技術及理論可觸可見。
上一篇的科普文章簡單的介紹了什么是同態加密，本篇文章將詳細梳理同態加密技術的發展脈絡，根據其發展路徑，總結、歸納出同態加密算法的構造類型，討論該技術的應用場景，最后指出其發展方向，對同態加密技術的研究具有指導意義。
01 發展歷程
1978 年，Rivest 等人提出利用同態加密的思想來保護數據信息的安全性，即通過利用具有同態性質的加密函數，對加密數據進行運算，同時保護數據的安全性。
這一概念提出后，引起了眾多密碼專家學者們的關注，由于這個良好的性質，人們可以委托第三方（可信或不可信）處理數據，并根據該思想設計了很多具有同態性質的加密方案。
20世紀80年代，出現了大量的非緊致的同態加密技術，這些方案的構造大多采用了Yao的電路技術。
2005年，Boneh、Goh和 Nissim提出了一個支持任意次加法運算和一次乘法運算的密碼方案，且過程中不會增加密文的噪聲。
2007年，Melchor 等人描述了一種構造加密方案的模版，它能夠計算淺層電路，且密文會隨著乘法深度呈指數增長，而加法不會增長其尺寸。
同態加密算法的構造類型
根據近年來同態加密發展的路徑，現有的同態加密算法的構造思想大致可以分為三類：
- 基于整數或理想格進行構建，以Gentry 等人的工作為代表為代表。
- 基于LWE或R-LWE問題構建，以Brakerski等人的工作為代表。
- 基于LWE問題，以GSW13為代表。
同態加密算法的三種構造類型
1.基于整數或理想格理論來進行構建，需要使用bootstrapping技術來實現全同態加密方案。
2009年，全同態加密的歷史上出現了一個里程碑式的節點，Gentry構造出了世界上第一個全同態加密方案。最初Gentry 的實現采用了理想格，基于理想陪集問題進行設計，現在還有很多方案思想都是源于Gentry的方案。
2010年，Dijk、Gentry及Vaikuntanathan又提出了一個基于整數的全同態加密方案。基于近似最大公因數問題進行設計，原始方案僅僅支持低階多項式的運算。而在使用了早先提出的bootstrapping技術之后，該方案能夠進行密文刷新，從而使得算法能夠支持更深的計算電路。
bootstrapping技術是一種密文的刷新技術，可將任何能夠運算自身解密電路的同態方案轉化成全同態方案，常被用于構造深度為d的全同態加密方案。
bootstrapping技術的原理可以通過黃金操作箱的例子來說明：
A/B黃金操作箱
假設所有的操作箱操作黃金的次數都是有限的，沒有辦法通過操作箱的方式將黃金加工成復雜的工藝品。
現在，為了實現復雜工藝品的加工，有人提出了一個很巧妙的辦法：
如果事先可以知道需要對黃金操作的次數的話，那么通過準備多個箱子，就可以實現更加復雜的操作。
2基于格進行設計，其安全性依賴于LWE以及R-LWE問題，效率上和第一類算法相比，具有極大的提升。
2011年，Brakerski和Vaikuntanathan提出了一個基于標準格上困難問題LWE的同態加密技術。
該方案首次使用標準格上困難問題構造了全同態加密，利用“重線性化”技術，在不引入理想相關假設的條件下，構造了一個部分同態加密方案。
其次，該方案又利用“dimension-modules reduction”技術，縮短同態密文，在不需要”squashing”和稀疏子集合假設的條件下，將部分同態加密方案擴展為全同態加密方案。
2012 年，Brakerski 等人共同構造了 BGV12方案，利用密鑰轉換（Key Switching）技術以解決密文進行乘法運算后的膨脹問題，并利用模轉換（Modulus Switching）技術以抑制密文運算中增長的噪聲，可使 SWHE方案（部分同態加密，支持加法和有限次乘法）方案轉換為層次型同態加密方案（也可近一步使用 bootstrapping 轉化為 FHE 方案）。
這是一個重大的轉折：打破了原有的 Gentry 框架，在效率上有了質的飛躍。在接下來的幾年中，多個密碼學者陸續提出了對同態計算效率進行優化的技術，如將多個明文比特“打包”到一個密文中，以及多個對 bootstrapping 過程進行改進優化的方案。
同年，Brakerski還提出了Bra12方案，在方案中，提出了一個基于LWE問題的同態加密方案的通用噪聲壓縮算法，使得噪聲增長從 縮減為 。
2017年，Cheon等人提出了一個能夠兼容浮點數，并對浮點數進行運算的全同態加密方案CKKS。
Cheon等人使用了一種近似規約技術。在此過程中，明文被近似取整，而密文被截斷（truncates）為若干較小的模數，在解密后進行重組，并被還原為小數。
2019年和2020年，Cheon又提出了針對同態密文的max和min函數計算方法。
3以GSW13為代表，使用特征向量構造全同態加密方案，使用近似特征向量進行構造，計算過程中不再需要計算公鑰。
2013 年，Gentry、Sahai 和 Waters基于 LWE 困難問題構造全同態加密方案GSW13，使用了近似特征向量方法，構造了矩陣形式的層次型同態加密方案。
密文是矩陣形式，且私鑰是密文矩陣的近似特征向量，而明文是相應的特征值。密文的同態乘法和加法分別對應矩陣的乘法和加法，這避免了在之前的方案中，由于密文乘法造成的維數膨脹的問題。
該方案不再需要密鑰轉換技術和模轉換技術，但是在運行效率上低于其他的BGV12 類方案。通過使用特征向量構造全同態加密方案，安全性可以規約到LWE問題上。
在運算時，雖然該方案不再需要運算公鑰，但是計算效率與第二類算法相比，有所降低。
02 前景展望
同態加密技術雖然起步較晚，但是由于其具有可基于密文計算這一特性，因而被廣泛的應用在外包計算、隱私保護機器學習、安全多方計算、聯邦學習以及數據交換共享中，從而吸引了大量的專家學者對其進行研究。
目前，針對同態加密技術的研究主要集中在提升計算速度、縮短密文長度、擴展數據類型以及擴展所支持的操作等方向。
隨著技術的愈發成熟，相信在不久的將來，同態加密一定能夠得到更加廣泛的應用。
參考文獻
[1] Gentry C. Fully Homomorphic Encryption Using Ideal Lattices. In the Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC 2009). Bethesda, MD, USA. May 31-June 2, 2009.
[2] Brakerski, Z. (2012). Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. Advances in Cryptology – CRYPTO 2012:868–886.
[3] Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2012). (Leveled) fully homomorphic encryption without bootstrapping. ACM Trans. Comput. Theory 6, 3, Article 13,2014:13-48.
[4] Van Dijk M, Gentry C, Halevi S, Vaikuntanathan V. Fully homomorphic encryption over the integers. Advances in Cryptology-EUROCRYPT 2010, Springer Berlin Heidelberg, 2010: 24-43.
[5] Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping. Proc of the 3rd Innovations in Theoretical Computer Science Conference. NewYork: ACM, 2012: 309-325.
[6] Gentry C, Halevi S, Smart N P. Better Bootstrapping in Fully Homomorphic Encryption. International Conference on Practice and Theory in Public Key Cryptography. Springer-Verlag, 2012:1-16.
[7] Paillier P. Public-key cryptosystems based on composite degree residuosity classes. EUROCRYPT 1999, 1999, 547(1):223-238.
[8] Cheon, J. H., Kim, A., Kim, M., & Song, Y. Homomorphic Encryption for Arithmetic of Approximate Numbers. Lecture Notes in Computer Science, 2017：409–437.
[9] Brakerski Z, Vaikuntanathan V. Efficient fully homomorphic encryption from (standard) LWE[C]. Proc of the 52nd Annual Symposium on Foundations of Computer Science. Washington DC: IEEE Computer Society, 2011: 97-106.
