IEEE TIFS'22：健壯且具有前后向安全性的可搜索對稱加密 - 網安

動態可搜索對稱加密（Dynamic Searchable Symmetric Encryption，DSSE）是云安全外包存儲領域中的一種加密搜索技術。在DSSE的應用場景中，客戶端能夠對外包存儲在半可信云服務器上的密文數據庫執行添加、刪除與關鍵字搜索操作，并且同時保證密文中關鍵字的保密性。目前，學界針對DSSE的研究工作幾乎圍繞著降低運行中的信息泄露與提升搜索性能開展，而忽視了實用中DSSE的一項重要特性：健壯性。DSSE的健壯性是指，當客戶端發布不合理的更新請求后，DSSE仍然能夠保證正常功能與所聲稱的安全性的一種性質。其中，不合理的更新請求包括添加重復的數據與刪除不存在的數據。經過深入研究，我們發現已有的絕大部分DSSE方案都不具備健壯性，且目前尚未存在一個DSSE方案能夠同時實現健壯性、前后向安全性與實用搜索性能。在本文中，我們首次定義了DSSE的健壯性，并且構造了一個全新的同時具備健壯性、前后向安全性與高性能的DSSE方案ROSE。在構造ROSE的過程中，我們還提出了一個新的密碼原語——密鑰可更新的偽隨機函數。最后，本文通過實驗說明了ROSE的高效性。

該成果“ROSE: Robust Searchable Encryption with Forward and Backward Security and Practical Performance”發表于信息安全領域的頂級期刊TIFS（IEEE Transactions On Information Forensics and Security），是實驗室安全組在云數據安全領域的研究成果。

原文鏈接：
https://doi.org/10.1109/TIFS.2022.3155977

背景與動機

近年來，隨著研究者對DSSE探索的深入，學術界涌現出了一大批提升DSSE安全性與性能的里程碑式的工作。例如：2016年USENIX Security上Zhang等人提出了針對DSSE的文件注入攻擊，從此之后能夠保證未來的密文不被以前的搜索請求影響的前向安全性（Forward Security）成為了一個DSSE的基本安全性質；2017年CCS上Bost等人首次形式化定義了能夠限制被刪除的密文在搜索請求中所泄露信息的后向安全性（Backward Security），自此之后主流的DSSE方案均同時具備前向安全性與后向安全性（統稱為前后向安全性）；2021年ESORICS上Chen等人構造了具有并行化檢索能力與非交互式物理刪除特性的DSSE方案，將DSSE的實用性能拉上了一個新臺階。

自從DSSE面世以來，研究者們從未關注過DSSE的健壯性問題，這也導致已有的絕大部分前后向安全的DSSE方案不具備健壯性。使用這些不具備健壯性的DSSE方案時，客戶端若發布不合理的更新請求，要么會產生額外的信息泄露，導致方案安全性降低，要么會破壞已有的密文數據庫，導致無法正常執行功能。如下表所示。在這張表中，可以看到已有DSSE方案中，只有Moneta和Fides實現了健壯性，然而它們的實際性能很低，不具備實用價值。而表中的其他方案，例如FB-DSSE等，在用戶發布不合理的更新請求時，會導致密文數據庫的破壞；對于ORION與HORUS方案等，用戶的不合理更新請求會導致其前向安全性的破壞。因此，健壯性問題對已有DSSE方案的影響非常大，影響范圍也十分廣泛。

DSSE健壯性的定義

本文首先定義了DSSE的健壯性，即定義什么樣的DSSE是健壯的。一言以蔽之，健壯的DSSE方案應當即使在客戶端發布了重復的添加操作或刪除不存在的密文時，依然保持其所聲稱的正確性與安全性。傳統的未考慮健壯性的DSSE的正確性定義要求，搜索操作應當返回所有被添加進密文數據庫，并且尚未被刪除的記錄。總體上來說，健壯性定義與傳統的DSSE正確性定義是兼容的。然而，健壯性與傳統DSSE的安全性要求無法完全兼容的，在具有健壯性的DSSE中，為了進一步實現前后向安全性，需要對前后向安全性的定義進行改造，更具體來說，對后向安全性的定義進行改造。

前向安全性的定義要求，新生成的密文數據最多僅能泄露該數據所對應的操作類型（添加或刪除）以及對應的文件標識符，這一定義是符合健壯性要求的。然而對后向安全性來說，情況變得復雜起來了。以第三類后向安全性（Type-III Backward Security）為例，第三類后向安全性要求搜索請求僅泄露兩種信息：1、所有曾經被添加進密文數據庫且未被刪除的滿足搜索條件的文件標識符及其被添加進密文數據庫的時間戳；2、對與所有曾經被添加但是又被刪除的密文，返回既包含其被添加進密文數據庫的時間戳，也包含其對應刪除請求發生時的時間戳的元組。在傳統的DSSE中，因為無需考慮客戶端會添加重復的密文以及刪除不存在的密文，上述兩種信息泄露的定義是簡單且直觀的。然而在健壯性條件下，這樣的直觀性不復存在。例如，對于第一種信息來說，若客戶端將某一密文重復添加多次，或在刪除過某密文后又重新向密文數據庫添加了一次該密文，第一種信息就無法描述這兩類情況。因此，第一種信息泄露的表述應當修改為“所有依然存在于密文數據庫的滿足搜索條件的文件標識符以及被添加進密文數據庫的時間戳集合”。而第二種信息要考慮的情況則更為復雜，例如若某客戶端先多次重復添加了某密文，未來又發布了多個針對該密文的刪除請求，服務器就會獲知密文數據庫中存在多個刪除請求對應多個添加請求，而顯然已有表述無法準確描述此時服務器所獲得的泄露內容。因此，第二種信息泄露的表述應當修改為“對與所有曾經被添加但是又被刪除的密文，返回既包含其被添加進密文數據庫的時間戳集合，也包含其對應刪除請求發生時的時間戳集合的元組”。按照上述思路，本文擴展了第三類后向安全性的定義，并進一步定義了能夠用于滿足具有健壯性的DSSE性質的通用第三類后向安全性。

ROSE：健壯且具有前后向安全性的DSSE實例化方案

在定義了前后向安全DSSE的健壯性之后，本文還提出了一個具有健壯性的前后向安全的DSSE實例化方案ROSE。ROSE是第一個證明了健壯性、前后向安全性與第三類后向安全性的DSSE方案。ROSE采用了鏈式結構來組織具有同一個關鍵字的密文。鏈式結構的好處有兩點：1、能夠實現亞線性級的搜索復雜度；2、鏈式結構為密文天然賦予了時間上的偏序關系。然而，鏈式結構存在一個問題，即難以在保證后向安全性的情況下實現密文的刪除功能。為了解決這個問題，我們進一步定義并構造了一個全新的密碼工具——密鑰可更新的偽隨機函數。密鑰可能新的偽隨機函數是能夠利用更新憑據來更新已有偽隨機數生成密鑰的全新密碼學原語，其在功能語義上與已有的密鑰同態偽隨機函數存在本質差別。借助密鑰可更新的偽隨機函數，我們在ROSE中實現了對同一密文，每次搜索后其對應的刪除憑據都不同的特性，同時在發布搜索請求時也同時上傳一個對應的搜索密文來存儲密鑰可更新的偽隨機函數的密鑰更新憑據，保證了在不泄露密文中文件標識符的前提下，未來的刪除請求可以刪除以前發布的對應密文，從而確保了ROSE的后向安全性。

在ROSE的構造中，密文在時間上的偏序關系是實現健壯性的重要依據。第三類后向安全性要求，服務器在對密文執行安全搜索與刪除時，不能獲知被刪除的密文中所包含的文件標識符，因此服務器僅能利用密文中所包含的偽隨機化的刪除憑據來進行刪除操作。而在健壯性中，客戶端可能會先后針對同一個密文發布多個添加或刪除請求。此時服務器是否返回這個密文，取決于客戶端所發布的最后一個關于此密文的請求是添加還是刪除。若密文間不存在時間上的偏序關系，或這樣的偏序關系無法在搜索過程中暴露給服務器，服務器就無法正確執行刪除操作，也就無從實現健壯性了。

下圖用一個例子簡要展示ROSE的運行流程：

實驗結果

DSSE的研究屬于應用密碼學范疇，其最終目標是實現實用化部署。因此，一個DSSE方案的性能表現是衡量其好壞的重要指標。我們將ROSE與已有的幾個具有健壯性或能夠很容易改造為具有健壯性的方案進行了對比，實驗結果顯示ROSE具有很好的性能表現。下圖分別展示了ROSE與已有方案的搜索時間與搜索帶寬開銷上隨搜索結果數量的變化，可以看到ROSE的開銷僅略高于IMDSSEI+II。

下圖展示了ROSE方案與已有方案的客戶端時間開銷隨搜索結果數量的變化。在這個實驗中沒有列出HORUS方案，因為HORUS方案的絕大部分搜索時間開銷都是在客戶端上產生的，與其比較意義不大。從實驗結果可以看出，ROSE的客戶端開銷是最低的。

因為ROSE的構造特點，其在執行刪除時會因為密鑰可更新的偽隨機函數而調用密鑰可更新的偽隨機函數。而密鑰可更新的偽隨機函數需要在橢圓曲線群上執行代數運算，這增加了刪除時候的時間開銷，雖然在一次搜索后這些刪除密文就會被刪除，但是在處理這些刪除密文時，服務器還是會消耗不少的時間。為了解決這個問題，我們在刪除階段引入了多線程技術，來并行化地執行刪除憑據的判定，從而在不降低安全性的基礎上大大提升了刪除的效率。下圖展示了在密文數據庫存在不同數量搜索請求（S'=50, 100, 150, 200）的情況下，搜索階段的時間開銷隨刪除密文占總密文比例的變化。

詳細內容請參見：

Peng Xu, Willy Susilo, Wei Wang, Tianyang Chen, Qianhong Wu, Kaitai Liang, Hai Jin. "ROSE: Robust Searchable Encryption With Forward and Backward Security." IEEE Transactions on Information Forensics and Security (TIFS), 17 (2022), pp. 1115-1130, doi: 10.1109/TIFS.2022.3155977.