[科普中國]-同態(tài)加密

同態(tài)加密是基于數學難題的計算復雜性理論的密碼學技術。對經過同態(tài)加密的數據進行處理得到一個輸出，將這一輸出進行解密，其結果與用同一方法處理未加密的原始數據得到的輸出結果是一樣的。

概念隨著互聯(lián)網的發(fā)展和云計算概念的誕生，以及人們在密文搜索、電子投票、移動代碼和多方計算等方面的需求日益增加，同態(tài)加密(Homomorphic Encryption)變得更加重要。同態(tài)加密是一類具有特殊自然屬性的加密方法，此概念是Rivest等人在20世紀70年代首先提出的，與一般加密算法相比，同態(tài)加密除了能實現基本的加密操作之外，還能實現密文間的多種計算功能，即先計算后解密可等價于先解密后計算。這個特性對于保護信息的安全具有重要意義，利用同態(tài)加密技術可以先對多個密文進行計算之后再解密，不必對每一個密文解密而花費高昂的計算代價；利用同態(tài)加密技術可以實現無密鑰方對密文的計算，密文計算無須經過密鑰方，既可以減少通信代價，又可以轉移計算任務，由此可平衡各方的計算代價；利用同態(tài)加密技術可以實現讓解密方只能獲知最后的結果，而無法獲得每一個密文的消息，可以提高信息的安全性。正是由于同態(tài)加密技術在計算復雜性、通信復雜性與安全性上的優(yōu)勢，越來越多的研究力量投入到其理論和應用的探索中。近年來，云計算受到廣泛關注，而它在實現中遇到的問題之一即是如何保證數據的私密性，同態(tài)加密可以在一定程度上解決這個技術難題。

本質上，同態(tài)加密是指這樣一種加密函數，對明文進行環(huán)上的加法和乘法運算再加密，與加密后對密文進行相應的運算，結果是等價的。由于這個良好的性質，人們可以委托第三方對數據進行處理而不泄露信息。具有同態(tài)性質的加密函數是指兩個明文a、b滿足Dec(En(a)⊙En(b))=a⊕b的加密函數，其中En是加密運算，Dec是解密運算，⊙、⊕分別對應明文和密文域上的運算。當⊕代表加法時，稱該加密為加同態(tài)加密：當⊙代表乘法時，稱該加密為乘同態(tài)加密。

全同態(tài)加密是指同時滿足加同態(tài)和乘同態(tài)性質，可以進行任意多次加和乘運算的加密函數。用數學公式來表達，即Dec(f(En(m1)，En(m2)，…，En(mk)))=f(m1，m2，…，mk)，或寫成：f(En(m1)，En(m2)，…，En(mk))=En(f(m1，m2，…，mk))，如果f是任意函數，稱為全同態(tài)加密。

直到2009年，IBM的研究人員Gentry首次設計出一個真正的全同態(tài)加密體制，即可以在不解密的條件下對加密數據進行任何可以在明文上進行的運算，使得對加密信息仍能進行深入和無限的分析，而不會影響其保密性。經過這一突破，存儲他人機密電子數據的服務提供商就能受用戶委托來充分分析數據，不用頻繁地與用戶交互，也不必看到任何隱私數據。同態(tài)加密技術允許公司將敏感的信息儲存在遠程服務器里，既避免從當地的主機端發(fā)生泄密，又依然保證了信息的使用和搜索；用戶也得以使用搜索引擎進行查詢并獲取結果，而不用擔心搜索引擎會留下自己的查詢記錄。為提高全同態(tài)加密的效率，密碼學界對其研究與探索仍在不斷推進，這將使得全同態(tài)加密越來越向實用化靠近。1

相關概念同態(tài)加密的思想起源于私密同態(tài)，代數同態(tài)和算術同態(tài)是私密同態(tài)的子集。

R 和 S 是域，稱加密函數 E：R→S 為：

加法同態(tài)，如果存在有效算法⊕，E(x+y)=E(x)⊕E(y)或者 x+y=D(E(x)⊕E(y))成立，并且不泄漏 x 和 y。

乘法同態(tài)，如果存在有效算法 ，E(x×y)=E(x) E(y)或者 xy=D(E(x) E(y))成立，并且不泄漏 x 和 y。

混合乘法同態(tài)，如果存在有效算法 ，E(x×y)=E(x) y 或者 xy=D(E(x) y)成立，并且不泄漏 x。

減法同態(tài)，如果存在有效算法○- ，E(x-y)=E(x)○- E(y)或者 x-y=D(E(x)○- E(y))成立，并且不泄漏 x 和 y，則稱 E 為減法同態(tài)。

除法同態(tài)，如果存在有效算法○/ ，E(x/y)=E(x)○/ E(y)或者 x/y=D(E(x)○/ E(y))成立，并且不泄漏 x 和 y，則稱 E 為減法同態(tài)。

代數同態(tài)，如果 E 既是加法同態(tài)又是乘法同態(tài)。

算術同態(tài)，如果 E 同時為加法同態(tài)、減法同態(tài)、乘法同態(tài)和除法同態(tài)。

主要應用云計算、電子商務、物聯(lián)網、移動代碼等。2

本詞條內容貢獻者為:

李嘉騫 - 博士 - 同濟大學