什么是同態(tài)加密？同態(tài)加密為什么能被稱為密碼學(xué)的圣杯？

同態(tài)加密是一種支持?jǐn)?shù)據(jù)密態(tài)處理的密碼學(xué)技術(shù)，可以廣泛應(yīng)用于云計(jì)算、醫(yī)療、金融等領(lǐng)域。

一、什么是同態(tài)加密

全同態(tài)加密是一種加密技術(shù)，允許在不解密的前提下，對(duì)密文進(jìn)行一些有意義的運(yùn)算，使得解密后的結(jié)果與在明文上做 “相同計(jì)算” 得到的結(jié)果相同。

通常所說(shuō)的 “同態(tài)加法”，“同態(tài)乘法”，指的是明文上的運(yùn)算，即 對(duì)應(yīng)的運(yùn)算

同態(tài)加密被稱為密碼學(xué)的 “圣杯”，原因是同態(tài)加密算法功能十分強(qiáng)大，可以支持密文上的任意操作。

目前的全同態(tài)加密算法效率比較低，只能支持一些簡(jiǎn)單的代數(shù)或邏輯運(yùn)算，對(duì)一些復(fù)雜的計(jì)算邏輯支持較差。

二、理論到實(shí)現(xiàn)

2.1 理論

全同態(tài)加密的思想早在 1978 年由 Rivest，Adleman 和 Dertouzos（前兩位就是 RSA 中的 R 和 A）在他們的論文《On Data Banks and Privacy Homomorphisms》中提出。論文中提出了對(duì)密文進(jìn)行一定的計(jì)算，可以間接地對(duì)原文進(jìn)行操作的構(gòu)想。需要指出的是，這離公鑰密碼學(xué)概念的提出，才僅過(guò)去兩年的時(shí)間，由此也凸顯了密碼大牛的想象力和洞見力。后來(lái)，這種技術(shù)才被重新命名為同態(tài)加密。

傳統(tǒng)的一些密碼方案具有一些簡(jiǎn)單的同態(tài)性質(zhì)，如教科書式的 RSA 算法（支持同態(tài)乘法），Paillier 算法（支持同態(tài)加法）等。然而，這些算法離真正的全同態(tài)加密還有很大的距離。

2.2 方案

經(jīng)過(guò) 30 多年的發(fā)展，Gentry在其博士論文中提出了第一個(gè)真正意義上的全同態(tài)加密方案。該方案基于理想格，利用環(huán)結(jié)構(gòu)上的同態(tài)性質(zhì)設(shè)計(jì)。

全同態(tài)加密方案：
簡(jiǎn)單來(lái)說(shuō)，假如I?RI?R是環(huán)RR的一個(gè)理想，x∈Rx∈R是環(huán)中的任意一個(gè)元素，則xI?IxI?I（吸收律），I+I=II+I=I（封閉性）?？紤]商環(huán)R/IR/I。對(duì)于任意的x,y∈R,x,y∈R,有

這些就是商環(huán)的運(yùn)算性質(zhì)，而性質(zhì)恰好可以用來(lái)構(gòu)造同態(tài)加密。不嚴(yán)格地講，如果把 運(yùn)算想象成 “加密” 過(guò)程，上面實(shí)際上可以翻譯為：

“xx的密文” 與 “yy的密文” 經(jīng)過(guò) “加法” 運(yùn)算 ===》“x+yx+y的密文”

“xx的密文” 與 “yy的密文” 經(jīng)過(guò) “乘法” 運(yùn)算 ===》 “xyxy的密文”

這正是同態(tài)加密所要完成的功能！

然而需要指出的是，這種方案還是只能支持有限次的同態(tài)乘法和同態(tài)加法，離 “任意運(yùn)算” 還是有不小的距離，所以仍然不是一個(gè)真正的全同態(tài)加密方案。因?yàn)樯鲜鲇衫硐敫裨O(shè)計(jì)出的方案本質(zhì)上是基于噪聲的，運(yùn)算過(guò)程中噪聲的規(guī)模會(huì)增長(zhǎng)。當(dāng)噪聲增長(zhǎng)到一定程度后，就不能從密文中將信息恢復(fù)出來(lái)了。Gentry 將這類可以支持一定程度上的同態(tài)加法和同態(tài)乘法的加密方案稱為 “SomeWhat Homomorphic Encryption” （簡(jiǎn)稱為 SHE 或 SWHE） 。

在 Gentry 之前僅有的類似方案是 05 年提出的 BGN 方案。其基于橢圓曲線上的雙線性對(duì)構(gòu)造，可以支持同態(tài)加法和一次同態(tài)乘法因此，為了實(shí)現(xiàn)真正意義上的全同態(tài)加密，Gentry并沒有停下前進(jìn)的腳步。

Gentry 的另一個(gè)貢獻(xiàn)，也是構(gòu)造全同態(tài)加密的關(guān)鍵，那就是提出了 Bootstrapping 技術(shù)：通過(guò)同態(tài)執(zhí)行解密電路（即始終保持在密文狀態(tài)下執(zhí)行解密電路），對(duì)密文進(jìn)行刷新，將其中所含的噪聲減少，使其能夠再進(jìn)行同態(tài)乘法和同態(tài)加法運(yùn)算。通過(guò)重復(fù)執(zhí)行 Bootstrapping， 便可以將 SWHE 方案轉(zhuǎn)化為 FHE 方案。這就是 Gentry 提出的構(gòu)造全同態(tài)加密的藍(lán)圖，也是目前唯一已知的構(gòu)造全同態(tài)加密的方式。

這里有一個(gè)比較有意思的點(diǎn)。前面說(shuō)了 ，SWHE 只能支持有限次的同態(tài)乘法操作，而 Bootstrapping 中需要同態(tài)執(zhí)行解密電路，那么一個(gè)很顯然的推論就是，解密電路中需要執(zhí)行的乘法運(yùn)算不能超過(guò) SWHE 中能支持的同態(tài)乘法的界限，因?yàn)樾枰?SWHE 中實(shí)現(xiàn) Bootstrapping 操作。但是，通過(guò)分析發(fā)現(xiàn)，幾乎所有的可用的加密方案，執(zhí)行其解密電路所需的乘法操作總是超過(guò)了 SWHE 中能支持的同態(tài)乘法的界限。

這個(gè)看似不可逾越的鴻溝，好像給Gentry的同態(tài)加密構(gòu)造藍(lán)圖打上了 “不可能” 的標(biāo)簽。但是 Gentry 通過(guò)引入一些新的計(jì)算假設(shè)，成功地將解密電路中所需的乘法操作拉到 SWHE 能支持的乘法操作范圍內(nèi)。從而成功地構(gòu)造出了第一個(gè)全同態(tài)加密方案。

三、全同態(tài)加密發(fā)展歷程

此后的第二代（BGV 等方案為代表）、第三代（GSW 方案為代表）全同態(tài)加密方案中，都有 Gentry 的貢獻(xiàn)?？梢院敛豢鋸埖卣f(shuō)是Gentry大神敲開了全同態(tài)體系的大門，并在隨后的 14 年中不斷地推動(dòng)「同態(tài)加密算法」的發(fā)展。由于在同態(tài)加密領(lǐng)域的杰出工作，Gentry 獲得了 2022 年的哥德爾獎(jiǎng)。有人預(yù)測(cè)，一旦同態(tài)加密獲得大規(guī)模應(yīng)用，Gentry很可能獲得圖靈獎(jiǎng)。

花邊新聞：Gentry 在哈佛獲得法學(xué)學(xué)位后，曾做過(guò)一段時(shí)間律師。令人津津樂道的跨界成功的教科書式案例，“出道即巔峰” 的典型代表。

從 Gentry 提出第一個(gè)全同態(tài)加密方案開始，全同態(tài)加密算法在設(shè)計(jì)、分析、優(yōu)化、實(shí)現(xiàn)、應(yīng)用等研究方向上都取得了很大的進(jìn)展。而全同態(tài)加密算法本身也經(jīng)歷了輪的 “迭代升級(jí)”。

（關(guān)于下面的分代，學(xué)術(shù)界也存在一些爭(zhēng)議。這里給出其中一種便于我們描述的分代方式，不代表小編的觀點(diǎn)）

噪聲管理是目前全同態(tài)加密方案中的一個(gè)重要部分，很多方案論文中，考慮的關(guān)鍵點(diǎn)就是更好的噪聲管理方式。實(shí)際上，也出現(xiàn)過(guò)一些無(wú)噪聲的 “同態(tài)加密方案”，主要基于非交換代數(shù)設(shè)計(jì)，但是這類方案安全性很低，基本上每出現(xiàn)一個(gè)方案，很快就被攻破了。