2.1 基于同態(tài)加密的安全機(jī)制

同態(tài)加密（HE）的概念最初由Rivest等人在1978年提出^[243]。同態(tài)加密提供了一種對加密數(shù)據(jù)進(jìn)行處理的功能，是一種允許對密文進(jìn)行計(jì)算操作并生成加密結(jié)果的加密技術(shù)。在密文上獲得的計(jì)算結(jié)果被解密后與在明文上的計(jì)算結(jié)果相匹配，就如同對明文執(zhí)行了一樣的計(jì)算操作，該流程如圖2-1所示。

作為一種不需要將密文解密就可以處理密文的方法，同態(tài)加密是目前聯(lián)邦學(xué)習(xí)系統(tǒng)里最常用的隱私保護(hù)機(jī)制，例如橫向聯(lián)邦學(xué)習(xí)里基于同態(tài)加密的安全聚合方法^{[36，284，285]}、基于同態(tài)加密的縱向聯(lián)邦學(xué)習(xí)^{[124，284，285]}、基于同態(tài)加密的聯(lián)邦遷移學(xué)習(xí)^[188]。

同態(tài)加密機(jī)制能夠在不對密文進(jìn)行解密的情況下計(jì)算密文（這樣計(jì)算方就不需要了解明文內(nèi)容，只要獲得密文就可以了），可以很好地保護(hù)敏感數(shù)據(jù)和信息，同時(shí)又可以執(zhí)行計(jì)算操作（例如在加密狀態(tài)下的加減乘除四則運(yùn)算）。也就是說，其他人可以對加密數(shù)據(jù)進(jìn)行處理，但是處理過程不會泄露任何原始內(nèi)容。同時(shí)，擁有解密密鑰的參與方解密處理過的數(shù)據(jù)后，得到的結(jié)果正好是處理相應(yīng)的明文的結(jié)果。

2.1.1 同態(tài)加密的定義

同態(tài)加密方案H是一種通過對密文進(jìn)行有效計(jì)算操作（計(jì)算方不需要獲知解密密鑰），從而允許在加密內(nèi)容上進(jìn)行特定代數(shù)運(yùn)算的加密方案。一個(gè)同態(tài)加密方案H由一個(gè)四元組組成：

各元組表示的含義如下：

? KeyGen表示密鑰生成函數(shù)。對于非對稱同態(tài)加密，一個(gè)密鑰生成元g被輸入KeyGen，并輸出一個(gè)密鑰對{pk，sk}=KeyGen（g），其中pk表示用于對明文進(jìn)行加密的公鑰（public key），sk表示用于對密文進(jìn)行解密的私鑰（secret key）。對于對稱同態(tài)加密，只生成一個(gè)密鑰sk=KeyGen（g），用于加密和解密操作。

? Enc表示加密函數(shù)。對于非對稱同態(tài)加密，一個(gè)加密函數(shù)以公鑰pk和明文m作為輸入，并產(chǎn)生一個(gè)密文c=Enc_pk（m）作為輸出。對于對稱同態(tài)加密，加密過程會使用公共密鑰sk和明文m作為輸入，并生成密文c=Enc_sk（m）。

? Dec表示解密函數(shù)。對于非對稱和對稱同態(tài)加密，私鑰sk和密文c被用來作為計(jì)算相關(guān)明文m=Dec_sk（c）的輸入。

? Eval表示評估函數(shù)。評估函數(shù)Eval將密文c和公共密鑰pk（對于非對稱同態(tài)加密）作為輸入，并輸出與明文對應(yīng)的密文，用于驗(yàn)證加密算法的正確性。

我們用Enc_pk（?）表示使用公鑰pk作為加密密鑰的加密函數(shù)，用M表示明文空間，用C表示密文空間。一個(gè)安全密碼系統(tǒng)若滿足以下條件，則可被稱為同態(tài)的（homomorphic）：

其中，⊙_M和⊙_C分別表示操作符⊙在明文空間M和密文空間C上的運(yùn)算。式（2.2）表示，對于在明文空間M中的任意兩個(gè)元素m₁和m₂，在對它們執(zhí)行運(yùn)算符⊙_M操作后，對得到的結(jié)果進(jìn)行加密，其結(jié)果與m₁和m₂分別先進(jìn)行加密再執(zhí)行運(yùn)算符⊙_C操作的結(jié)果一致；←符號表示左邊項(xiàng)等于或可以直接由右邊項(xiàng)計(jì)算出來，而不需要任何中間解密運(yùn)算。

為了簡化表述，用[[v]] 來表示對明文v的同態(tài)加密結(jié)果。我們來定義同態(tài)加密的兩個(gè)基本操作，即加法同態(tài)加密和乘法同態(tài)加密（這里為了表述的方便，不區(qū)分運(yùn)算符在明文空間和密文空間上的寫法，例如明文加法運(yùn)算+_M和密文加法運(yùn)算+_C，我們統(tǒng)一使用+來表示，乘法運(yùn)算符同理）。

定義2-1 加法同態(tài)運(yùn)算 對于在明文空間M中的任意兩個(gè)元素u和v，其加密結(jié)果分別為[[u]]和[[v]]，滿足：

同理，我們定義乘法同態(tài)加密如下。

定義2-2 乘法同態(tài)運(yùn)算 對于在明文空間M中的任意兩個(gè)元素u和v，其加密結(jié)果分別為[[u]]和[[v]]，滿足：

2.1.2 同態(tài)加密的分類

同態(tài)加密方法可以分為三類：部分同態(tài)加密（Partially Homomorphic Encryp-tion，PHE），些許同態(tài)加密（Somewhat Homomorphic Encryption，SHE），全同態(tài)加密（Fully Homomorphic Encryption，F(xiàn)HE）。不同的同態(tài)加密方案的計(jì)算復(fù)雜度區(qū)別很大。本節(jié)對不同種類的同態(tài)加密方案進(jìn)行簡要的介紹。感興趣的讀者可以查閱文獻(xiàn)[39][30]獲取不同種類的同態(tài)加密方案的更多內(nèi)容。

1.部分同態(tài)加密（PHE）

對于部分同態(tài)加密（也稱為半同態(tài)加密，PHE），（M，⊙_M）和（C，⊙_C）都屬于一個(gè)群。以（C，⊙_C）為例，它滿足下面四個(gè)性質(zhì)。

? 封閉性：即對于任意的兩個(gè)元素c₁，c₂∈C以及操作符⊙_C，滿足（c₁ ⊙_C c₂）∈C。

? 結(jié)合律：即對于任意的三個(gè)元素c₁，c₂，c₃∈C以及操作符⊙_C，滿足（c₁ ⊙_C c₂） ⊙_C c₃=c₁ ⊙_C（c₂ ⊙_C c₃）。

? 單位元：存在C中的一個(gè)元素e，使得對于所有C中的元素a，總有等式（e ⊙_C a）=（a ⊙_C e）=a成立。

? 逆元：對于每個(gè)C中的元素a，總存在C中的一個(gè)元素b，使得總有（a ⊙_C b）=（b ⊙_C a）=1成立。

操作符⊙_C能夠無限次地用于密文。PHE是一種群同態(tài)（group homomorphism）技術(shù)。

加法同態(tài)。若在明文上的運(yùn)算符⊙_M是加法運(yùn)算符，且滿足定義2-1，則該方案可被稱為加法同態(tài)的（additively homomorphic）。Paillier在1999年提出了一種可證的安全加法同態(tài)加密系統(tǒng)^[224]，且對應(yīng)的密文上的運(yùn)算符⊙_C也是加法運(yùn)算符。滿足加法同態(tài)的加密算法一般也滿足標(biāo)量乘法同態(tài)，因?yàn)闃?biāo)量乘法運(yùn)算可以轉(zhuǎn)換為有限次的加法運(yùn)算。

乘法同態(tài)。若在明文上的運(yùn)算符⊙_M是乘法運(yùn)算符，且滿足定義2-2，則該方案被稱為乘法同態(tài)的（multiplicative homomorphic）。文獻(xiàn)[244][96]中分別提出了兩種典型的乘法同態(tài)加密方案，即RSA加密算法和ElGamal加密算法，且對應(yīng)的密文上的運(yùn)算符⊙_C也是乘法運(yùn)算符。

PHE的特點(diǎn)是，要求其加密操作符運(yùn)算只需要滿足加法同態(tài)或者乘法同態(tài)中的一個(gè)即可，不需要兩個(gè)同時(shí)滿足。

2.些許同態(tài)加密（SHE）

些許同態(tài)加密（SHE）是指經(jīng)過同態(tài)加密后的密文數(shù)據(jù)，在其上執(zhí)行的操作（如加法、乘法等）只能是有限的次數(shù)。一些文獻(xiàn)中也定義SHE為只有包含有限數(shù)量的某些電路（如跳轉(zhuǎn)程序^[139]，混淆電路^[289]）能夠支持進(jìn)行任意次數(shù)的運(yùn)算，例如BV^[55]、BGN^[52]和IP^[139]。SHE方案為了安全性使用了噪聲（noise）數(shù)據(jù)。密文上的每一次操作都會增加密文上的噪聲量，而乘法操作是增長噪聲量的主要技術(shù)手段。當(dāng)噪聲量超過一個(gè)上限值之后，解密操作就不能得出正確結(jié)果了。這就是為什么絕大多數(shù)的SHE方案會要求限制計(jì)算操作次數(shù)的原因，正是這些缺點(diǎn)導(dǎo)致它在實(shí)際應(yīng)用中受到很多限制。

3.全同態(tài)加密（FHE）

全同態(tài)加密算法允許對密文進(jìn)行無限次的加法和乘法運(yùn)算操作。我們知道，要實(shí)現(xiàn)任意的函數(shù)計(jì)算，加法和乘法運(yùn)算是僅需的操作，即任意一個(gè)函數(shù)都可以轉(zhuǎn)化為只包含加法和乘法的形式。設(shè)A，B ∈F₂（即取值空間為0，1域），與非門（NAND gate）可以通過公式“1+A×B”計(jì)算得到。由于功能上的完備性，與非門能夠用來構(gòu)建任何邏輯門電路，因此，F(xiàn)HE能夠計(jì)算任何函數(shù)功能。

但值得注意的是，雖然FHE從理論上能夠解決任何函數(shù)的加密計(jì)算問題，但是要設(shè)計(jì)一個(gè)真正意義上的全同態(tài)加密算法是非常困難的，直到2009年才由斯坦福大學(xué)的博士生Craig Gentry提出了世界上第一個(gè)FHE算法^[106]。自此之后，全同態(tài)加密算法的設(shè)計(jì)成為密碼學(xué)的熱門研究方向。從整體上看，F(xiàn)HE算法的設(shè)計(jì)又可以進(jìn)一步分為以下四種^[30]。

? Ideal Lattice-based FHE：基于理想格的全同態(tài)加密，也就是由Gentry設(shè)計(jì)的第一個(gè)全同態(tài)加密算法^[106]。

? Approximate-GCD based FHE：由Van Dijk等人提出的一種全同態(tài)加密方案，與Gentry的實(shí)現(xiàn)相似，該方案的安全性基于AGCD假設(shè)和稀疏子集和假設(shè)^[85]。

? （R）LWE-based FHE：與上面兩種方案相比，該實(shí)現(xiàn)也被稱為第二代全同態(tài)加密技術(shù)，典型的實(shí)現(xiàn)方案見于文獻(xiàn)[193，54]等。與基于理想格的實(shí)現(xiàn)不同，該方案基于（R）LWE構(gòu)造，通過引入再線性化技術(shù)與維數(shù)模約減技術(shù)實(shí)現(xiàn)了乘法的同態(tài)加密，效率比第一代的加密方案有了很大提升。

? 基于近似特征向量技術(shù)實(shí)現(xiàn)的FHE：前面的加密方案都需要借助計(jì)算密鑰的輔助來實(shí)現(xiàn)全同態(tài)加密，但計(jì)算密鑰的大小制約了全同態(tài)加密的性能。為此，在2013年，Gentry等人利用近似特征向量技術(shù)設(shè)計(jì)了無須計(jì)算密鑰的全同態(tài)加密方案GSW^[105]，標(biāo)志著第三代全同態(tài)加密方案的誕生。

當(dāng)前，F(xiàn)HE的研究仍在高速發(fā)展，在高效的自舉算法^{[34，53，89]}、多密鑰全同態(tài)加密^[189]等領(lǐng)域都有許多人在進(jìn)行研究。目前的FHE建立在些許同態(tài)加密（SHE）方法的基礎(chǔ)上，并通過代價(jià)高昂的自助法（bootstrap）操作實(shí)現(xiàn)。由于自助法的代價(jià)高昂，F(xiàn)HE方案計(jì)算十分緩慢且在實(shí)踐中往往并不比傳統(tǒng)的安全多方計(jì)算方法更好，因此，許多研究人員目前正著眼于發(fā)現(xiàn)滿足特定需求的更有效的SHE方案，而非去發(fā)掘FHE方案。