同態(tài)加密是密碼學領域自1978年以來的經(jīng)典難題，也是實現(xiàn)數(shù)據(jù)隱私計算的關(guān)鍵技術(shù)，在云計算、區(qū)塊鏈、隱私計算等領域均存在著廣泛的應用需求和一些可行的應用方案。
本文首先介紹同態(tài)加密的基本概念、研究進展以及標準化進展，然后對主流的乘法/加法半同態(tài)加密算法和全同態(tài)加密算法及其工程實現(xiàn)情況進行概述，最后對同態(tài)加密在各領域的應用場景進行分析。
一、同態(tài)加密概述
1、基本概念
同態(tài)加密（Homomorphic Encryption,HE）是指滿足密文同態(tài)運算性質(zhì)的加密算法，即數(shù)據(jù)經(jīng)過同態(tài)加密之后，對密文進行特定的計算，得到的密文計算結(jié)果在進行對應的同態(tài)解密后的明文等同于對明文數(shù)據(jù)直接進行相同的計算，實現(xiàn)數(shù)據(jù)的“可算不可見”。同態(tài)加密的實現(xiàn)效果如圖1所示。
圖1：同態(tài)加密原理
如果一種同態(tài)加密算法支持對密文進行任意形式的計算，則稱其為全同態(tài)加密（Fully Homomorphic Encryption,FHE）；如果支持對密文進行部分形式的計算，例如僅支持加法、僅支持乘法或支持有限次加法和乘法，則稱其為半同態(tài)加密或部分同態(tài)加密，英文簡稱為SWHE（Somewhat Homomorphic Encryption）或PHE（Partially Homomorphic Encryption）。一般而言，由于任意計算均可通過加法和乘法構(gòu)造，若加密算法同時滿足加法同態(tài)性和乘法同態(tài)性，則可稱其滿足全同態(tài)性。
目前，同態(tài)加密算法已在區(qū)塊鏈、聯(lián)邦學習等存在數(shù)據(jù)隱私計算需求的場景實現(xiàn)了落地應用。由于全同態(tài)加密仍處于方案探索階段，現(xiàn)有算法存在運行效率低、密鑰過大和密文爆炸等性能問題，在性能方面距離可行工程應用還存在一定的距離。因此，實際應用中的同態(tài)加密算法多選取半同態(tài)加密（如加法同態(tài)），用于在特定應用場景中實現(xiàn)有限的同態(tài)計算功能。
2、研究進展
1978年，Rivest、Adleman（“RSA”中的“R”和“A”）和Dertouzos提出了全同態(tài)加密的構(gòu)想[1]，自此成為了密碼學研究領域的一個公開難題。目前，同態(tài)加密算法主要分為半同態(tài)加密和全同態(tài)加密兩大類。半同態(tài)加密主要包括以RSA算法[2]和ElGamal算法[3]為代表的乘法同態(tài)加密、以Paillier算法[4]為代表的加法同態(tài)加密以及以Boneh-Goh-Nissim方案[5]為代表的有限次數(shù)全同態(tài)加密；全同態(tài)加密算法主要包括以Gentry方案[6][7]為代表的第一代方案、以BGV方案[8]和BFV方案[9][10]為代表的第二代方案、以GSW方案[11]為代表的第三代方案以及支持浮點數(shù)近似計算的CKKS方案[12]等等。上述方案及其基本特性和應用情況總覽如表1所示。
表1：各類同態(tài)加密算法
3、標準化進展
（1）半同態(tài)加密標準化
2019年5月，國際標準化組織ISO發(fā)布了同態(tài)加密標準（ISO/IEC 18033-6:2019）。該標準僅涉及半同態(tài)加密，具體包含兩種較為成熟的半同態(tài)加密機制：ElGamal乘法同態(tài)加密和Paillier加法同態(tài)加密，并規(guī)定了參與實體的參數(shù)和密鑰生成、數(shù)據(jù)加密、密文數(shù)據(jù)解密、密文數(shù)據(jù)同態(tài)運算等步驟的具體過程。
（2）全同態(tài)加密標準化
2017年7月，來自學術(shù)界、工業(yè)界和政界的相關(guān)領域研究人員組成了全同態(tài)加密標準化開放聯(lián)盟HomomorphicEncryption.org，在微軟研究院舉辦了首屆全同態(tài)加密標準化研討會，開始共同推進全同態(tài)加密標準草案的編寫工作，并發(fā)布了全同態(tài)加密安全標準、API標準、應用標準三份白皮書。迄今為止，HomomorphicEncryption.org在三年內(nèi)已舉辦五屆全同態(tài)加密標準化會議，參與成員包括微軟、三星SDS、英特爾、IBM、谷歌、萬事達卡等企業(yè)，以及NIST、ITU等機構(gòu)的代表和各大高校的學者。在標準化進展方面，HomomorphicEncryption.org已分別于2018年3月和11月發(fā)布和更新了全同態(tài)加密標準草案。
二、主流同態(tài)加密算法原理
1、半同態(tài)加密算法
滿足有限運算同態(tài)性而不滿足任意運算同態(tài)性的加密算法稱為半同態(tài)加密。典型的半同態(tài)加密特性包括乘法同態(tài)、加法同態(tài)、有限次數(shù)全同態(tài)等。
（1）乘法同態(tài)加密算法
在實際應用中，密文乘法同態(tài)性的需求場景不多，因此乘法同態(tài)性通常偶然存在于已有的經(jīng)典加密算法中。滿足乘法同態(tài)特性的典型加密算法包括1977年提出的RSA公鑰加密算法和1985年提出的ElGamal公鑰加密算法等。
①RSA算法
RSA算法是最為經(jīng)典的公鑰加密算法，至今已有40余年的歷史，其安全性基于大整數(shù)分解困難問題。在實際應用中，RSA算法可采用RSA_PKCS1_PADDING、RSA_PKCS1_OAEP_PADDING等填充模式，根據(jù)密鑰長度（常用1024位或2048位）對明文分組進行填充，而只有不對明文進行填充的原始RSA算法才能滿足乘法同態(tài)特性。由于原始的RSA不是隨機化加密算法，即加密過程中沒有使用隨機因子，每次用相同密鑰加密相同明文的結(jié)果是固定的。因此，利用RSA的乘法同態(tài)性實現(xiàn)同態(tài)加密運算會存在安全弱點，攻擊者可能通過選擇明文攻擊得到原始數(shù)據(jù)。
②ElGamal算法
ElGamal算法是一種基于Diffie-Hellman離散對數(shù)困難問題的公鑰密碼算法，可實現(xiàn)公鑰加密和數(shù)字簽名功能，同時滿足乘法同態(tài)特性。ElGamal是一種隨機化加密算法，即使每次用相同密鑰加密相同明文得到的密文結(jié)果也不相同，因此不存在與RSA算法類似的選擇明文攻擊問題，是ISO同態(tài)加密國際標準中唯一指定的乘法同態(tài)加密算法。
（2）加法同態(tài)加密算法
Paillier算法是1999年提出的一種基于合數(shù)剩余類問題的公鑰加密算法，也是目前最為常用且最具實用性的加法同態(tài)加密算法，已在眾多具有同態(tài)加密需求的應用場景中實現(xiàn)了落地應用，同時也是ISO同態(tài)加密國際標準中唯一指定的加法同態(tài)加密算法。此外，由于支持加法同態(tài)，所以Paillier算法還可支持數(shù)乘同態(tài)，即支持密文與明文相乘。
（3）有限全同態(tài)加密算法
2005年提出的Boneh-Goh-Nissim方案是一種基于雙線性映射的公鑰密碼方案，支持任意次加法同態(tài)和一次乘法同態(tài)運算。方案中的加法同態(tài)基于類似Paillier算法的思想，而一次乘法同態(tài)基于雙線性映射的運算性質(zhì)。由于雙線性映射運算會使得密文所在的群發(fā)生變化，因此僅能支持一次乘法同態(tài)運算，但仍支持對乘法后的密文進一步作加法同態(tài)運算。
2、全同態(tài)加密算法
滿足任意運算同態(tài)性的加密算法稱為全同態(tài)加密。由于任何計算都可以通過加法和乘法門電路構(gòu)造，所以加密算法只要同時滿足乘法同態(tài)和加法同態(tài)特性就稱其滿足全同態(tài)特性。
（1）主流算法
全同態(tài)加密算法的發(fā)展起源于2009年Gentry提出的方案，后續(xù)方案大多基于格代數(shù)結(jié)構(gòu)構(gòu)造。目前已在主流同態(tài)加密開源庫中得到實現(xiàn)的全同態(tài)加密算法包括BGV方案、BFV方案、CKKS方案等。
①第一代全同態(tài)加密方案——Gentry方案
Gentry方案是一種基于電路模型的全同態(tài)加密算法，支持對每個比特進行加法和乘法同態(tài)運算。Gentry方案的基本思想是構(gòu)造支持有限次同態(tài)運算的同態(tài)加密算法并引入“Bootstrapping”方法控制運算過程中的噪音增長，這也是第一代全同態(tài)加密方案的主流模型。“Bootstrapping”方法通過將解密過程本身轉(zhuǎn)化為同態(tài)運算電路，并生成新的公私鑰對對原私鑰和含有噪音的原密文進行加密，然后用原私鑰的密文對原密文的密文進行解密過程的同態(tài)運算，即可得到不含噪音的新密文。但是，由于解密過程本身的運算十分復雜，運算過程中也會產(chǎn)生大量噪音，為了給必要的同態(tài)運算需求至少預留足夠進行一次乘法運算的噪音增長空間，需要對預先解密電路進行壓縮簡化，即將解密過程的一些操作盡量提前到加密時完成。
②第二代全同態(tài)加密方案——BGV/BFV方案
Gentry方案之后的第二代全同態(tài)加密方案通?；贚WE/RLWE假設，其安全性基于代數(shù)格上的困難問題，典型方案包括BGV方案和BFV方案等。
BGV（Brakerski-Gentry-Vaikuntanathan）方案是目前主流的全同態(tài)加密算法中效率最高的方案。在BGV方案中，密文和密鑰均以向量表示，而密文的乘積和對應的密鑰乘積則為張量，因此密文乘法運算會造成密文維數(shù)的爆炸式增長，導致方案只能進行常數(shù)次的乘法運算。BGV方案采用密鑰交換技術(shù)控制密文向量的維數(shù)膨脹，在進行密文計算后通過密鑰交換將膨脹的密文維數(shù)恢復為原密文的維數(shù)。同時，BGV方案可采用模交換技術(shù)替代Gentry方案中的“Bootstrapping”過程，用于控制密文同態(tài)運算產(chǎn)生的噪聲增長，而不需要通過復雜的解密電路實現(xiàn)。因此，在每次進行密文乘法運算后，首先需要通過密鑰交換技術(shù)降低密文的維數(shù)，然后通過模交換技術(shù)降低密文的噪聲，從而能夠繼續(xù)進行下一次計算。
BFV（Brakerski/Fan-Vercauteren）方案是與BGV方案類似的另一種第二代全同態(tài)加密方案，同樣可基于LWE和RLWE構(gòu)造。BFV方案不需要通過模交換進行密文噪聲控制，但同樣需要通過密鑰交換解決密文乘法帶來的密文維數(shù)膨脹問題。
目前，最為主流的兩個全同態(tài)加密開源庫HElib和SEAL分別實現(xiàn)了BGV方案和BFV方案。
③第三代全同態(tài)加密方案——GSW方案
GSW（Gentry-Sahai-Waters）方案是一種基于近似特征向量的全同態(tài)加密方案。該方案基于LWE并可推廣至RLWE，但其的性能不如BGV方案等其他基于RLWE的方案。GSW方案的密文為矩陣的形式，而矩陣相乘并不會導致矩陣維數(shù)的改變，因此GSW方案解決了以往方案中密文向量相乘導致的密文維數(shù)膨脹問題，無需進行用于降低密文維數(shù)的密鑰交換過程。
④浮點數(shù)全同態(tài)加密方案——CKKS方案
CKKS（Cheon-Kim-Kim-Song）方案是2017年提出的一種新方案，支持針對實數(shù)或復數(shù)的浮點數(shù)加法和乘法同態(tài)運算，得到的計算結(jié)果為近似值，適用于機器學習模型訓練等不需要精確結(jié)果的場景。由于浮點數(shù)同態(tài)運算在特定場景的必要性，HElib和SEAL兩個全同態(tài)加密開源庫均支持了CKKS方案。
（2）工程實現(xiàn)
雖然現(xiàn)有的全同態(tài)加密算法在工程實現(xiàn)性能方面存在一定的局限性，但仍有世界頂尖的科技公司對全同態(tài)加密進行了開源實現(xiàn)。目前，最為主流的全同態(tài)加密算法開源工具包括IBM主導的HElib庫和微軟主導的SEAL庫。
①HElib
HElib是一個基于C++語言的同態(tài)加密開源軟件庫，底層依賴于NTL數(shù)論運算庫和GMP多精度運算庫實現(xiàn)，主要開發(fā)者為IBM的Halevi，目前最新版本為1.0.2，實現(xiàn)了支持“Bootstrapping”的BGV方案和基于近似數(shù)的CKKS方案。同時，HElib在上述原始方案中引入了許多優(yōu)化以加速同態(tài)運算，包括Smart-Vercauteren密文打包技術(shù)[13]和Gentry-Halevi-Smart優(yōu)化[14]，提升了算法的整體運行效率。HElib提供了一種“同態(tài)加密匯編語言”，支持“set”、“add”、“multiply”、“shift”等基本操作指令，此外還提供了自動噪聲管理、改進的“Bootstrapping”方法、多線程等功能。目前，HElib支持在Ubuntu、CentOS、macOS等操作系統(tǒng)平臺上進行安裝部署。
2020年5月，IBM在GitHub上開源了基于HElib開發(fā)的面向macOS和iOS操作系統(tǒng)的全同態(tài)加密工具包，提供了基于Xcode的全同態(tài)加密SDK，近期還將發(fā)布面向Linux和Android操作系統(tǒng)的工具包。
②SEAL
SEAL（Simple Encrypted Arithmetic Library，簡單加密運算庫）是微軟密碼學與隱私研究組開發(fā)的開源同態(tài)加密庫，目前最新版本為3.5，支持BFV方案和CKKS方案，項目的參與人員包括CKKS的作者之一Song。SEAL基于C++實現(xiàn)，不需要其他依賴庫，但一些可選功能需要微軟GSL、ZLIB和Google Test等第三方庫的支持。SEAL支持Windows、Linux、macOS、FreeBSD、Android等操作系統(tǒng)平臺，同時支持.NET開發(fā)。與HElib類似，SEAL同樣支持了基于整數(shù)的精確同態(tài)運算和基于浮點數(shù)的近似同態(tài)運算兩類方案，但SEAL依靠微軟的天生優(yōu)勢能夠在Windows系統(tǒng)中進行部署。
在噪聲管理方面，與HElib支持自動噪聲管理不同，在SEAL中每個密文擁有一個特定的噪聲預算量，需要在程序編寫過程中通過重線性化操作自行控制乘法運算產(chǎn)生的噪聲?；赟EAL實現(xiàn)同態(tài)加密運算的性能在很大程度上取決于程序編寫的優(yōu)劣，且存在著不同的優(yōu)化方法，因此總體而言，SEAL的學習和使用難度較大。
由于現(xiàn)有的全同態(tài)加密算法在實際場景中的實用性不高，目前已落地的同態(tài)加密應用中采用的多為Paillier算法等性能較好的加法同態(tài)加密等半同態(tài)加密算法，通過將復雜計算需求以一定方式轉(zhuǎn)化為純加法的形式實現(xiàn)加法同態(tài)加密算法的有效應用。
三、同態(tài)加密應用場景
同態(tài)加密的概念最初提出用于解決云計算等外包計算中的數(shù)據(jù)機密性保護問題，防止云計算服務提供商獲取敏感明文數(shù)據(jù)，實現(xiàn)“先計算后解密”等價于傳統(tǒng)的“先解密后計算”。隨著區(qū)塊鏈、隱私計算等新興領域的發(fā)展及其對隱私保護的更高要求，同態(tài)加密的應用邊界拓展到了更為豐富的領域。
1、經(jīng)典應用場景——云計算
在云計算或外包計算中，用戶為了節(jié)約自身的軟硬件成本，可將計算和存儲需求外包給云服務提供商，利用云服務提供商強大的算力資源實現(xiàn)數(shù)據(jù)的托管存儲和處理。但是，將明文數(shù)據(jù)直接交給云服務器具有一定的安全風險，而傳統(tǒng)的加密存儲方式則無法實現(xiàn)對密文數(shù)據(jù)的直接計算，因此如何同時實現(xiàn)數(shù)據(jù)的機密性和可計算性成為了學術(shù)界的一個難題。同態(tài)加密的出現(xiàn)為這一場景的實現(xiàn)提供了可能性。
在傳統(tǒng)的云存儲與計算解決方案中，用戶需要信任云服務提供商不會竊取甚至泄露用戶數(shù)據(jù)，而基于同態(tài)加密的云計算模型可在根本上解決這一矛盾。首先，用戶使用同態(tài)加密算法和加密密鑰對數(shù)據(jù)進行加密，并將密文發(fā)送給云服務器；云服務器在無法獲知數(shù)據(jù)明文的情況下按照用戶給定的程序?qū)γ芪倪M行計算，并將密文計算結(jié)果返回給用戶；用戶使用同態(tài)加密算法和解密密鑰對密文計算結(jié)果進行解密，所得結(jié)果與直接對明文進行相同計算的結(jié)果等價。
2、在區(qū)塊鏈中的應用
區(qū)塊鏈應用的基本邏輯是將需要存證的信息上鏈，并通過眾多區(qū)塊鏈節(jié)點的驗證和存儲，確保上鏈數(shù)據(jù)的有效性和不可篡改性。例如，在比特幣中，用戶將轉(zhuǎn)賬信息進行廣播，區(qū)塊鏈節(jié)點在進行驗證后將其打包上鏈，保證交易的合法性；在以太坊中，需要依賴區(qū)塊鏈節(jié)點對智能合約的正確執(zhí)行，以實現(xiàn)鏈上信息的統(tǒng)一性和正確性。但是，無論是公有鏈還是聯(lián)盟鏈，直接基于明文信息進行區(qū)塊鏈發(fā)布通常會在泄露一定的敏感數(shù)據(jù)。
基于同態(tài)加密的區(qū)塊鏈應用理論模型如圖2所示。為了保護鏈上信息的隱私性，同時又能實現(xiàn)區(qū)塊鏈節(jié)點對相關(guān)信息的可計算性，可對數(shù)據(jù)進行同態(tài)加密，并將計算過程轉(zhuǎn)化為同態(tài)運算過程，節(jié)點即可在無需獲知明文數(shù)據(jù)的情況下實現(xiàn)密文計算。例如，區(qū)塊鏈底層應用平臺特別是公有鏈平臺大多基于交易模型，可考慮采用加法同態(tài)加密進行支持隱私保護的交易金額計算等操作。
圖2：基于同態(tài)加密的區(qū)塊鏈應用模型
在一般的區(qū)塊鏈隱私保護應用需求中，通常需要同時實現(xiàn)鏈上數(shù)據(jù)的保密性和可驗證性，而同態(tài)加密僅能解決鏈上的密文計算問題。由于私鑰不能公開，且隨機化加密使得密文之間無法比較對應明文值是否相等，單獨依靠同態(tài)加密技術(shù)難以在鏈上實現(xiàn)明文計算結(jié)果的驗證。例如，加法同態(tài)加密雖然可以在保護交易金額和賬戶余額隱私的情況下實現(xiàn)金額的密文計算，但區(qū)塊鏈節(jié)點無法對相關(guān)金額的有效性進行驗證。因此，同態(tài)加密在區(qū)塊鏈場景中的應用需求和應用能力有限，理論上更適合云計算等算力外包場景以及存在多個參與方之間交互計算需求的隱私計算應用。
3、在聯(lián)邦學習中的應用
聯(lián)邦學習的概念最早由谷歌提出，多個參與方可在保證各自數(shù)據(jù)隱私的同時實現(xiàn)聯(lián)合機器學習建模，即在不獲取對方原始數(shù)據(jù)的情況下利用對方數(shù)據(jù)提升自身模型的效果。根據(jù)數(shù)據(jù)融合維度的不同，聯(lián)邦學習主要可分為橫向聯(lián)邦學習和縱向聯(lián)邦學習，分別對應樣本維度的融合和特征維度的融合。目前，聯(lián)邦學習方案可采用同態(tài)加密、秘密分享、不經(jīng)意傳輸?shù)让艽a學手段解決不同階段的安全計算問題。其中，同態(tài)加密主要用于聯(lián)合建模過程中的參數(shù)交互計算過程，實現(xiàn)預測模型的聯(lián)合確立。目前，在聯(lián)邦學習場景中使用較多同態(tài)加密算法為Paillier加法半同態(tài)加密算法。
在該類方案中，一般包含參與方A、參與方B、協(xié)作方C三種角色，參與方A和參與方B為數(shù)據(jù)提供方，而參與方C負責進行密鑰分發(fā)和匯總計算，有時協(xié)作方C也可由兩個參與方之一扮演。由于加法同態(tài)加密無法實現(xiàn)任意形式的計算，在進行聯(lián)合建模時需要事先將擬聯(lián)合計算的計算式近似轉(zhuǎn)換為加法形式，并確定協(xié)議的具體流程。例如，通過泰勒展開將乘法運算轉(zhuǎn)化為多項式相加的形式。聯(lián)合模型的加密訓練過程一般包含以下步驟：
協(xié)作方C生成同態(tài)加密公私鑰對，并向參與方A和B分發(fā)公鑰；
A和B以同態(tài)密文的形式交互用于計算的中間結(jié)果；
A和B將各自的計算結(jié)果匯總給C，C進行匯總計算，并對結(jié)果進行解密；
C將解密后的結(jié)果返回給A和B，雙方根據(jù)結(jié)果更新各自的模型參數(shù)。
在一些基于半同態(tài)加密的聯(lián)邦學習特定方案中，也可無需協(xié)作方C進行模型匯總，參與雙方各自形成一個子模型，在后續(xù)的聯(lián)合預測的過程中需要進行參數(shù)交互。
除以上使用單一密鑰的方法外，目前還存在無需協(xié)作者C的聯(lián)合建模方案，參與計算的兩方各掌握一對公私鑰，但該方案的復雜程度較大，在性能方面不如上述方案。此外，學術(shù)界還提出了多密鑰全同態(tài)加密方案，支持在多方使用不同密鑰加密的密文之間進行同態(tài)計算，但該類方法目前還處于理論階段。
目前，同態(tài)加密在聯(lián)邦學習場景中的應用大多用于聯(lián)合建模過程中的參數(shù)交互過程，避免泄露原始數(shù)據(jù)和直接傳輸明文參數(shù)，可在一定程度上同時解決數(shù)據(jù)融合計算和數(shù)據(jù)隱私保護問題。但是，目前基于加法半同態(tài)加密的解決方案仍存在一定的局限性，包括精度損失、交互開銷大、公平性不足等問題。
四、總結(jié)與建議
目前，全同態(tài)加密算法仍處于以學術(shù)界研究為主的發(fā)展階段，現(xiàn)有方案均存在計算和存儲開銷大等無法規(guī)避的性能問題，距離高效的工程應用還有著難以跨越的鴻溝，同時面臨國際和國內(nèi)相關(guān)標準的缺失。因此，在嘗試同態(tài)加密落地應用時，可考慮利用Paillier加法同態(tài)加密算法等較為成熟且性能較好的半同態(tài)加密算法，解決只存在加法或數(shù)乘同態(tài)運算需求的應用場景，或通過將復雜計算需求轉(zhuǎn)化為只存在加法或數(shù)乘運算的形式實現(xiàn)全同態(tài)場景的近似替代。
