什么是同態(tài)加密
早在1978年，Ron Rivest, Leonard Adleman, 以及Michael L. Dertouzos就以銀行為應(yīng)用背景提出了同態(tài)加密（Homomorphic Encryption）這個(gè)概念。在這個(gè)概念中，允許對(duì)密文進(jìn)行特定的代數(shù)運(yùn)算后依然能得到加密的結(jié)果，將該結(jié)果解密以后的結(jié)果與對(duì)明文進(jìn)行同樣運(yùn)算的結(jié)果會(huì)保持一致。
具體的定義如下，假設(shè)存在明文m，加密函數(shù)E,解密函數(shù)D,密文c，則有
c = E(m)
m = D(c)
假設(shè)現(xiàn)在需要對(duì)明文m做一些處理，處理過程可以用函數(shù)f表示，如果存在下面關(guān)系
f(m) = D(f(c))
則稱加密算法為同態(tài)加密算法。
用途
上面的一些公式究竟有什么用？下面我們來假設(shè)一個(gè)場景。某小銀行A有一批交易私密的數(shù)據(jù)處理，比如說要提取用戶交易信息給用戶畫像進(jìn)行相應(yīng)的理財(cái)產(chǎn)品推薦之類，定義了特征提取方法函數(shù)F，但計(jì)算量很大，A并不想投太多錢在基礎(chǔ)建設(shè)上，而是想使用廉價(jià)的云計(jì)算服務(wù)。這個(gè)業(yè)務(wù)有幾個(gè)特征：
- 需要處理的數(shù)據(jù)是私密數(shù)據(jù)
- 處理函數(shù)特別耗計(jì)算力
- 銀行
A不是土豪，并不愿意投太多錢到機(jī)器和運(yùn)維費(fèi)用上。
而使用其他公司提供的云計(jì)算平臺(tái)就會(huì)存在服務(wù)不可信的問題，這時(shí)候同態(tài)加密就開始發(fā)揮威力了。
從圖中可以看到引入同態(tài)加密之后，云計(jì)算平臺(tái)拿到加密數(shù)據(jù)，處理完的數(shù)據(jù)其實(shí)也是加密數(shù)據(jù)，這樣很好地防止云計(jì)算平臺(tái)獲取到原始私密數(shù)據(jù)，同時(shí)保證在傳輸過程中就算給攔截?cái)r截者也無法看到原始數(shù)據(jù)和處理結(jié)果。從圖中可以看到，同態(tài)計(jì)算方式流程中，由云計(jì)算平臺(tái)返回的處理結(jié)果cr，通過解密后D(cr)得到的結(jié)果r與原始數(shù)據(jù)m直接經(jīng)過F(m)得到的結(jié)果一致。
實(shí)際上這個(gè)方案有一個(gè)難點(diǎn)，就是選擇的同態(tài)算法是否支持任意處理函數(shù)F。其實(shí)按支持力度算法可分成兩類，支持任意處理函數(shù)F的同態(tài)加密算法被稱為全同態(tài)加密算法（Fully Homomorphic Encryption），而只支持特定函數(shù)F的就是微同態(tài)加密算法（Somewhat Homomorphic Encryption）。第一個(gè)全同態(tài)算法由Craig Gentry在2009年提出，但由于復(fù)雜度太高，暫時(shí)無法商用。
所以，同態(tài)加密在這個(gè)場景中只是理論可行，畢竟不能支持任意處理函數(shù)F能支持的應(yīng)用場景比較有限。
匿名投票系統(tǒng)設(shè)計(jì)
實(shí)際在我們生活上，有很多場景只需要特定的處理函數(shù)F既可，比如匿名投票系統(tǒng)。在介紹匿名投票系統(tǒng)之前，先稍微深入了解微同態(tài)加密算法。
微同態(tài)加密算法表示該算法至少滿足以下幾個(gè)條件中一個(gè):
- 加法同態(tài)
- 乘法同態(tài)
- 減法同態(tài)
- 除法同態(tài)
比如說我們經(jīng)常用到的RSA算法就是乘法同態(tài)，而在投票系統(tǒng)中，由于票數(shù)統(tǒng)計(jì)都是加法累加，只要找到具備加法同態(tài)的算法既可，比如Paillier算法，有興趣自行搜索一下，這里講一下Paillier算法的同態(tài)等式
D(E(m1,r1)*E(m2,r2) mod n^2) = m1+m2 mod n
其中m1和m2是原文，r1和r2是算法的隨機(jī)因子（主要是為了針對(duì)同樣的明文加密出來的不同密文）,n是算法所選擇出來的兩個(gè)大素?cái)?shù)的乘積。
為了最簡要說明同態(tài)算法使用，我們簡化匿名投票系統(tǒng)的模型，模型定義如下
- 只兩個(gè)候選人
Bertrand和Lynn - 只兩個(gè)投票者
Obama和Cliton，兩者有算法公鑰，他們都是有身份的人，可以保證只投一票。 - 一個(gè)記票人
Satan，他可能是個(gè)壞蛋，但需要他運(yùn)行處理算法進(jìn)行記票。 - 一個(gè)公布結(jié)果人
Athena，她有算法私鑰
投票流程如下所示：
其中投票原文m1如下所示：
{
"Bertrand": 1,
"Lynn": 0
}
表示Obama投了Bertrand一票，投票密文cm1可能如下所示：
{
"Bertrand": 1283192381..., //一個(gè)很大的整數(shù)
"Lynn": 23432423... //也是一個(gè)很大的整數(shù)
}
Satan拿到兩個(gè)投票密文后需要統(tǒng)計(jì)票數(shù)，比如說統(tǒng)計(jì)Bertrand的票數(shù)，他需要把兩個(gè)投票密文Bertrand對(duì)應(yīng)的票數(shù)相乘（根據(jù)上面Paillier同態(tài)等式）來獲取票數(shù)，但實(shí)際上他并不知道Obama是否投了Bertrand一票。
而Athena拿到的加密票數(shù)可能如下所示：
{
"Bertrand": 89812371293..., //一個(gè)很大的整數(shù)
"Lynn": 218308213... //也是一個(gè)很大的整數(shù)
}
使用解密算法解密后就可以得到最終結(jié)果
{
"Bertrand": 1,
"Lynn": 1
}
至于Bertrand的那一票是誰投的，只有投票人知道了。
