同態加密技術的發展是怎樣的？

發表評論

A+

同態加密是基于數學難題的計算復雜性理論的密碼學技術。對經過同態加密的數據進行處理得到一個輸出，將這一輸出進行解密，其結果與用同一方法處理未加密的原始數據得到的輸出結果是一樣的，下面來看看同態加密技術的發展是怎樣的嗎？

同態加密思想從提出到現在，在具體實現方案方面，經歷了3個重要時期：1978—1999年是部分同態加密的繁榮發展時期；1996—2009年是部分同態加密與淺同態加密的交織發展時期，也是淺同態加密方案的繁榮發展時期；2009年以后是全同態加密的繁榮發展時期。下面將以時間為主線，按照同態加密方案的類型介紹同態加密的發展。

1、部分同態加密方案
部分同態加密方案按照明文空間上能實現的代數或算術運算分為乘法同態、加同態和異或同態3種類型。下面從幾個著名的同態加密方案的優缺點入手，總結一下乘法同態、加同態、或同態加密方案的特性。

（1）乘法同態加密方案。乘法同態加密方案的同態性表現為[m1×m2=D（E（m1）×E（m2））]。RSA [5]是最早的具有乘法同態性的加密方案，它是基于因子分解困難問題的，屬于確定性加密，不能抵御選擇明文攻擊；1985年，ElGamal [3]基于有限域上的離散對數困難假設設計了ElGamal加密算法，該加密方案同樣具有乘法同態性，并且滿足選擇明文不可區分（IND-CPA）安全。

（2）加法同態加密方案。加法同態加密方案的同態性表現為[m1+m2=D（E（m1）?E（m2））]（[?]為定義在密文空間上的某種代數運算或算術運算）。具有加法同態性的加密方案有很多，應用最為廣泛的當屬Paillier [5]加密系統，該加密系統基于高階合數度剩余類困難問題，且具有IND-CPA安全。

（3）異或同態加密方案。乘法同態加密方案的同態性表現為[m1⊕m2=D（E（m1）?E（m2））]（[?]為定義在密文空間上的某種代數運算或算術運算）。目前，只有Goldwasser-Micali [15]加密系統屬于該類同態加密系統，該加密系統基于二次剩余困難問題，雖具有IND-CPA安全，但每次只能加密單比特，因此加密效率會比較低。

2、淺同態加密方案
淺同態加密方案能同時進行有限次乘法和加法運算的加密。從某種程度上講，該類型的加密方案是人們在研究解決RSA 3個人提出的公開問題（如何設計全同態加密方案）的過程中，出現的“副產品”。1999—2005年間出現了不少淺同態加密方案，例如文獻[6]、[16-18]中提到的方案。目前最為著名的淺同態加密方案當屬Boneh[5]等基于理想成員判定困難假設設計的加密方案。該方案能執行一次乘法和若干次加法運算，Boneh [5]等雖然用它成功解決了2DNF問題，但是該方案在解密時需要搜索解密，因此基于此方案的2DNF保密計算協議效率很低。

雖然此類加密系統為實現全同態加密方案的設計奠定了一定的基礎，但是只能用于解決某些專門的問題，即能夠解決的應用問題有限，很難將其拓展并且應用于解決更廣泛的問題。

3、全同態加密方案
2009年Gentry[7]設計了首個全同態加密方案，這一里程碑事件激起了全同態研究的熱潮。到目前，全同態加密方案按照構造思想大致可以分為以下3代。

（1）以Gentry[7]設計方案為代表的、基于格上困難問題構造的第1代全同態加密方案，這類方案的設計思想大致如下：

設計一個能夠執行低次多項式運算的淺同態加密算法。

控制密文噪聲增長，即依據稀疏子集和問題對解密電路執行“壓縮”操作，然后再執行自己的解密函數實現同態解密，從而能夠達到降噪的目的。

依據循環安全假設（即假定用方案的公鑰加密自身密鑰作為公鑰是安全的）實現純的全同態加密。

（2）以Brakerski-Vaikuntanathan [9]為代表的、基于帶誤差學習或環上帶誤差學習困難問題構造的第2代全同態加密方案，該類方案的構造思想大致如下：

歸約的基礎是誤差學習或環上帶誤差學習困難問題。

用向量表示密鑰與密文。

用密鑰交換技術來約減密文的膨脹維數，以達到降噪目的。

該類方案的優點是不再需要電路自舉技術，突破了Gentry的設計框架，在效率方面實現了很大的提升；其缺點是在使用密鑰交換技術時需要增加大量用于密鑰交換的矩陣，從而導致公鑰長度的增長。

（3）以Gentry-Sahai-Waters [12]為代表的、基于帶誤差學習或環上帶誤差學習困難問題構造的第3代全同態加密方案，此類方案的構造思想大致如下：