密鑰泄露后安全的可搜索對稱加密
責編：gltian ｜2023-07-03 13:59:36動態可搜索對稱加密（Dynamic Searchable Symmetric Encryption，DSSE）是一種用于實現加密關鍵字檢索的密碼學原語。在DSSE中，存在一個客戶端和一個“誠實但好奇”的服務器。服務器上存儲有一個加密數據庫，客戶端能夠更新該加密數據庫的內容以及在該加密數據庫上實現關鍵字檢索，同時隱藏關鍵字的明文信息。DSSE因其可增強用戶在使用安全云外包存儲的流程中的友好性，受到廣泛的研究。然而，我們發現，如果DSSE的密鑰產生了泄露，那么現有DSSE方案均會失去安全性。為了解決這一問題，我們提出了密鑰可更新的可搜索對稱加密（Searchable Encryption with Key-Update，SEKU）。SEKU允許客戶端非交互式地更新服務器上密文的密鑰，使得已泄露的密鑰失效。同時，我們還利用泄露函數定義了SEKU的密鑰泄露后安全性。該安全性要求在密鑰泄露后，采用已泄露密鑰生成的密文依然具有安全性。最后，我們構造了具有密鑰泄露后安全性的SEKU方案——Bamboo。Bamboo同時還具有前向安全性與后向安全性。最后的實驗結果表明，Bamboo相比傳統DSSE方案，具有相當或更好的性能。
該成果“The Power of Bamboo: On the Post-Compromise Security for Searchable Symmetric Encryption”已被CCF A類國際會議NDSS 2023錄用。該會議主要關注網絡和分布式系統安全，被稱為“安全領域四大頂會之一“，2023年的論文錄用率為16.2%.
- 論文鏈接：https://dx.doi.org/10.14722/ndss.2023.24725
背景與動機
DSSE允許一個客戶端將自己的加密數據庫安全外包存儲到一個誠實但好奇的服務器上。通常，該加密數據庫是一系列密文的集合。DSSE中，客戶端通常持有一個私鑰與一個私有狀態，私有狀態記錄了加密數據庫當前的狀態。利用私鑰和私有狀態，客戶端能夠向加密數據庫添加數據或從加密數據庫中刪除數據，以及對加密數據庫執行關鍵字檢索，并且在這些操作中不泄露任何關鍵字信息。
自從DSSE在學術界被提出以來，許多學者對其展開了研究。檢索性能與安全性是DSSE中最受關注的特點。在檢索性能方面，目前主流DSSE方案均實現了亞線性級檢索復雜度，即檢索時間開銷僅與檢索結果的數量線性相關。在安全性方面，目前主流的DSSE方案均以前向安全性與后向安全性作為實現目標。其中前向安全性保證了，當客戶端向加密數據庫中新添加一個密文，或者從加密數據庫中新刪除一個密文，即使被更新的密文中所包含的關鍵字曾經被檢索過，服務器也無法將客戶端的添加和刪除操作與以前的任何檢索請求聯系起來。而后向安全性則限制檢索時被刪除的密文所能夠泄露的信息。前向與后向安全性的提出對DSSE的安全性有很大的提升作用。
然而，已有DSSE方案的安全性，均依賴于一個假設，即客戶端的密鑰從不會泄露。這個假設在實用中是難以成立的。畢竟在國際上已經出現了多起知名企業密鑰被泄露的事件。因此，在DSSE中也應當考慮密鑰泄露的風險。
圖1 知名企業的密鑰泄露事件
挑戰
發生密鑰泄露事件后，常規的補救措施是對客戶端本地的密鑰，以及加密數據庫中密文的加密密鑰進行更新，使得已泄露的密鑰失效，讓密鑰竊取者無法再解密尚未來得及獲取的密文，從而實現止損的效果。也就是說，我們需要給DSSE配備一個密鑰更新協議，使得客戶端可以隨時執行這個協議來進行密鑰更新。
在實用中，這個密鑰更新協議最直觀的實現方式是，讓客戶端將整個加密數據庫下載到本地，在本地解密之后使用新的密鑰加密生成新加密數據庫，再將新加密數據庫上傳到服務器保存。顯然這樣的實現方式會造成大量的帶寬與客戶端計算開銷，是不實用的。因此出于實用性考慮，這個密鑰更新協議應當是非交互式的，即客戶端僅需要生成一個具有常數級大小的密鑰更新憑據，再將該憑據上傳到服務器上。服務器利用該憑據更新整個加密數據庫的密鑰。
直觀來看，這樣的非交互式更新操作的實現是非常簡單的。僅需將密文無關的可更新加密或密鑰可更新的偽隨機函數與現有可搜索加密方案進行結合，即可實現這樣的非交互式更新。例如可將MITRA這個DSSE方案中的偽隨機函數替換為密鑰可更新的偽隨機函數，或將Horus這個DSSE方案中的加密方案替換為密文無關的可更新加密。然而，這樣的直觀實現無法解決一個重要的安全性問題：如何保證密鑰泄露后、密鑰更新前這段時間所生成密文的安全性。
圖2 密鑰泄露后、密鑰更新前生成的可搜索密文
在實用中，密鑰泄露事件可能無法及時被發現，即客戶端可能會繼續使用泄露后的密鑰生成可搜索密文或發布加密檢索請求。當密鑰泄露時，從安全模型上來看，客戶端所有已有的加密數據庫可認為已被泄露。然而，如果能夠保證在密鑰泄露后、密鑰更新前所生成可搜索密文的安全性，就相當于實現了針對外部密鑰竊取者的前向安全性。這樣的安全性在實用中非常重要，能夠極大提升密鑰泄露情況下客戶端數據的安全性。
然而，顯然上述非交互式更新的實現方法并未考慮到針對密鑰竊取者的前向安全性。因此，如何實現針對密鑰竊取者的前向安全性，是一個重要的技術挑戰。
解決思路
為了解決這個問題，我們設計構造了SEKU實例化方案Bamboo。Bamboo實現了密鑰泄露后安全性，即：1、密鑰更新過程不向服務器泄露任何語義信息；2、在密鑰泄露后、密鑰更新前所生成的可搜索密文不會向密鑰竊取者泄露任何信息。同時，Bamboo還具備亞線性級檢索復雜度。Bamboo實現密鑰泄露后安全性和亞線性級檢索復雜度的核心是兩點：1、雙重加密和2、隱藏鏈式結構。
雙重加密思想具體來說，就是在內層加密使用一次性隨機數對數據進行加密，而外層加密則使用密鑰可更新的加密體制。其中外層加密允許客戶端對加密數據庫執行非交互式的密文更新，而內層加密中，由于使用的是一次性隨機數進行加密，即使當前客戶端的密鑰泄露了，服務器也無法獲知新生成密文中內層加密所用的隨機數，也就無法解密新生成的密文，從而保證了密鑰泄露后、密鑰更新前所生成密文的安全性。
而Bamboo為了實現亞線性級檢索復雜度，在具有相同關鍵字的可搜索密文間構造了一條隱藏鏈式結構。該結構中，新生成的密文加密保存有前一條密文的內層加密密鑰。客戶端僅需保存最新生成的密文的內層密鑰即可。當客戶端發布檢索請求時，將最新生成的密文的內層密鑰上傳到服務器，服務器便可根據隱藏鏈式結構一次性找到所有滿足條件的密文，也即實現了亞線性級檢索復雜度。
方案性能
最后，我們在網絡環境下對Bamboo的性能進行了測試，并與傳統的不具有密鑰泄露后安全性的方案進行了對比。對比結果顯示，Bamboo與傳統方案的性能在同一級別，并且在某些指標上比傳統方案要好。
在實驗中，我們將所提出的方案Bamboo與三個傳統方案MITRA、Aura和Fides進行了對比。這三個方案實現了與Bamboo相同級別的前向與后向安全性。在對比時，我們同時為這三個方案設計了密鑰更新協議。其中MITRA的密鑰更新協議是通過替換其所使用的偽隨機函數為密鑰可更新的偽隨機函數，從而實現了非交互式的密鑰更新。而Aura和Fides因其構造上的獨特性，無法實現這樣的替換，因此這兩個方案的密鑰更新協議是通過將整個加密數據庫從服務器端下載下來，再由客戶端對其進行重新加密而實現的。
表1 密文生成性能對比
表2 密鑰更新性能對比
表1和表2分別對比了Bamboo和其他三個方案的密文更新性能與密鑰更新性能。Bamboo的性能比Aura和Fides都好，但是比MITRA稍弱一些。這是因為Bamboo所生成的密文比MITRA所生成的密文多包含一個元素來保存隱藏鏈的信息。多出的這個元素在密文更新與密鑰更新時，分別需要多一次橢圓曲線群上元素的指數運算，因此造成性能開銷的增長。
圖3 Bamboo的多線程密鑰更新性能
圖3展示了Bamboo密鑰更新過程在多線程情況下的加速效果。很顯然，所用線程越多，Bamboo的密鑰更新耗時越短。
圖4 檢索性能對比
圖4展示了Bamboo和其他三個方案檢索性能的對比，Bamboo的性能比Fides好，比MITRA和Aura略差。
圖5 檢索時客戶端性能對比
圖5展示了Bamboo與其他三個方案在檢索時客戶端耗時的對比。顯然Bamboo比MITAR和Fides在檢索時會產生更少的客戶端性能開銷。但是相比Aura，Bamboo的客戶端開銷略高一點。
總得來說，相比起傳統方案，Bamboo的性能與它們不相上下，優勢之處互有來回。同時考慮到Bamboo首創性地實現了密鑰泄露后安全性，該安全性并未給Bamboo帶來顯著的額外性能開銷。因此，可以下結論說，Bamboo具有很高的實用性。
其他重要貢獻
除了上述Bamboo方案的構造外，本文中還首次定義了密鑰可更新的可搜索對稱加密及其安全性，并對安全模型進行了詳盡分析，并首次用泄露函數定義了密鑰泄露后安全性。囿于篇幅，此處不再詳細描述，請感興趣的讀者閱讀論文了解詳情。
詳細內容請參見：
Tianyang Chen, Peng Xu, Stjepan Picek, Bo Luo, Willy Susilo, Hai Jin, and Kaitai Liang. “The Power of Bamboo: On the Post-Compromise Security for Searchable Symmetric Encryption.” In Proceedings of the Network and Distributed System Security Symposium (NDSS) 2023.
https://dx.doi.org/10.14722/ndss.2023.24725
來源：穿過叢林