全同態(tài)加密算法概述

全同態(tài)加密算法概述全同態(tài)加密概述01全同態(tài)加密方案02格密碼03算法性能比較04Content目錄

01

全同態(tài)加密概述全同態(tài)加密全同態(tài)加密屬于密碼學領(lǐng)域。由于全同態(tài)加密支持無需解密，就能夠?qū)γ芪倪M行任意計算，因此可以立竿見影的解決數(shù)據(jù)隱私安全問題，有很大的應用需求。例如，在云環(huán)境下，用戶加密數(shù)據(jù)后存儲在云端，由于數(shù)據(jù)加密使得云端無法獲得數(shù)據(jù)的內(nèi)容，從而保證了數(shù)據(jù)的隱私。此外，由于是全同態(tài)加密，云端可以對密文數(shù)據(jù)進行任意計算?？偠灾瑧B(tài)加密不但通過加密保護了數(shù)據(jù)，而且沒有喪失計算性。02

全同態(tài)加密方案全同態(tài)加密方案全同態(tài)加密的概念早在1978年就提出，然后一找就是30多年過去了。當然這30多年也沒閑著，30年間人們提出的方案隨后就被證明是不安全的。當然在這30年間，人們也退而求其次，能做一次加法和一次乘法的也可以，例如c1c2+c3c4，即一個二次多項式。這樣的方案稱為BGN方案。當然再退而求其次，就是只能做加法，或者只能做乘法，這種方案稱為單同態(tài)。例如，RSA就是乘法同態(tài)，Paillier就是加法同態(tài)。這些方案在有些地方大放異彩，盡管只能做一種同態(tài)計算。直到2009年，Gentry，一個斯坦福大學的博士生，基于理想格提出一個全同態(tài)加密方案。Gentry的全同態(tài)加密方案是基于理想格構(gòu)造的。03

格密碼格密碼說到這里，不得不說兩句格密碼。很多人只知道RSA,ECC，但是提起格密碼一臉的茫然與恐懼，覺得格密碼一定是一個很難理解的問題。事實上，恰好相反，所謂的格（Lattice）就是整系數(shù)基的線性組合構(gòu)成的點，通俗地說就是一個空間中的一些離散有規(guī)律的點。既然是離散的點，那么點之間一定有距離，距離產(chǎn)生美，從而產(chǎn)生了一些困難問題，例如：最短向量問題(SVP)。格密碼如果是一個二維平面，那么尋找在格上尋找最短向量問題是簡單的，但是當維數(shù)變大的時候，例如200多維，尋找格上的最短向量問題就變的異常困難，稱之為格上標準困難問題，是一個指數(shù)級的困難問題。你可以想象一下，當你在迷宮里時（現(xiàn)實世界是3維的），找出口還不算很困難，但是當在一個200多維的迷宮里時，困難程度立刻指數(shù)級上升。04

算法性能比較算法性能比較全同態(tài)加密算法的主要優(yōu)勢是可以針對密文進行操作，仍然可以回復明文，因此，滿足用戶對云服務的基本要求。本文算法與2種全同態(tài)加密算法進行比較（表1）：算法性能比較(1)理想格全同態(tài)加密算法：需要進行矩陣運算和向量模運算（向量的加法和乘法），每加密一個比特都需要進行矩陣和向量運算（表示為連續(xù)性不好），公鑰擴展O(n7)，每個Evaluate中計算門的計算量為O(n6)。(2)整數(shù)全同態(tài)加密算法：需要進行整數(shù)模運算，連續(xù)性好，Evaluate算法中輸入超過本身算法要求，就不會實現(xiàn)全同態(tài)的性質(zhì)，存在攻擊危險。每個