全同態加密屬於密碼學領域。www.emoneybtc.com由於全同態加密支持無需解密，就能夠對密文進行任意計算，因此可以立竿見影的解決數據隱私安全問題，有很大的應用需求。例如，在雲環境下，用戶加密數據後存儲在雲端，由於數據加密使得雲端無法獲得數據的內容，從而保證了數據的隱私。此外，由於是全同態加密，雲端可以對密文數據進行任意計算。總而言之，全同態加密不但通過加密保護了數據，而且沒有喪失計算性。
全同態加密的概念早在1978年就提出，然後一找就是30多年過去了。當然這30多年也沒閒著，30年間人們提出的方案隨後就被證明是不安全的。
當然在這30年間，人們也退而求其次，能做一次加法和一次乘法的也可以，例如c1c2+c3c4，即一個二次多項式。這樣的方案稱為BGN方案。
當然再退而求其次，就是只能做加法，或者只能做乘法，這種方案稱為單同態。例如，RSA就是乘法同態，Paillier就是加法同態。這些方案在有些地方大放異彩，盡管只能做一種同態計算。
直到2009年，Gentry，一個斯坦福大學的博士生，基於理想格提出一個全同態加密方案。Craig Gentry. Fully Homomorphic Encryption Using Ideal Lattices. In the 41st ACM Symposium on Theory of Computing (STOC), 2009. 這篇論文是來自於他的博士論文：Craig Gentry. A Fully Homomorphic Encryption Scheme (Ph.D. thesis).
世界嘩然。各大報紙頭條，密碼學界的突破（Breakthrough），計算機界的突破。英文中Breakthrough可不是隨便用的。
最為湊巧的是，09年左右恰好是雲計算概念火熱的時候。而所有介紹全同態加密的文章開頭都會來一句，全同態加密用在雲計算中可以保護數據隱私安全。誰催化了誰，真的不知道。
Gentry的全同態加密方案是基於理想格構造的。理想格為何物？通俗的說就是一種困難問題，就像大整數難題一樣。
說到這裡，不得不說兩句格密碼。很多人只知道RSA,ECC，但是提起格密碼一臉的茫然與恐懼，覺得格密碼一定是一個很難理解的問題。事實上，恰好相反，所謂的格（Lattice）就是整系數基的線性組合構成的點，通俗地說就是一個空間中的一些離散有規律的點。既然是離散的點，那麼點之間一定有距離，距離產生美，從而產生了一些困難問題，例如：最短向量問題(SVP)。
如果是一個二維平面，那麼尋找在格上尋找最短向量問題是簡單的，但是當維數變大的時候，例如200多維，尋找格上的最短向量問題就變的異常困難，稱之為格上標准困難問題，是一個指數級的困難問題。你可以想象一下，當你在迷宮裡時（現實世界是3維的），找出口還不算很困難，但是當在一個200多維的迷宮裡時，困難程度立刻指數級上升。
最令人感興趣的是，格上標准困難問題至今沒有量子算法可以破解或者撼動它，因此格上標准困難問題被認為是抗量子的。
格上的加密方案最大特征：是一個含有噪音的方案。加密時往裡添加噪音，主要是為了進一步提高安全性。然而恰好是這個噪音，導致加密的形式與解密形式比較簡單。這種特性為構造全同態加密埋下了伏筆。
話還是說回來，繼續說全同態加密，否則講格密碼可以講一千零一夜。那麼30多年人們沒有提出一個全同態加密方案，為什麼Gtentry可以構造出來呢？
因為Gentry發現了一個方法：Boostrapping，該方法我把它稱之為：同態解密。這個方法的作用是約減噪音。因為格上加密法案是噪音方案，即在密文中含有噪音，所以每次密文計算後，噪音都會增加，尤其是密文乘法導致噪音增長的非常快。即使你構造了一個具有同態性的加密方案，由於噪音增長，導致無法獲得同態性。因此，約減密文計算後的噪音變得異常關鍵。當然在此之前應該構造一個具有同態性的方案。
Gentry是在格上首先構造一個具有同態性的加密方案，該方案能夠做加法，也能夠做乘法，但是只能做有限次的乘法。為什麼呢？因為噪音的增長。噪音增長太快，使得無法繼續密文計算。這樣的方案稱為：有限同態加密方案（Somewhat HE）。
如果想做更多的計算，怎麼辦呢？約減噪音，我想連小孩都會的有的常規想法。路線並不新穎，不知道是否讓你失望了。關鍵是怎麼約減？
Gentry觀察到一個現象：如果解密的時候，輸入的不是密文，而是對密文加密後的密文，同樣，不是解密密鑰，而是加密後的密鑰，解密會輸出什麼東西呢？
答案：一個新的密文，該新密文依然是對原明文的加密。最重要的是新密文的噪音總是恆定的。
說到這裡，你反應過來了麼。這意味著每次密文計算後，如果使用同態解密操作，將會輸出一個噪音恆定的新密文，這個新密文可以繼續計算，計算後再同態解密，再計算，周而復始，無窮盡也，所謂任意計算實現了。
把密文再加密，密鑰再加密後，輸入到解密函數中，輸出新的密文，這個方法就是Boostrapping技術，即：同態解密。
Gentry的論文，被號稱是難以理解的。例如上面這個Boostrapping方法，當時我是理解的很久，因為它裡面有很多技術細節。Gentry的博士論文也被號稱沒有幾個人能夠讀懂。但是最後我是讀懂了。
有了同態解密，全同態加密幾乎被構造出來。幾乎是因為Gentry構造的加密方案中，解密電路的深度太深，導致無法同態解密。為此，Gentry又發明出一個方法：壓縮電路，將解密電路的復雜度降低，使得可以同態執行解密電路。你說復雜不復雜。
隨後人們遵循Gentry 的思想提出了整數上的，小主理想上的，而且還進行了實現。但是依然很復雜。
然而，2012年有一個人Brakerski將全同態加密推上了頂峰，使之變的簡單了，而且將全同態加密構件建在LWE問題之上。
LWE問題是一個格上的平均性困難問題，可以被歸約到格上標准困難問題。也是抗量子的。目前主流的格上加密方案都是構建在LWE之上。
由於使用Boostrapping實現任意計算代價太高，而且現實中並不太需要任意計算，所以退而求其次，如果能夠執行多項式深度的同態計算，也是能夠滿足大多數需求的。所以隨後的LWE上的全同態加密不使用Boostrapping技術約減噪音，而是使用其它噪音約減技術，使得能夠進行多項式深度的密文計算，代價大大降低了。
總之，目前只有在格上建立的全同態加密方案是安全的。建立的方法就是首先建立一個有限同態加密方案(SWHE)，然後使用噪音約減技術，使之成為一個能夠執行多項式深度同態計算的方案，稱之為層次型全同態加密。
全同態加密的效率也是飛速提高，目前執行一次乘法在毫秒級，密文與明文之比約為10^2。微軟去年初在人工神經網絡上執行密文計算，效果是令人滿意的。
全同態加密目前處在工程化研究階段，相信全同態加密很快就會進入實踐。