全同態加密釋疑（四）：轉折點：LWE上全同態加密的誕生

01-27

Gentry構造全同態加密方案的思想是非常「規則」的，是按照數學的思維來考慮問題的，就是圍繞理想這一概念，因為只有這樣才能產生密文的加法和乘法算。Gentry第一個全同態加密方案是基於理想格構造的。方案所選擇的代數結構是理想格，是因為在格里解密操作比較簡單，絕大多數都是矩陣向量乘或是內積，它們都屬於NC1，具有低的解密電路複雜度，此外理想格像格一樣具有加法結構，同時它還具有乘法結構的特性，可以說兩全其美。

所有後面沿著Gentry的構造思路都是按照這個思想來的。直到LWE上的全同態加密方案的出現。

Gentry構造全同態加密方案的思想可以抽象概述為：首先在環R上構造一個線性糾錯碼C，「線性」意味著保證加法同態性，「糾錯」意味著碼字中存在錯誤，如果該錯誤在一定範圍內就可以糾錯。而且C是環上的一個理想，其基有兩種表示，一種是「好」的表示，用來做密鑰，可以對大的錯誤進行糾錯（相當於解密），當錯誤超過上限後將無法糾錯（即無法解密）。另外一種表示是「壞」的表示，用來做公鑰，可以產生隨機的碼字，用於加密。由於線性糾錯碼C的線性特性決定了其具有加法同態特性，另外C是環上的一個理想，所以其乘法也具有同態特性，然而由於錯誤存在上限，因此僅對有限次的乘法計算保持其同態特性。該思想形成的方案就是部分（Somewhat）同態加密方案，由於密文計算中錯誤增長的原因，該方案只能對密文進行有限次的運算。最初的方案都可以用這種思想解釋。

上述構造思想中的環結構保證了乘法計算，但是對於LWE（環LWE）上的加密方案由於沒有環結構，所以無法提供密文向量的乘法，一度成為LWE（環LWE）上構造全同態加密的最大障礙。Brakerski在論文Bv11中引入了再線性化技術與維數模約減技術，成功的解決了在沒有環結構的方案中進行密文乘積的問題。後來在BGV方案中經過改進形成了密鑰交換技術和模交換技術。

在基於LWE（環LWE）的全同態加密方案中，密文乘積定義為兩個密文c1和c2的張量c1c2，對應的密鑰為s.

按照這種形式的乘法定義，一方面，密文乘積將導緻密文維數的膨脹，只能進行常數次的密文乘法計算；另一方面，同樣面臨著噪音在乘法中急劇增長的問題。解決這些問題，一方面通過使用密鑰交換技術，可以將密文的維數還原到原來的維數，因此可以進行下一次密文的乘積；另一方面使用模交換技術，可以將增長的噪音約減回原來的噪音大小上。因此，不需要啟動就可以獲得層次型全同態加密方案(可以執行任意多項式深度的電路)，所以不再需要稀疏子集和問題假設和循環安全假設，這是全同態加密思想上的一次飛躍，打破了原有的Gentry構造框架，效率上也得到了極大地提升。目前效率最高的環-LWE上的BGV方案使用的就是這種構造方法