同態加密是一種允許直接對加密數據執行計算而無需解密密鑰加密方案。從理論上講其功能強大且在學術上很具有吸引力,但是實際使用門檻較高。

原文標題:《隱私保護計算技術指南 4》
撰文:陳智罡

概述

同態加密是指具有特殊代數結構的一系列加密方案,該結構允許直接對加密數據執行計算而無需解密密鑰。

自 1970 年代以來,支持單一算術運算(加法或乘法)的加密方案就已廣爲人知,通常被稱爲單同態。Rivest,Adleman 和 Dertouzos 意識到同態性質的實用價值 , 並就此領域進行了探索研究。

2009 年,Craig Gentry 提出了第一個全同態加密方案。該方案允許對加密數據執行加法和乘法。

這是一項重要的發明,因爲原則上,這種加密方案可以允許對加密數據計算任意布爾和算術電路,而無需向執行計算的一方透露輸入數據或結果。取而代之的是,結果只能由有權訪問密鑰的特定方(通常是輸入數據的所有者)解密。

該功能使同態加密成爲用於雲存儲和計算安全的強大工具,並且是依賴於此類功能的高級加密和協議的基礎。

儘管從理論上講其功能強大且在學術上很具有吸引力,但第一代全同態加密方案在性能和密鑰大小方面的原因,使其無法得以實踐應用,只處於理論階段。

在接下來的幾年中,爲發明和實現更簡單,更快的同態加密方案,學術領域進行了大量工作。這項工作最終由 IBM 研究院發佈了全同態加密庫 HElib。該庫將先前的同態加密實現的性能提高了幾個數量級。如今,有多個開源的同態加密庫可用,它們實現了適用於不同應用程序的各種同態加密方案。

關於術語的注意事項

雖然原則上全同態加密方案允許對加密數據進行任意計算,但實際上幾乎所有有效的實現方式都使用所謂的「分層模式」下的全同態加密 (Leveled FHE),其中加密方案配置爲僅支持特定大小或有界大小的計算,通常會導致性能極大的提升。

爲簡單起見,在本文中,我們自由地使用術語同態加密(HE)來指全同態加密(FHE)或層次型全同態加密。

應用實例

同態加密提供了強大的後量子安全和獨特的非交互式密文計算功能,但是會導致較高計算開銷和消息大小的擴展。

因此,理想的應用場景應該是在具有相對較小但關鍵的加密計算組件,包括持久性存儲方面。並且其功能很難或者不可能使用其他方法來實現。

典型的應用實例是在醫療領域。其中法規強制執行嚴格的患者數據隱私措施,但是醫院和診所可能仍希望使第三方服務提供商能夠分析,評估或計算其數據,而無需花費大量金錢以及耗時的法律程序。例如,服務提供商可以提供圖像分析服務以在 MRI 掃描中檢測腫瘤。可以直接對同態加密數據進行計算分析,從而避免醫療數據泄漏給服務提供商的問題。

對於數據存儲提供商而言,潛在的應用程序是對加密的客戶數據執行分析。例如,客戶可能想使用雲存儲服務來存儲大型加密數據庫,而不必爲簡單的計算查詢而下載整個數據庫,因爲這會帶來不必要的本地計算配置與成本,並可能使整個數據集暴露於潛在的低安全性計算環境中。

相反,所有可能的數據彙總都應由雲存儲提供商直接以加密形式執行,以避免不必要地將數據暴露給客戶端計算機

另一個有希望的應用是在隱私數據交集和隱私信息檢索協議中。在隱私數據交集中,客戶端和服務器擁有唯一的標識符集(例如,名稱,電子郵件地址,電話號碼),並希望在它們的集合中找到共同的項目。例如,兩家公司可能希望找到他們共同的客戶。

當一組中的某一組比另一組小得多時,同態加密可以爲該問題提供有效的解決方案

在這種情況下,可以對較小的集合進行同態加密,然後發送給另一方,後者可以將加密後的數據與其集合做匹配計算。在私人信息檢索中,當事方之一可以檢索與匹配項相關聯的數據,而無需數據所有者知道檢索了什麼數據(如果有的話)。在這種類型的協議中,對數據集合的大小有上限的限制,並且所有通信和計算都必須與這些上限成比例。

敵手模型和安全性爭論

如今,所有具有實用性能或接近實用性能的同態加密方案都基於有錯誤學習(LWE)或環上錯誤學習(RLWE)的困難問題。換句話說,如果可以有效地破壞這些困難問題,則可以有效地解決 LWE 或環 LWE 的特定問題。由於對 LWE 和環 LWE 進行了廣泛的研究,並認爲現代計算機無法解決這些困難問題,因此有充分的理由相信這些同態加密方案是安全的。

由於同態加密是一種特殊的加密算法,而不是指的協議,因此其安全性定義僅規定,當給定密文後沒有密鑰的敵手將無法獲得有關明文的任何信息。即使允許敵手選擇任意數量的明文加密,此特性也將保留。此性質也稱爲 CPA。

但是,當允許敵手獲取自己選擇的數據解密時,其安全性不成立。確實,對於同態加密的安全使用,至關重要的是,除非有關可信數據的信息不會發生不良行爲,否則絕不要將有關解密數據的信息傳遞迴相應的加密數據的信息源。這包括看似無害的信息,例如重複執行協議的請求,拒絕爲服務付費或揭示行爲的任何變化,這些變化可能取決於加密計算的結果。

這樣的反向通信信道的存在可能最壞地導致完整的密鑰恢復攻擊,並且降低安全級別。因此,應將涉及單用戶的數據外包存儲和計算視爲同態加密的主要用例。在收到計算結果之後,密鑰所有者不得基於解密結果執行任何服務提供商可以觀察到的操作,以避免上述攻擊。

另一個微妙之處是大多數同態加密方案都不提供輸入隱私:如果計算依賴於兩個或更多方的私有加密輸入,則不能保證加密方案可以保護這些輸入免受密鑰所有者的攻擊。同態加密在本質上也很特殊,截獲密文的任何人都可以修改底層的明文。除非例如密文是由發送者加密簽名的。

目前同態加密的使用門檻較高,沒有加密專家的幫助,就不可能從中建立安全協議。多數基於同態加密的協議只能在半誠實的安全模型中被證明是安全的。但是也有例外,其中通過將同態加密與其他原語結合起來可以實現更強大的安全模型。

使用技術的成本

同態加密的使用至少帶來三種類型的成本:消息擴展,計算成本和工程成本。

在同態加密系統中,由於編碼效率較低(將實際數據轉換爲可以加密的明文元素)以及密文本身擴展(密文大小與明文大小之比),加密數據通常比未加密數據大得多。

根據使用情況,編碼效率低下的範圍可能從理想情況(根本沒有擴展)到在編碼方法選擇不當時以數萬或數十萬規模的擴展率。消息擴展原則上可以任意大,但是實際上,根據使用情況,可以預期擴展因子爲 1 到 20 倍。因此,在大多數情況下,人們不應該考慮使用同態加密來加密大量數據,而應仔細考慮所需的加密計算確切需要哪些數據,而僅對其進行加密。

同態加密的計算成本與未加密的計算相比顯著。準確的成本在很大程度上取決於加密方案的參數以及吞吐量或等待時間。也就是說,大多數同態加密方案都支持對加密數據進行向量化的批處理計算,如果可以充分利用批處理功能,則可以將吞吐量提高 1000–100000x。

開發具有同態加密的複雜系統可能是一項挑戰,應始終在專家的幫助下完成,這樣的解決方案的初始成本可能很高。造成這種情況的原因有兩個:如前所述,如果沒有特殊的專業知識,則很難理解和評估安全模型;而如果不深入瞭解其工作原理,則可能難以充分利用可用的同態加密庫。

還應注意,同態加密很難或不可能與現有系統集成。相反,此技術的複雜應用程序可能需要對現有數據管道,數據操作過程和算法以及數據訪問策略進行實質性更改。

可用性

最常用的全同態加密方案是 Brakerski-Gentry-Vaikuntanathan (BGV)和 Brakerski-Fan-Vercauteren (BFV)方案。兩者都允許對有限域元素的向量進行加密計算。

最近,CKKS 方案計劃已獲得普及。CKKS 方案允許對實數或複數進行近似加密計算,非常適合統計和機器學習應用。

不同方案之間的權衡比較複雜,即使對於本領域的專家而言也可能難以理解。對於非常大和非常小的計算,BGV 方案比 BFV 方案具有性能優勢,但是在許多其他情況下,技術的差異可以忽略不計。另一方面,與 BFV 方案相比,BGV 方案更加複雜並且學習曲線更陡峭。CKKS 方案的性能與 BGV 相當,但學習起來可能更具挑戰性。但是,它提供了其他方案無法提供的功能。

BGV 方案在 IBMResearch 的 HElib 庫和新澤西理工學院的 PALISADE 庫 / 框架中實現。BFV 在 MicrosoftSEAL,PALISADE 和 FV-NFLlib 庫中實現。CKKS 在 Microsoft SEAL,HEAAN 和 HElib 中實現。

雖然 BGV,BFV 和 CKKS 在理論上都允許對加密數據進行任意計算,但是在預先確定電路深度並選擇加密方案參數以實現計算的分層模式下,它們通常效率更高。

相反,TorusFHE (TFHE)方案對按位加密的輸入進行操作,並嘗試進行優化以實現任意計算。在需要按位加密輸入的情況下,例如在涉及加密數字比較,排序或類似非多項式運算的計算中,諸如 TFHE 之類的方案可能是最有效的解決方案。TFHE 方案具有相同名稱的庫。

來源鏈接:mp.weixin.qq.com