IBM重寫了其C++同態加密庫，速度提高75倍 ！

IBM 的同態加密技術將速度提升 75 倍,它讓你可以處理加密數據，無需將加密數據轉換成明文數據、再轉換回成密文數據。

同態加密是一種用于在不解密的情況下處理加密數據的技術。這將使敏感數據處理變得極其安全：比如說，公司可以加密托管在云端的數據庫，無需將記錄轉換回成明文，就可以處理記錄。

IBM 研究同態加密已有一些年頭，它在三年前發布了 HElib C++ 庫的第一個版本，但該技術始終存在性能開銷大的問題。

在同態加密的發明者克雷格·金特里（Craig Gentry）的帶領下，IBM 首次研發的同態加密技術其運行速度比明文操作慢“100 萬億倍”。后來在一臺 16 核服務器上運行，速度加快了 200 萬倍。

因此，藍色巨人繼續完善 HElib。在 GitHub 上發布的最新版本（https://github.com/shaih/HElib）“重新實施了同態線性變換”，因而提升了性能，結果速度提高了 15 倍到 75 倍。

在國際密碼學研究協會上展示的這篇論文（見文末）中，IBM 的謝·哈勒維（Shai Halevi）和維克多·舒普（Victor Shoup，后者還供職于紐約大學）解釋了他們如何提高速度。

他們寫道：“在目前 HElib 中采用的線性變換算法中，大部分時間花在了在加密矢量（encrypted vector）中的時隙（slot）之間傳輸數據。”

這是通過“特殊的自同構”（automorphism，一種將對象映射到自身的數學操作）來完成的，計算成本來自自同構要完成多少次循環。

論文寫道：“將這種自同構運用于密文的主要成本實際上是‘密鑰交換’的成本：我們將自同構運用于密文中的每個環元素上（這實際上是成本很低的操作）后，最終得到了相對于“錯誤”密鑰的加密；通過使用這個特定自同構所特有的公鑰中的數據（即所謂的“密鑰交換矩陣”），我們就可以將密文轉換回成相對于‘正確’密鑰的加密。”

“所以提高性能的主要目標是，減少自同構的數量，并降低每個自同構的成本。”

用更通俗的話來說，新的庫采用了一種新的策略來計算那些自同構（速度提高了 15 倍到 20 倍）；研究人員重構了許多必要的計算；一些計算被移出了庫的主循環（速度提高了 6 倍到 20 倍）。

由于上述的密鑰交換矩陣，為同態加密構建公鑰的方式同樣開銷很大。每個矩陣為公鑰添加了幾兆字節，而在 HElib 中，一個公鑰中可能有幾百個這樣的矩陣。研究人員表示，針對常見操作，他們能夠將矩陣的大小縮小 33% 至 50%。

HElib 仍然是一個研究性質的項目。正如 GitHub 頁面所述：“在現階段，這個庫主要面向研究 HE 及其用途的研究人員。目前它還相當低級，最好把它看成是‘面向 HE 的匯編語言’。也就是說，它提供了低級例程（set、add、multiply 和 shift 等），為優化提供了盡可能多的途徑。但愿最終我們能夠提供更高級的例程。”

論文全文：

來自: mp.weixin.qq.com