同態加密——如何讓幫你幹活的人不知道自己都幹了些什麼

什麼是同態加密

隨著雲計算越來越發達，我們在雲伺服器上進行的計算越來越多。有時候我們需要把一些很私密的數據(比如需要實驗數據，個人信息等)上傳到雲伺服器上進行處理，這時候就存在數據被泄露的風險。

首先來考慮這麼兩個問題：

1. 如何運輸黃金而不被運輸的人把黃金偷走

2. 如何把黃金交給工匠進行加工，而且使得工匠也無法獲得任何黃金

假設我要運輸100g黃金，我只要把這100g黃金鎖在一個保險柜里運輸就可以了。但是如果我想要對這100g黃金進行加工，並且想要使加工黃金的工匠無法獲得黃金，單純的把黃金鎖在保險箱里就不可行了。這個問題的一個解決方法是：

1. 找一個帶手套的保險箱，把黃金鎖在裡面

2. 工匠可以通過保險柜上的手套操作黃金，這樣工匠即能對黃金進行處理又無法竊取黃金

3.打開保險箱，拿出裡面的黃金

和上面的例子相似，為了數據不被泄露，我們可以對數據進行加密。對使用普通加密方法加密得到的密文進行修改，修改後的密文在解密後一般都會變成毫無意義的亂碼。也就是說，我們無法操作加密後的數據。這種性質在一般的信息傳輸中是非常有用的，可以用來判斷信息是否被修改，但是想要對加密後的數據進行運算就非常困難了。為了解決這個問題，人們提出了一種叫做同態加密的加密方法。

什麼是同態加密呢？ 同態加密就是一種能夠讓我們對加密後的內容進行運算，然後用密鑰對運算結果進行解密，解密得到的結果等於加密前的內容經過相同的運算之後的結果。比如把數字3加密之後得到密文A，數字5加密後得到密文B，2 密文A得到的密文解密後得到的結果為6， 密文A+密文B得到的密文解密的結果為8。有了同態加密後，我們就可以把加密後的數據上傳到雲伺服器上，在雲伺服器上進行運算，然後下載運算後的結果，對結果進行解密。這樣就得到了計算結果並且能夠保證數據不被泄露。因為數據是被加密的，所以把加密後的數據公布給所有人也不會發生數據泄露。這樣，我們就可以把計算任務通過區塊鏈眾包給普通用戶。

如果我們有一個加密函數 , 把明文A變成密文A, 把明文B變成密文B，也就是說 ， 。另外我們還有一個解密函數 能夠將 加密後的密文解密成加密前的明文。對於一般的加密函數，如果我們將A和B相加，得到C。我們用 對C進行解密得到的結果一般是毫無意義的亂碼。但是，如果 是個可以進行同態加密的加密函數， 我們對C使用 進行解密得到結果C， 這時候的C = A + B。如果滿足 ， 我們將這種加密函數叫做加法同態，如果滿足 ，我們將這種加密函數叫做乘法同態。如果一個加密函數只滿足加法同態，我們就只能進行加減法運算；如只滿足乘法同態，那麼就只能進行乘除法運算。如果一個同態加密函數同時滿足加法同態和乘法同態，那麼這個使用這個加密函數完成各種加密後的運算(加減乘除、多項式求值、指數、對數、三角函數)。第一個滿足加法和乘法同態的同態加密方法直到2009年才由Craig Gentry提出。

同態加密之所以被稱為同態加密是因為這種加密方法跟抽象代數中的同態很像。在抽象代數中，如果 是兩個交換環，如果函數 使得:

1. , 其中 , 分別是G和H中的幺元
2. 
3. 

均成立，那麼我們把 稱為一個同態(homomorphism)。一般的加密函數都是雙射的，雙射的同態又稱為同構(isomorphism)。所以這麼說來，同態加密被稱為同構加密更加貼切。

全同態加密(Fully Homomorphic Encryption)

2009年，Craig Gentry在論文Fully Homomorphic Encryption Using Ideal Lattices中第一次提出了一種能夠對所有的運算進行同態加密的方法，這也是第一種同時滿足加法同態和乘法同態的加密方法。這裡的全同態指的是給定任意一種運算，可以使用論文中的方法直接構造出對應的同態加密後的運算。使用這種方法甚至可以把需要執行的運算步驟進行加密，也就是說給定要計算的函數 和參數 ，這種方法不僅可以加密參數 ，還可以加密 ，讓計算的執行者無法得知 中都進行了那些計算。

但是這種方法有個致命的缺點，計算複雜度過高。經過這種方法加密後再進行運算需要的時間比直接進行計算需要的時間高兩個數量級。

Somewhat Homomorphic Encryption

與FHE不同，Somewhat Homomorphic Encryption只考慮在幾種常見的運算上進行同態加密，但是這幾種運算的速度都跟直接進行運算的速度在同一量級。只要一個同態加密演算法滿足加同態和乘同態，我們就可以使用泰勒展開式來計算各種函數的值。這種加密方法有很多，以下是幾種比較流行的方法：

• Efficient Homomorphic Encryption on Integer Vectors and Its Applications
• Yet Another Somewhat Homomorphic Encryption (YASHE)
• Somewhat Practical Fully Homomorphic Encryption (FV)
• Fully Homomorphic Encryption without Bootstrapping

其中目前最好的方法是YASHE或者FV.YASHE，但是這兩種方法過於複雜，本文介紹的是第一種加密方案，Efficient Integer Vector。這種方案在整數向量上進行操作，能夠高效的實現整數向量的數乘、加減、內積、線性變換等操作。

Efficient Integer Vector

首先定義一些符號：

• S：代表你的密鑰的矩陣
• c：加密後的整數向量，密文
• x：加密前的整數向量，明文
• ：權重，一個標量，我們用這個值來對輸入的向量進行權重調整，提高信噪比。但是這個值也不能設置的過大，否則可能出現溢出錯誤。
• E/e：額外的隨機雜訊，我們在調整過權重後的明文上加上雜訊，使得兩個在數值上差距不大的向量經過加密後得到的密文也有較大的差距。

接下來我們來看如何加密和解密：

, ， ，

, ，其中 表示把 四捨五入到最近的整數。

因為e相對於 比較小，我們經過舍人之後就消除e的影響。

Addition in Efficient Integer Vector

使用相同的密鑰 對整數向量 和 進行加密得到密文 、 , 即：

如果我們想把 和 相加，只需要把 和 相加即可。公式如下：

所以，對整數向量進行加減法時直接將密文進行加減就可以。

密鑰變換

密鑰變換使得我們可以把原來的密鑰變成我們指定的(滿足某些條件的)其他密鑰。當然，我們也需要對密文進行相應的修改使得修改後的密文用新的密鑰解碼後能夠得到與原來相同的明文。密鑰轉化在許多運算和分析中都十分有用，這將在下文中提及。因為這一步需要對密鑰進行操作，所以只能在本地運行。

假設我們的明文 ，密文 ，密鑰 ，我們想將密鑰換成 ， 相應地，我們需要將密變成 並使得下面公式成立：

為了完成這個工作，我們先把S 和 c 變成中間表示S* 和 c*，然後把S* 和 c*再變成S 和 c。S* 和 c* 是 S 和 c 的二進位表示。通過使用二進位表示，我們可以防止誤差增加過多，保證密文能夠被正確的解密。

第一步：將S, c變換成

設 是c中絕對值最大的一個元素，設 滿足 。我們令 的二進位表示為 ，使得 。例如對於 ，我們將其變為 。如果 是負數，我們取其絕對值的二進位表示，然後將每個 前面加個負號。例如對於 ，我們將其表示為 。然後，我們將 表示為 。例如，取 ，則

然後，我們將 中的每個元素 替換為 。例如將

變成 。

此時 ，所以 。

第二步：計算密鑰變換矩陣

我們接下來計算一個密鑰變換矩陣 ，使得 滿足：

這裡的E是一個隨機噪音矩陣。因為 中的元素乘了 ... 等值，而 沒有乘。所以通過這種方法，我們可以使 中的各個元素保持相對於 中的元素比較小。從而防止誤差過大而解密錯誤。

為了簡單起見，我們將新的密鑰的形式限制為 ， 其中 為m階單位矩陣， 為用戶指定的某個矩陣。

此時，我們可以使 ，其中 是一個隨機的噪音矩陣，但為了保證安全性其中各個元素的絕對值不宜較小。 此時有

用 將 變換為 ，即 。這樣可以得到

線性變換：

設 ，如果想要求 的值，我們可以發現：

所以，我們可以把 認為是 使用密鑰 加密後得到的密文。此時，我們為了保密，可以將密鑰 變成 ，然後在本地計算一個密鑰變換矩陣 ，然後將這個矩陣發送給雲端，在雲端計算 。這時如果用 對 進行解密就可以得到 。

帶權內積：

引理：對於長度為n向量 和n階方陣 ，

，其中 代表將矩陣 的每一行連接起來變成一個向量。

證明如下：

假設有明文 和對應的使用 加密得到的密文 。也就是 ， 。

我們提出如下假設：

使用密鑰 解密密文 得到明文 。也就是說對於某個新的誤差項 :

證明.

首先我們通過令 將其忽略，使用此前的引理，我們可以得到：

我們可以通過選擇一個比較大的 ，使得：

證明了上面的假設之後，我們就可以運用密鑰變換的方法把 變換成其他的密鑰 ，同時使用密鑰變換矩陣 把 變成 即可完成帶權內積。

推薦閱讀：