同態加密的實現原理是什麼？在實際中有何應用？

12-29

謝邀。

在Asiancrypt 2015投稿日期之前，想最後回答一個知乎問題，後面要專心學術了哈。既然是半年來的最後一個問題，肯定要選一個合適的。知乎上面被邀請回答了這個問題，正好和我後面要做的研究相關，而且這個問題我自己也已經挖坑很久了。因此，這次算是來填坑了~在回答問題之前，給出一些溫馨提示：

首先，同態加密特別適合在雲計算（Cloud Computing）中得以應用。而知乎er們應該有好多Computer Science專業的同學，而這其中又有很多將致力於雲計算的研究。因此，我的回答會盡量通俗易懂。大家各取所需，其樂融融嘛。當然了，比我水平再高的知乎er們我就沒法呈現更棒的答案了，歡迎幫我補充，同時歡迎一起討論一起研究。我分3個層次進行回答：

概覽和基本概念。這一部分爭取做到大家都能看的很明白，從而多多支持我們的研究，給funding啊！
定義、安全性和簡單實例。這一部分呈現給有一點密碼學基礎，同時對代數學有一定基礎的知乎er們。
安全假設和構造概覽。這一部分呈現給致力於同態加密及其相關研究的知乎er們，做到拋磚引玉的作用。

其次，同態加密的安全模型、構造以及安全性證明，乃至安全性假設，都是密碼學近10年提出的知識。因此現在市面上還沒有相關的教材和比較權威的介紹。所以我的介紹主要來源於：（1）論文；（2）公開課，特別是Bar-Ilan University在2012年組織的Winter School；（3）我自己和導師的交流。我會給出全部資料的鏈接，有興趣的知乎er們可以進行查閱，並進一步進行學習。

最後，一些感謝的話。

感謝幫我畫答案中插圖的楊柳颸同學。她是我的小學同學，好朋友，也是鄰居啦，現在在清華美院讀研究生。考慮到我自己畫圖學術氣息太濃，這次特意請她幫我畫了插圖，水平很高哦！
感謝「知乎密碼學交流群」的全體成員們。自群成立以來，大家一直在群里討論各種密碼學的問題。這個題我說想答，也得到了他們的大力支持。包括 @玄星， @錢宸， @秦飛， @Laughing man， @劉健， @edwardz 等。特別是 @edwardz 同學，現在正在研究Lattice-Based Cryptography，很厲害的！

==============================

一、概覽：同態加密的概念

同態加密（Homomorphic Encryption）是很久以前密碼學界就提出來的一個Open Problem。早在1978年，Ron Rivest, Leonard Adleman, 以及Michael L. Dertouzos就以銀行為應用背景提出了這個概念[RAD78]。對，你沒有看錯，Ron Rivest和Leonard Adleman分別就是著名的RSA演算法中的R和A。至於中間的S，Adi Shamir，現在仍然在為密碼學貢獻新的工作。

什麼是同態加密？

提出第一個構造出全同態加密（Fully Homomorphic Encryption）[Gen09]的Craig Gentry給出的直觀定義最好：

A way to delegate processing of your data, without giving away access to it.

這是什麼意思呢？一般的加密方案關注的都是數據存儲安全。即，我要給其他人發個加密的東西，或者要在計算機或者其他伺服器上存一個東西，我要對數據進行加密後在發送或者存儲。沒有密鑰的用戶，不可能從加密結果中得到有關原始數據的任何信息。只有擁有密鑰的用戶才能夠正確解密，得到原始的內容。我們注意到，這個過程中用戶是不能對加密結果做任何操作的，只能進行存儲、傳輸。對加密結果做任何操作，都將會導致錯誤的解密，甚至解密失敗。

同態加密方案最有趣的地方在於，其關注的是數據處理安全。同態加密提供了一種對加密數據進行處理的功能。也就是說，其他人可以對加密數據進行處理，但是處理過程不會泄露任何原始內容。同時，擁有密鑰的用戶對處理過的數據進行解密後，得到的正好是處理後的結果。

有點抽象？我們舉個實際生活中的例子。有個叫Alice的用戶買到了一大塊金子，她想讓工人把這塊金子打造成一個項鏈。但是工人在打造的過程中有可能會偷金子啊，畢竟就是一克金子也值很多錢的說… 因此能不能有一種方法，讓工人可以對金塊進行加工（delegate processing of your data），但是不能得到任何金子（without giving away access to it）？當然有辦法啦，Alice可以這麼做：

Alice將金子鎖在一個密閉的盒子裡面，這個盒子安裝了一個手套。
工人可以帶著這個手套，對盒子內部的金子進行處理。但是盒子是鎖著的，所以工人不僅拿不到金塊，連處理過程中掉下的任何金子都拿不到。
加工完成後。Alice拿回這個盒子，把鎖打開，就得到了金子。

這個盒子的樣子大概是這樣的：

這裡面的對應關係是：

盒子：加密演算法
盒子上的鎖：用戶密鑰
將金塊放在盒子裡面並且用鎖鎖上：將數據用同態加密方案進行加密
加工：應用同態特性，在無法取得數據的條件下直接對加密結果進行處理
開鎖：對結果進行解密，直接得到處理後的結果

同態加密哪裡能用？

這幾年不是提了個雲計算的概念嘛。同態加密幾乎就是為雲計算而量身打造的！我們考慮下面的情景：一個用戶想要處理一個數據，但是他的計算機計算能力較弱。這個用戶可以使用雲計算的概念，讓雲來幫助他進行處理而得到結果。但是如果直接將數據交給雲，無法保證安全性啊！於是，他可以使用同態加密，然後讓雲來對加密數據進行直接處理，並將處理結果返回給他。這樣一來：

用戶向雲服務商付款，得到了處理的結果；
雲服務商掙到了費用，並在不知道用戶數據的前提下正確處理了數據；

這方法簡直完美啊有沒有？！但是，這麼好的特性肯定會帶來一些缺點。同態加密現在最需要解決的問題在於：效率。效率一詞包含兩個方面，一個是加密數據的處理速度，一個是這個加密方案的數據存儲量。我們可以直觀地想一想這個問題：

工人戴著手套加工金子，肯定沒有直接加工來得快嘛~ 也就是說，隔著手套處理，精準度會變差（現有構造會有誤差傳遞問題），加工的時間也會變得更長（密文的操作花費更長的時間），工人需要隔著操作，因此也需要更專業（會正確調用演算法）。
金子放在盒子裡面，為了操作，總得做一個稍微大一點的盒子吧，要不然手操作不開啊（存儲空間問題）。裡面也要放各種工具吧，什麼電鑽啦，銼刀啦，也需要空間吧？

這種加密方案真的有在研究？

我舉3個簡單的例子：

第一個構造出全同態加密方案的人是Gentry，這是他在Stanford攻讀博士學位的研究成果。Gentry畢業後去哪裡了呢？IBM。大家知道IBM可是一個雲服務提供商啊！在IBM，Gentry和另一個密碼學大牛Halevi繼續進行同態加密及其相關的研究，並實現了一些同態加密方案。如果IBM真的做出了可以在實際使用的同態加密方案，那麼其他雲服務提供商就可以拜拜了啊！這遊戲不用玩了啊，人家能在不知道數據內容得前提下處理數據啊，畢竟誰都不想把數據泄露給其他公司啊！
國內的某個大公司（具體是哪個我就不透露了…）對這方面的研究非常感興趣，我也和他們做了一次交流，並且初步達成了一定的研究大方向。要不怎麼我現在也去弄這個頭大的東西呢。要知道，國內的公司也沒閑著，這是制高點，拿到了就是一家獨大，而且是超級技術壟斷，不公開源代碼或者不了解內部構造的話想仿造都仿造不了啊…不過，這方面的研究說實話Gap確實大，入門起碼要3個月的時間，還不一定做的出來…
即使沒有實現全同態加密，也可以得到其他一些很有趣的結論。而每一個結論都可能引發技術壟斷。這些結論由於涉及到了一定的基礎知識，我在後面中會進行介紹。

業界如何評價全同態加密的構造？

在此引用一個前輩的話：

如果未來真的做出了Practical Fully Homomorphic Encryption，那麼Gentry一定可以得到圖靈獎。

剩下的，我也就不用多說了吧…

==============================

二、同態加密的定義、安全性和簡單實例

下面的內容，如果可以接受符號表述，具有一點密碼學的知識，對抽象代數有一定的了解的話，可能體會的更深刻哦。

同態加密具體如何定義？

我們在雲計算應用場景下面進行介紹：

Alice通過Cloud，以Homomorphic Encryption（以下簡稱HE）處理數據的整個處理過程大致是這樣的：

Alice對數據進行加密。並把加密後的數據發送給Cloud；
Alice向Cloud提交數據的處理方法，這裡用函數f來表示；
Cloud在函數f下對數據進行處理，並且將處理後的結果發送給Alice；
Alice對數據進行解密，得到結果。

據此，我們可以很直觀的得到一個HE方案應該擁有的函數：

KeyGen函數：密鑰生成函數。這個函數應該由Alice運行，用於產生加密數據Data所用的密鑰Key。當然了，應該還有一些公開常數PP（Public Parameter）；
Encrypt函數：加密函數。這個函數也應該由Alice運行，用Key對用戶數據Data進行加密，得到密文CT（Ciphertext）；
Evaluate函數：評估函數。這個函數由Cloud運行，在用戶給定的數據處理方法f下，對密文進行操作，使得結果相當於用戶用密鑰Key對f(Data)進行加密。
Decrypt函數：解密函數。這個函數由Alice運行，用於得到Cloud處理的結果f(Data)。

那麼，f應該是什麼樣子的呢？HE方案是支持任意的數據處理方法f？還是說只支持滿足一定條件的f呢？根據f的限制條件不同，HE方案實際上分為了兩類：

Fully Homomorphic Encryption (FHE)：這意味著HE方案支持任意給定的f函數，只要這個f函數可以通過演算法描述，用計算機實現。顯然，FHE方案是一個非常棒的方案，但是計算開銷極大，暫時還無法在實際中使用。
Somewhat Homomorphic Encryption (SWHE)：這意味著HE方案只支持一些特定的f函數。SWHE方案稍弱，但也意味著開銷會變得較小，容易實現，現在已經可以在實際中使用。

什麼叫做安全的HE？

HE方案的最基本安全性是語義安全性（Semantic Security）。直觀地說，就是密文（Ciphertext）不泄露明文（Plaintext）中的任意信息。這裡密文的意思就是加密後的結果；明文的意思就是原始的數據。如果用公式表述的話，為：

$forall m_0, m_1, extbf{Encrypt}(PK, m_0) approx extbf{Encrypt}(PK, m_1)$

這裡PK代表公鑰（Public Key），是非對稱加密體制中可以公開的一個量。公式中的"約等於"符號，意味著多項式不可區分性，即不存在高效的演算法，可以區分兩個結果，即使已知m0, m1和PK。有人說了，這怎麼可能？我已經知道m0, m1了，我看到加密結果後，對m0或者m1在執行一次加密演算法，然後看哪個結果和給定結果相同不就完了？注意了，加密演算法中還用到一個很重要的量：隨機數。也就是說，對於同樣的明文m進行加密，得到的結果都不一樣，即一個明文可以對應多個密文（many ciphertexts per plaintext）。

在密碼學中，還有更強的安全性定義，叫做選擇密文安全性（Chosen Ciphertext Security）。選擇密文安全性分為非適應性（None-Adaptively）和適應性（Adaptively），也就是CCA1和CCA2。 @一大坨的答案中已經間接提到了，HE方案是不可能做到CCA2安全的。那麼，HE方案能不能做到CCA1安全呢？至今還沒有CCA1安全的FHE方案，但是在2010年，密碼學家們就已經構造出了CCA1的SWHE方案了[LMSV10]。

HE方案還有一方面的安全性，就是函數f是不是也可以保密呢？這樣的話HE就更厲害了！Cloud不僅不能夠得到數據本身的內容，現在連數據怎麼處理的都不知道，只能按照給定的演算法執行，然後返回的結果就是用戶想要的結果。如果HE方案滿足這樣的條件，我們稱這個HE方案具有Function-Privacy特性。不過，僅我個人所了解到的，現在還沒有Function-privacy FHE，甚至Function-privacy SWHE也沒有。

不過，Function-privacy引入了另一個很有趣的概念，那就是我們能不能反過來，就做到Function-privacy，但是不用做到數據隱私呢？這其實也有很好的應用場景：比如一個天才設計了一個演算法（想像Jeffrey Dean設計了歷史上第一個O(1/n)複雜度演算法，或者設計了一個O(n^2)演算法，但是是用來解決旅行商問題的），但是他不想把這個演算法公開。他只提供一個程序，這個程序不泄露任何演算法本身的內容，人們只能調用這個演算法，然後得到輸出的結果。這個特別像什麼？對啦，就是程序的編譯與反編譯嘛。如果Function-privacy的加密設計出來了，那麼計算機科學家們就可以一勞永逸地阻止程序反編譯，甚至連破解都杜絕了。滿足這樣條件的加密方案，即，給演算法加密的方案，叫做Obfuscation。很遺憾，2001年，密碼學家們已經證明，不可能實現嚴格意義上的Obfuscation [BGIRSVY01]。但是，可以做到一個稱為Indistinguishability Obfuscation的東西。這個東西是密碼學家們研究同態加密過程中的一個產物，現在已經有了一些候選方案了[GGHRSB13]。這個就不展開說了，是另一個領域的內容。

舉個SWHE的例子？

在2009年Graig Gentry給出FHE的構造前，很多加密方案都具有Somewhat Homomorphism的性質。實際上，最最經典的RSA加密，其本身對於乘法運算就具有同態性。Elgamal加密方案同樣對乘法具有同態性。Paillier在1999年提出的加密方案也具有同態性，而且是可證明安全的加密方案哦！後面還有很多啦，比如Boneh-Goh-Nissim方案[BGN05], Ishai-Paskin方案等等。不過呢，2009年前的HE方案要不只具有加同態性，要不只具有乘同態性，但是不能同時具有加同態和乘同態。這種同態性用處就不大了，只能作為一個性質，這類方案的同態性一般也不會在實際中使用的。

在此我們看一下Elgamal加密方案，看看怎麼個具有乘同態特性。Elgamal加密方案的密文形式為：

$CT=(C_1, C_2)=(g^r,h^r cdot m)$

其中r是加密過程中選的一個隨機數，g是一個生成元，h是公鑰。如果我們有兩個密文：

$CT_1 = (g^{r_1},h^{r_1} cdot m_1), CT_2 = (g^{r_2},h^{r_2} cdot m_2)$

我們把這兩個密文的第一部分相乘，第二部分相乘，會得到：

$CT= (g^{r_1} cdot g^{r_2},h^{r_1} cdot m_1 cdot h^{r_2} cdot m_2)=(g^{r_1 + r_2}, h^{r_1 + r_2} cdot m_1m_2)$

也就是說，相乘以後的密文正好是m1m2所對應的密文。這樣，用戶解密後得到的就是m1m2的結果了。而且注意，整個運算過程只涉及到密文和公鑰，運算過程不需要知道m1m2的確切值。所以我們說Elgamal具有乘同態性質。但是很遺憾，其沒有加同態性質。

HE的效率如何？

2011年，Gentry和Halevi在IBM嘗試實現了兩個HE方案：Smart-Vercauteren的SWHE方案[SV10]以及Gentry的FHE方案[Gen09]，並公布了效率。結果如何呢？我們給出Gentry公布的數據（原始數據可以在2nd Bar-Ilan Winter School on Cryptography找到）Smart-Vercauteren的SWHE方案效率如下：

看著好像還行，不過這Dimension有點誇張啊…也就是說公鑰很長…那麼，Gentry的FHE方案如何呢？效率如下：

公鑰2.3GB，KeyGen需要2個小時，也是醉了…

==============================

三、現有HE方案的安全假設和構造概覽

如果你致力於HE的研究，我們給出一些可用的資料。

如何證明HE方案的安全性？

對於現在的密碼學方案，安全性證明要把它規約到解決一個公開的困難問題上。簡單地說，就是如果方案被破解了，那麼攻擊者可以用破解演算法解決一個困難問題。然而，由於這個困難問題還沒有找到高效的（多項式複雜度的）演算法，因此方案是安全的。

那麼，2009年以後的HE方案是建立在哪個困難問題上呢？是一個被稱作Learning With Errors（LWE）的困難問題[Reg05]。後來，隨著另一個新的工具出現，密碼學家們又致力於基於Ring Learning With Errors（Ring-LWE）問題的HE構造[LPR10]。

Ring-LWE涉及到抽象代數中Ring以及Ideal的概念，稍顯複雜。我們這裡簡單介紹一下LWE問題，Ring-LWE問題和它有點像。LWE問題分為兩類，一個叫做Search-LWE，一個叫做Decision-LWE。Search-LWE可以簡單地用下圖來表示，其中A是一個m*n的矩陣，由Zp中的元素組成；s是一個n維向量；e是一個m維向量；b是一個m維向量：

這個問題大致為：選擇一個秘密（secret）值s，並選擇一個範數很小的擾亂（error）向量e，計算b = As + e mod q。這個問題是：只給定矩陣A和計算的結果b（圖中紅色部分），不給定s和e（途中藍色部分），反過來求秘密值s的大小。Decision-LWE問題有點類似：給定A和b，演算法需要判斷，b是由某個s通過As + e計算得來的呢，還是就是一個隨機量呢？這裡有幾個小問題：

m和n有多大？這取決於我們要求安全度有多高了。實際上這還取決於一些其他因素。
e的範數要多麼小？LWE要求e的取值要滿足離散高斯分布（Discrete Gaussian Distribution）。
怎麼想到的這麼個問題？實際上，LWE問題是Lattice中的一個問題。Lattice是什麼呢？這個展開說就有點累了…

如果知乎er們想了解更多有關Abstract Algebra，Lattice，以及LWE的內容，下面的三個材料是可以閱讀的：

Harvard Extension School的Abstract Algebra課程。這門課可以幫助快速入門Abstract Algebra。當然了，這可是Harvard學生的本科課程哦。Abstract Algebra
2nd Bar-Ilan Winter School on Cryptography。Bar-llan大學自2011年開始每年都組織一次密碼學的Winter School，請的都是大牛啊！2012年的主題是Lattice-Based Cryptography，2013年的主題是Pairing-Based Cryptography。2015年2月，新的一輪Winter School就開始了，知乎上 @劉健同學要去聽的哦，羨慕嫉妒恨呢！2nd Bar-Ilan Winter School on Cryptography
Oded Regev的Lecture Notes on Lattice。Regev是誰？是他提出的LWE和Ring-LWE，所以他課程的材料當然有價值一聽。Lattices in Computer Science (Fall 2009)

介紹一下構造FHE的思路？

FHE最重要的一點是Fully，就是說要支持任意的函數f。因此我們也可以很明顯看出，想要構造FHE，就需要了解計算機是如何計算的。一般來說，我們有兩種思路：

從計算機原理考慮。計算機無論做何種運算，歸根到底都是位運算。那麼，計算機至少要支持哪些位運算，才能夠支持所有的運算呢？實際上，一個計算機只要支持邏輯與運算（AND），以及異或運算（XOR），那麼這個計算機理論上就可以實現計算機的其他運算了（我們稱之為圖靈完備性，Turing Completeness）
從抽象代數考慮。我們只需要加法和乘法就可以完成全部運算了。但其實更嚴格的說，只要我們在一個域（Field）上構造HE，理論上我們就可以支持所有的f。

基於LWE問題的FHE只能針對1 bit進行加密，因此現在的構造都是從計算機原理考慮。也就是在bit的層面上實現FHE方案，或者更嚴謹地說，從電路層（Circuit）實現FHE方案。具體構造呢，大家刻意參考下面給出的參考文獻了。實話實說，我自己也沒有都消化，或者更嚴格地說，Regev的LWE構造論文我還沒有完全看明白。因此，我在此也號召密碼學愛好者一起研究啦~

==============================

以上。

==============================

參考文獻

[RAD78] Ron Rivest, Leonard Adleman, and Michael L. Dertouzos. On data banks and privacy homomorphisms. Foundations of Secure Computation, 1978.

[Gen09] Craig Gentry. Fully homomorphic encryption using ideal lattices. STOC 2009. Also, see 「A fully homomorphic encryption scheme」, PhD thesis, Stanford University, 2009.

[LMSV10] Jake Loftus, Alexander May, Nigel P. Smart, and Frederik Vercauteren. On CCA-Secure Fully Homomorphic Encryption. Cryptology ePrint Archive 2010/560.

[BGIRSVY01] Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Key Yang. On the (Im)possibility of Obfuscating Programs. Crypto 2001.

[GGHRSB13] Sanjam Garg, CraigGentry, Shai Halevi, MarianaRaykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. Foundations of Computer Science, 2013.

[Paillier99] Pascal Paillier. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. Eurocrypt 1999.

[BGN05] Dan Boneh, Eu-Jin Goh, and Kobbi Nissim. Evaluating 2-DNF formulas on ciphertexts. TCC 2005.

[GH11a] Craig Gentry and Shai Halevi. Implementing gentry』s fully-homomorphic encryption scheme. Eurocrypt 2011.

[SV10] Nigel P. Smart and Frederik Vercauteren. Fully homomorphic encryption with relatively small key and ciphertext sizes. PKC 2010.

[Reg05] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. STOC 2005.

[LPR10] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. Eurocrypt 2010.

雲計算與同態

看了前面的回答感覺大家繞的好遠……只問問概念不用提那麼多……

假設有個function E滿足

E(a)+E(b)= E(a + b)

E(a) * E(b) = E(a*b)

那麼這就叫全同態,滿足期中之一就是半同態，加密就是那個E，解密就理解為

如果F(a ) = x

D(x)= a

整個加密E和解密D就是全同態加密，其中還有公匙，私匙什麼的，就是理解為E,D的一部分好了

好處就是我對密文（F(x)）運算，對結果解密之後，就是想要的原文運算結果。那麼我把數據加密後給雲，雲只要計算密文，在不知道我真實數據情況下幫我計算，再發給我，我自己機器解密一下就是計算結果了。所以就是雲計算嘍，你掙了100萬，行賄20萬就能大大方方的上雲端給你記這筆帳嘍

怎麼實現的，那是數學的事，去讀讀Gentry相關的文章就行，那個基於整數(integer)的版本很好理解…但那個很慢

於是他又搞了個基於格(lattice)版本，快很多了，很有前景了…至於那個玩意很難懂是真的，國內外都是。知乎里…包括我自己我敢說沒人真懂。

大家都是看個大概齊，直接去搞IBM那開源代碼了。

同態加密 - 搜狗百科

作用可以是替代非對稱加密協議用於交換密鑰，且時間較短。

實際上在沒有RSA和DH協議之前。沙米爾（AdiShamir ）已經提出了一個協議叫做沙米爾密鑰交換協議。

大概內容如下：

A與B通信。

A加密Fa（x）發送給B

B加密得到的字元串Gb(Fa(x),y)發給A

A解密以上字元串F-1a(Gb(Fa(x),y),z)發給B

B解密以上字元串得到G-1b（F-1a(Gb(Fa(x),y),z)）

假設這裡同態密碼成立。我把XYZ拆開寫。

G-1b（F-1a(Gb(Fa(x),y),z)）《=》G-1b（Gb(F-1a（Fa（x））)）, G-1b（F-1a(Gb(y))),G-1b（F-1a(z))《=》x,F-1a（y）,G-1b（F-1a(z))

在這一步得到了X。現在兩個人可以使用密鑰X進行通訊了。

到這一步雙方只是使用自己的演算法和密鑰一同加密解密就交換了通訊密鑰。

1.為毛要使用同態密碼？

因為算大質數時間太長而且質數分解的安全性沒有辦法證明。索性還是對稱加密來的安全。

2.通訊過程中雙方是否暴露了彼此的加密演算法或者信息。

沒有，通訊雙方都不知道對方的加密演算法，更何況第三方。

3.這個協議為毛沒有替代非對稱加密的作用？

因為同態密碼代數結構太複雜。

4.世界上有無同態代數結構。

有，異或運算。

PS，我不是學數學的。當時了解之後就很快對這個失去了興趣。我書讀的少，問我的問題別太難。

你指的同態性，首先是Rsa加密體系的一個弱點，可以被用於選擇密文攻擊。而同態性，可以在加密後保持一定結構，使你對明文的運算等價於對密文的運算。在現實中，可以用於雲計算加密，比如有些公司需要處理大量數據，要交由其他公司（如提供雲計算的服務商）去做，但數據比較敏感，不希望別人知道，這時候就可以利用同態加密。總之，主要依靠數論的知識，樓主了解一下就知道了。

ps:第一次回答問題，把答案寫到評論里去了，現在移過來。

你指的是homomorphic encryption 吧。

大致意思就是在明文上的某種運算對應於密文上的某種運算。

例如 Enc（）是加密演算法，m是明文，這種加密演算法滿足性質

Enc（m1*m2) = Enc(m1)+Enc(m2)， *，+分別指明文上和密文上的某種運算。

這種加密的一個應用就是，想想看，你想計算m1*m2，可以先把m1和m2加密了，然後計算 Enc(m1)+Enc(m2)，然後解密就可以得到結果了。例如，這種加密現在在雲計算的外包中有些應用，但本人持謹慎態度。

一個很大的缺點就是，通常這種加密方法只能滿足某一種運算，從而限制了其應用。例如，RSA，滿足加法和乘法之間的轉化（這點我只是想了一下，沒具體驗證）。

Fully homomorphic encryption, 雖然由Gentry 在09年提出，號稱可以滿足各種運算，但是複雜度太高了，目前只有理論上的研究價值。

ps：以上有什麼不對的地方，請多指正。

我不太懂HE，但是看了上文，有個想法想請教，for example，一些涉及版權的圖像，需要對其嵌入水印，但是不想讓水印嵌入的操作者複製這些圖像，就先對這些圖像進行加密，然後在encrypted image中嵌入水印，再交給圖像所有者，最後通過解密得到嵌入水印的圖像，這樣的加密演算法算HE嗎？

那有什麼實現同態加密的庫嗎？

說實話我希望看到新東西，而不是基本概念。我最近倒是做了一個報告，單不知道是否合適上傳。而且裡面有些錯誤，我也不太有耐心去修改了。