分布式人工智能系統(tǒng)是一個(gè)多學(xué)科交叉領(lǐng)域，從應(yīng)用場(chǎng)景看，其既可以應(yīng)用在數(shù)據(jù)中心做加速，又可以用在聯(lián)邦學(xué)習(xí)領(lǐng)域成為多方共同訓(xùn)練模型的工具。而在這兩個(gè)應(yīng)用場(chǎng)景中，隱私保護(hù)都是必不可少的。近些年同態(tài)加密在隱私保護(hù)領(lǐng)域備受關(guān)注，本文將科普性地介紹什么是同態(tài)加密，以及其在聯(lián)邦學(xué)習(xí)、云計(jì)算領(lǐng)域的應(yīng)用。
1什么是同態(tài)加密
同態(tài)加密（HE，homomorphic encryption）是密碼學(xué)里一種特殊的加密模式，同態(tài)加密使我們可以將加密后的密文發(fā)給任意的第三方進(jìn)行計(jì)算，并且在計(jì)算前不需要解密，即：在密文上進(jìn)行計(jì)算。雖然同態(tài)加密的概念最早出現(xiàn)于30年前，但是第一個(gè)支持在密文上進(jìn)行任意運(yùn)算的全同態(tài)加密框架出現(xiàn)較晚，在2009年由Craig Gentry提出。
同態(tài)加密的數(shù)學(xué)定義為[1]：
其中E為加密算法，M是所有可能信息的集合。如果加密算法E滿足公式(1)，那么我們稱E在★運(yùn)算上符合同態(tài)加密的性質(zhì)。目前的同態(tài)加密算法，主要支持兩種運(yùn)算上的同態(tài)：加法和乘法。
需要注意的是，以上公式(1)只是為了讓我們更加清晰地理解同態(tài)加密的性質(zhì)，實(shí)際中的同態(tài)加密算法可能會(huì)有一些不同。比如Paillier算法對(duì)加法同態(tài)，那么根據(jù)公式(1)，其密文的求和應(yīng)該等于求和后的密文，但實(shí)際情況是密文的乘積等于求和后的密文，所以我們一般只要求得到的密文結(jié)果和我們預(yù)期的計(jì)算相同，但是對(duì)密文上的計(jì)算不作具體要求（一般由加密算法決定）。
2同態(tài)加密的組成與分類
同態(tài)加密算法一般包含以下四個(gè)部分：
KeyGen：密鑰生成算法，產(chǎn)生公鑰和私鑰
Encryption：加密算法
Decryption：解密算法
Homomorphic Property：同態(tài)加密計(jì)算部分
其中前三個(gè)部分在很多加密算法中都可以看到，第四部分則是同態(tài)加密算法的核心，指導(dǎo)密文下的運(yùn)算。
為了更好地理解與運(yùn)用同態(tài)加密算法，我們按照將同態(tài)加密算法支持的運(yùn)算類型和數(shù)量，將其分成3類：部分同態(tài)加密、層次同態(tài)加密、和全同態(tài)加密[1]。
部分同態(tài)加密（Partial HE，簡(jiǎn)稱PHE）指同態(tài)加密算法只對(duì)加法或乘法（其中一種）有同態(tài)的性質(zhì)。例如：RSA加密是最早應(yīng)用的公鑰加密算法框架，同時(shí)RSA算法也是一種PHE算法，其對(duì)乘法有同態(tài)的性質(zhì)。PHE的研究成果出現(xiàn)比較早，并且加法同態(tài)加密算法（Additive HE）比乘法同態(tài)加密算法要多一些。PHE的優(yōu)點(diǎn)是原理簡(jiǎn)單、易實(shí)現(xiàn)，缺點(diǎn)是僅支持一種運(yùn)算（加法或乘法）。
層次同態(tài)加密算法（LHE，Leveled HE或SWHE，SomeWhat HE）一般支持有限次數(shù)的加法和乘法運(yùn)算。層次同態(tài)加密的研究主要分為兩個(gè)階段，第一個(gè)階段是在2009年Gentry提出第一個(gè)FHE框架以前，比較著名的例子有：BGN算法、姚氏混淆電路等；第二個(gè)階段在Gentry FHE框架之后，主要針對(duì)FHE效率低的問題。LHE的優(yōu)點(diǎn)是同時(shí)支持加法和乘法，并且因?yàn)槌霈F(xiàn)時(shí)間比PHE晚，所以技術(shù)更加成熟、一般效率比FHE要高很多、和PHE效率接近或高于PHE，缺點(diǎn)是支持的計(jì)算次數(shù)有限。
全同態(tài)加密算法（Fully HE，簡(jiǎn)稱FHE）支持在密文上進(jìn)行無限次數(shù)的、任意類型的計(jì)算。從使用的技術(shù)上分，F(xiàn)HE有以下類別：基于理想格的FHE方案、基于LWE/RLWE的FHE方案等等。FHE的優(yōu)點(diǎn)是支持的算子多并且運(yùn)算次數(shù)沒有限制，缺點(diǎn)是效率很低，目前還無法支撐大規(guī)模的計(jì)算。
圖1三種類型同態(tài)加密的研究時(shí)間線[1]
圖1展示了三類同態(tài)加密算法的研究時(shí)間線，同態(tài)加密的概念在1976年提出，隨后PHE的研究成果逐漸豐富；在Gentry的FHE框架前，LHE研究占主導(dǎo)；2009年后，研究熱點(diǎn)集中在FHE。
3同態(tài)加密在機(jī)器學(xué)習(xí)中的應(yīng)用
3.1聯(lián)邦學(xué)習(xí)（PHE）
聯(lián)邦學(xué)習(xí)是一種隱私保護(hù)機(jī)器學(xué)習(xí)方法，其主要思想為：構(gòu)建一個(gè)隱私保護(hù)機(jī)器學(xué)習(xí)系統(tǒng)，使得擁有數(shù)據(jù)的多方能夠聯(lián)合訓(xùn)練一個(gè)或多個(gè)模型，并且任意一方的數(shù)據(jù)不會(huì)泄露給其他參與者。這能在保證隱私數(shù)據(jù)不泄露的情況下，提升參與者們本地模型的任務(wù)表現(xiàn)，打破數(shù)據(jù)孤島[2]。
圖2聯(lián)邦學(xué)習(xí)流程示例
在聯(lián)邦學(xué)習(xí)中，多方聯(lián)合訓(xùn)練模型一般需要交換中間結(jié)果，如果直接發(fā)送明文的結(jié)果可能會(huì)有隱私泄露風(fēng)險(xiǎn)。在這種場(chǎng)景下，同態(tài)加密就可以發(fā)揮很重要的作用。多方直接將中間結(jié)果用同態(tài)加密算法進(jìn)行加密，然后發(fā)送給第三方進(jìn)行聚合，再將聚合的結(jié)果返回給所有參與者，不僅保證了中間結(jié)果沒有泄露，還完成了訓(xùn)練任務(wù)（第三方可以通過優(yōu)化系統(tǒng)設(shè)計(jì)去除）。
在聯(lián)邦學(xué)習(xí)中，因?yàn)橹恍枰獙?duì)中間結(jié)果或模型進(jìn)行聚合，一般使用的同態(tài)加密算法為PHE（多見為加法同態(tài)加密算法），例如在FATE中使用的Paillier即為加法同態(tài)加密算法。為了更好地展示同態(tài)加密在聯(lián)邦學(xué)習(xí)中的應(yīng)用，我們?cè)诖苏故疽粋€(gè)同態(tài)加密在聯(lián)邦學(xué)習(xí)推薦系統(tǒng)中的應(yīng)用[3]。
圖3聯(lián)邦矩陣分解推薦系統(tǒng)流程
在傳統(tǒng)的推薦系統(tǒng)中，用戶需要上傳瀏覽記錄、評(píng)價(jià)信息來實(shí)現(xiàn)個(gè)性化推薦，但是這些信息均屬于個(gè)人的隱私數(shù)據(jù)，直接上傳會(huì)帶來很大的安全隱患。在聯(lián)邦推薦系統(tǒng)中，每個(gè)用戶將數(shù)據(jù)保存在本地，只上傳特定的模型梯度。這樣雖然避免了隱私數(shù)據(jù)的直接泄露，但是還是透露了梯度信息給云服務(wù)器。同時(shí)我們發(fā)現(xiàn)，從數(shù)學(xué)上可以證明，使用連續(xù)兩次更新的梯度即可反推出用戶的評(píng)分信息。這種情況下，就必須使用同態(tài)加密對(duì)用戶上傳的梯度進(jìn)行保護(hù)，即用戶在上傳梯度前使用加法同態(tài)加密算法對(duì)梯度信息進(jìn)行加密，然后云服務(wù)器將所有用戶的密文梯度進(jìn)行聚合（相加），再將更新后的模型返還給各個(gè)用戶解密，完成訓(xùn)練更新。
3.2密態(tài)機(jī)器學(xué)習(xí)（LHE and FHE）
除了聯(lián)邦學(xué)習(xí)外，同態(tài)加密另一個(gè)比較重要的應(yīng)用領(lǐng)域是密態(tài)計(jì)算。和聯(lián)邦學(xué)習(xí)不同的是，密態(tài)計(jì)算不需要多方參與，但需要的計(jì)算比聯(lián)邦學(xué)習(xí)更加復(fù)雜（算子多、計(jì)算量大）。密態(tài)計(jì)算中使用的同態(tài)加密算法多為L(zhǎng)HE和FHE。其實(shí)全同態(tài)加密研究的初衷，就是為了實(shí)現(xiàn)安全的云計(jì)算，即對(duì)云算力有需求的用戶可以將本地的數(shù)據(jù)全部加密，然后上傳到云端，然后云端的服務(wù)器即可按照用戶指令完成計(jì)算，整個(gè)過程用戶的數(shù)據(jù)不會(huì)泄露給云端，從而完成“絕對(duì)安全”的云計(jì)算服務(wù)。
但是由于目前FHE效率比較低，所以使用全同態(tài)加密進(jìn)行云計(jì)算遠(yuǎn)遠(yuǎn)沒有達(dá)到應(yīng)用的級(jí)別。機(jī)器學(xué)習(xí)在云計(jì)算中有著廣闊的市場(chǎng)，而機(jī)器學(xué)習(xí)有訓(xùn)練和推理兩種需求，訓(xùn)練過程一般數(shù)據(jù)較多、計(jì)算量很大，而推理則數(shù)據(jù)量相對(duì)較小、計(jì)算量也小，所以目前研究主要集中在密態(tài)下的機(jī)器學(xué)習(xí)推理，并且目前已經(jīng)有速度比較快的方案[4]；而密態(tài)下的機(jī)器學(xué)習(xí)訓(xùn)練研究稀少，是一個(gè)比較難解決的問題。
4部分開源同態(tài)加密庫的效率比較
目前GitHub中有很多的開源HE框架，在這里我們選擇兩個(gè)進(jìn)行測(cè)試比較，一個(gè)是python-paillier，支持加法同態(tài)；一個(gè)是SEAL-CKKS，屬于LHE算法，支持有限次數(shù)的加法和乘法。
表1:Paillier和CKKS的效率對(duì)比（ms）
表1展示了Paillier和CKKS的效率對(duì)比，時(shí)間單位為毫秒，測(cè)試機(jī)器為Intel(R)Xeon(R)E5-2630 24-core 2.6GHz CPU，63GB RAM，表格C+P中的C代表密文、P代表明文。表格中CKKS的key含義為polynomial modulus degree。
從結(jié)果中可以看出，paillier在key size逐漸增大時(shí)，耗時(shí)迅速增長(zhǎng)（速度超過線性），paillier一般使用最少2048位密鑰來保證安全，2048位下的paillier運(yùn)算效率高于CKKS。值得一提的是，SEAL-CKKS支持SIMD操作，所以在機(jī)器學(xué)習(xí)的訓(xùn)練、推理中，可以按照batch size維度對(duì)一批數(shù)據(jù)進(jìn)行打包、加密，使得運(yùn)算效率線性提升。
總結(jié)：在不能夠使用SIMD操作時(shí)（部分機(jī)器學(xué)習(xí)場(chǎng)景可能沒有batch的情況，比如矩陣分解），使用key size比較小的paillier效率更高；在能夠使用SIMD操作時(shí)（例如大部分場(chǎng)景下的機(jī)器學(xué)習(xí)模型訓(xùn)練、推理），SEAL-CKKS效率顯著高于paillier。
參考文獻(xiàn)：
[1]A.Acar et al,"A Survey on Homomorphic Encryption Schemes,"ACM Computing Surveys(CSUR),vol.51,(4),pp.1-35,2018.Available:http://dl.acm.org/citation.cfm?id=3214303.DOI:10.1145/3214303.
[2]Q.Yang et al,"Federated Machine Learning,"ACM Transactions on Intelligent Systems and Technology(TIST),vol.10,(2),pp.1-19,2019.Available:http://dl.acm.org/citation.cfm?id=3298981.DOI:10.1145/3298981.
[3]D.Chai et al,"Secure federated matrix factorization,"arXiv Preprint arXiv:1906.05108,2019.
[4]C.Juvekar,V.Vaikuntanathan and A.Chandrakasan,":A low latency framework for secure neural network inference,"in 27thSecurity Symposium(Security 18),2018,.
