同態加密

2009年9月，CraigGentry的論文發表於STOC。一名IBM研究員解決了一項棘手的數學問題，該問題自從幾十年前公鑰加密發明以來一直困擾著科學家們。該項創新為“隱私同態（privacyhomomorphism）”或“全同態加密（fullyhomomorphicencryption）”領域的重要技術突破，使得加密信息，即刻意被打亂的數據仍能夠被深入和無限的分析，而不會影響其保密性。

IBM研究員CraigGentry設計了這一解決方案。他使用被稱為“理想格ideallattice”的數學對象，使人們可以充分操作加密狀態的數據，而這在過去根本無法設想。經過這一突破，存儲他人機密電子數據的電腦銷售商就能受用戶委託來充分分析數據，不用頻繁與用戶交互，也不必看到任何隱私數據。利用Gentry的技術，對加密信息的分析能得到同樣細緻的分析結果，就好像原始數據完全可見一樣。

使用該解決方案能增強雲計算業務模式。計算機銷售商可以受託在任意網際網路環境中保管他人的機密數據。

以往加密手段的一個弊處在於它通常是將數據保存在盒子內而不讓外界使用或者分析數據，除非使用解密密鑰將盒子打開，而完全同態加密方案可以讓你在數據加密的情況下對數據進行分析和計算。IBM的工程師們近日突破了一項折騰他們幾十年的老大難問題：如何對數據進行加密，這樣其他人可以進行排序和搜索，而無需實際揭示它的內容。

如果說，一種加密演演算法，對於乘法和加法都能找到對應的操作，就稱其為全同態加密演演算法。換句話說，它的意義就在於，對於允許任意複雜的明文操作，都能構造出相應的加密操作。但直到目前還沒有真正可用的全同態加密演演算法，因為“在同步加密方案成為實用工具前，還需要進行很多理論上的工作以提高其“效率”。不過，IBM的研究員已使其該方向上前進了一大步，有效性已在逐步改善。

隨著雲計算將在未來變得越來越普及，同步加密技術將允許公司將敏感的信息儲存在遠程伺服器里，既避免從當地的主機端發生泄密，又依然保證了信息的使用和搜索。用戶也得以使用搜索引擎進行查詢並獲取結果，而不用擔心搜索引擎會留下自己的查詢記錄。

這項技術的關鍵點在於“雙盲”設計——可以檢測加密漏洞並進行修復，而不會造成信息泄露。而最好的消息還在於，它能夠在幾分鐘之內部署在普通的電腦上，而非成為那些天價超級計算機的專屬。

同態加密的思想起源於私密同態，代數同態和算術同態是私密同態的子集。

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

加法同態，如果存在有效演演算法⊕，E(x+y)=E(x)⊕E(y)或者 x+y=D(E(x)⊕E(y))成立，

並且不泄漏 x 和 y。

乘法同態，如果存在有效演演算法，E(x×y)=E(x) E(y)或者 xy=D(E(x) E(y))成立，

並且不泄漏 x 和 y。

混合乘法同態，如果存在有效演演算法，E(x×y)=E(x) y 或者 xy=D(E(x) y)成立，並

且不泄漏 x。

減法同態，如果存在有效演演算法○- ，E(x-y)=E(x)○- E(y)或者 x-y=D(E(x)○- E(y))成立，

並且不泄漏 x 和 y，則稱 E 為減法同態。

除法同態，如果存在有效演演算法○/ ，E(x/y)=E(x)○/ E(y)或者 x/y=D(E(x)○/ E(y))成立，

並且不泄漏 x 和 y，則稱 E 為減法同態。

代數同態，如果 E 既是加法同態又是乘法同態。

算術同態，如果 E 同時為加法同態、減法同態、乘法同態和除法同態。

利用一項全新的技術，未來的網路伺服器無須讀取敏感數據即可處理這些數據。2009年，一項數學論證提出的幾種可行性方案問世，這使得研究人員開始努力將方案變得更實際。

這一名為“全同態加密”的技術被冠以“密碼學的聖杯”的稱號。對數據進行加密給計算帶來了難度，但如能夠在不解密的前提下進行計算則進一步提高了數據的安全性。例如，遠程計算服務提供商收到客戶發來的加密的醫療記錄資料庫，藉助全同態加密技術，提供商可以像以往一樣處理數據卻不必破解密碼。處理結果以加密的方式發回給客戶，客戶在自己的系統上進行解密讀取。這一技術同樣可以應用到網路郵件或在線辦公軟體套裝中。

英國布里斯托爾大學密碼學教授奈傑爾·斯瑪特（NigelSmart）與比利時魯汶大學研究員弗雷德里克·韋爾科特朗（FrederikVercauteren）正在協作，對最原始的技術方案加以修改並進行實施和測試。斯瑪特說：“我們吸收了金特里的方案並對之作了簡化。”在最初的方案中，金特里使用了矩陣和矢量進行加密，斯瑪特與韋爾科特朗進行了改進，改用整數和多項式作為加密辦法。“這使得數據更簡單易懂，處理起來更容易。”斯瑪特說，“從而可以真正計算這些數據。”

最初的方案依賴矩陣和矢量，每一步都要分別計算每個元，這已經足夠複雜；計算完矩陣后還要處理數據本身，使得計算更加複雜。這使得矩陣和矢量加密方法實用性不強。斯瑪特與韋爾科特朗改寫了加密方法，免去了複雜的計算，使得金特里的理念得以在電腦上進行實施和測試。“我們確實實現了他的理念：對數據進行加密但計算過程更加簡單。”斯瑪特說，“我們可以處理30個順序操作。”

但是這一方案也有其局限性。隨著計算步驟的增加，連續加密的計算結果質量在下降，用斯瑪特的話說就是數據“變髒了”。不能進行任意計算，意味著現有的演演算法版本還未能實現全同態。

針對這個問題，金特里開發了一種演演算法，能夠定期對數據進行清理，實現系統的自我糾正，從而實現全同態。然而，金特里的演演算法要求系統實現一定量的計算，斯瑪特目前還無法實施。金特里表示，他與IBM的同事ShaiHelevi已經對斯瑪特的方案進行了修改，正在進行測試，今夏晚些時候將宣布改進結果。

目前，斯瑪特正在調整系統參數，試圖找到最佳的計算方法。“例如，生成密鑰的過程是非常緩慢的，我們已經對其進行了改進。”他說，“就像是調試賽車：調試完引擎后發現輪胎也需要調整一下。”

但同時斯瑪特也承認，改進何時到位並投入實際應用，目前還無從確認。“但是系統已經在運行；對於密碼學來講，在一年的時間裡發現新技術並進行首次應用展示，這已經是個奇迹。”他同時引用了橢圓曲線密碼技術的例子作為對照。該技術目前被應用在黑莓這樣的移動設備上用來保護數據安全。1985年被首次提出，但是在五年後才得到實施。

美國富士施樂公司研究中心的帕洛阿爾托實驗室高級科學家埃莉諾·里費爾（EleanorRieffel）對斯瑪特的觀點表示認同。“全同態技術的發展很快，但這是個全新的領域，大家都還在探索階段。”她說，“通過最初的摸索，人們不斷試驗進而找到最佳方案。”

里費爾同時指出，雖然這一技術的未來發展還不明朗，但IT界卻充滿了興趣。“越來越多的公司把重要數據存儲在外部，或者存儲在公司的多個地點，全同態的加密技術對他們有很大的吸引力。”該技術應用範圍或許更廣，但現階段有限的實施可以應用到特定的行業中。她補充道。