具有隱私保護的完整性可驗證的關鍵字搜索方案

劉雪艷 蘆婷婷 楊曉濤

(西北師范大學數學與統計學院 蘭州 730070)

1 引言

隨著大數據和云計算時代的到來，越來越多的個人和企業將大量私有數據上傳到云中，從而節省本地存儲和管理成本。為了保證數據的機密性和隱私性，數據屬主需要將數據加密后再上傳到云中，傳統的明文搜索不適用于當前需求。2000年，Song等人[1]提出了可搜索加密(Searchable Encryption, SE)的概念，實現了不解密密文情況下對密文的快速檢索。2004 年，Boneh等人[2]首次提出了公鑰可搜索加密的概念，隨后，具有連接關鍵詞[3,4]、模糊關鍵詞[5]、動態關鍵字[6,7]、子集關鍵字[8]等功能的公鑰可搜索加密方案也相繼被提出。但是在實際應用中，數據擁有者往往無法預先確定所有訪問者的信息，但是又希望能控制共享數據的訪問權限，并且實現一對多的通信模式，顯然傳統的公鑰可搜索加密和基于身份的可搜索加密技術已經不能解決這一難題，而基于屬性關鍵字搜索(Attribute-Based Keyword Search, ABKS)的加密機制引起眾多學者的關注。

基于屬性關鍵詞搜索加密機制是一對多的公鑰加密搜索方式：數據屬主可以使用自己定義的訪問結構加密關鍵字和共享信息，屬性集滿足訪問結構的用戶才能獲得搜索授權和解密操作。文獻[9]在屬性加密方案[10]的基礎上提出基于屬性的密文檢索方案，該方案實現了快速關鍵字搜索，但沒有對搜索結果進行驗證。Ameri等人[11]在密鑰策略屬性加密方案[12]的基礎上提出一個密鑰策略的可搜索加密方案，該方案在搜索令牌中加入時間戳，只能提取在指定時間間隔內生成的密文。Miao 等人[13,14]提出了一種可驗證的關鍵字搜索方案，通過對每個密文文檔設置簽名，由第三方審計檢驗返回密文的正確性，但是該方案密文大小與屬性的個數成正比，導致搜索時間隨屬性的增加而增加。Ballard等人[15]提出動態的關鍵字搜索方案，采用Merkle 樹實現數據的完整性認證，但是，該認證方法不支持多關鍵字搜索。為解決上述問題，文獻[7]提出完整性驗證的多關鍵字搜索方案，減少了計算量。文獻[16]提出支持屬性撤銷的關鍵字搜索方案，該方案將繁重的代理重加密工作交給授權中心，造成授權中心的瓶頸。隨后一些支持代理重加密等特點的關鍵字搜索方案相繼被提出[17,18]，但是由于將訪問結構和索引一起發送給云服務器，導致訪問結構信息泄露問題。文獻[19]提出了隱藏訪問結構的ABKS方案，并支持屬性撤銷，但該方案只適合單個關鍵字的搜索。還出現了一些具有其它特色的搜索方案[20,21]，但這些方案都沒有考慮關鍵字搜索。

本文將關鍵字搜索技術與ABE技術結合，提出具有隱私保護的完整性可驗證的關鍵字搜索方案，實現了細粒度的搜索授權，主要工作有：(1)方案采用了一個有序多值屬性訪問結構和有序多值屬性集，固定每個屬性的位置，減少參數及相關計算，提高了方案的效率；(2)方案采用倒序索引結構和Merkle哈希樹生成數據認證樹，實現對云服務器返回密文的完整性認證，防止云服務器對數據的惡意篡改和返回不正確的結果；(3)為了防止訪問結構泄露和保護用戶身份隱私性，采用hash及對運算實現對訪問結構的隱藏；(4)外包解密技術減少了用戶側的計算開銷。

2 準備工作

2.1 判定性DL(Decisional Linear)假設

2.2 有序多值屬性訪問結構

2.3 Merkle 哈希樹

2.4 倒序索引結構與數據認證樹

表1 屬性值

圖1 Merkel樹

3 可實現隱私保護的關鍵字搜索方案

3.1 系統模型

圖2 倒序索引列表

圖3 數據認證

圖4 系統模型

本文方案主要有4個實體(如圖4)：數據屬主(DO)，數據用戶(DU)，授權中心(TA)，云服務器(CSP)。TA是可信的，為系統產生公鑰和主密鑰，并為用戶產生私鑰，用戶的私鑰與自身屬性相關。DO決定訪問策略并加密對稱鑰，建立關鍵字索引，為每個關鍵字建立密文認證樹，將索引、認證樹、密文文檔發送給云服務器。CSP是誠實又好奇的，它會誠實地遵守協議但又試圖解密文檔，CSP分為存儲服務器和解密服務器。存儲服務器存儲和管理數據屬主上傳的關鍵字索引、加密文檔，并通過判斷用戶上傳的門限值提供相應的檢索服務。DU收到密文，將其外包給解密服務器進行部分解密，并檢驗返回密文與外包解密的正確性。

3.2 方案描述

圖5 訪問結構的隱藏

圖6 用戶屬性集的轉化

4 正確性分析與安全性證明

4.1 正確性分析

4.2 安全性證明

5 性能分析

5.1 理論分析

5.2 實驗分析

本小節對本方案和文獻[13,19]的密鑰生成算法、門限生成算法、搜索和解密算法進行了實驗仿真。仿真平臺Windows 10，AMD A8-6410 APU with AMD Randeon R5 Graphics 2.00 GHz，內存為8 GB，代碼庫PBC(Paring-Based Cryptography[22])，使用大素數為512位。從圖7-圖10可以看出，本文方案與文獻[13]方案在密鑰生成、門限生成、搜索階段效率幾乎持平，但是在解密階段效率高很多，而相比文獻[19]的各個階段，本文方案是高效的。圖11和圖12分別給出本文方案在屬性個數變化時多關鍵字情形下，門限生成時間與搜索時間，從圖中可以得出，門限生成與屬性個數和各關鍵字個數無關，而搜索階段僅與關鍵字個數有關，其余兩個方案不支持多關鍵字搜索。

6 結束語

本文就不可信云環境下，提出具有隱私保護的完整性可驗證的ABKS方案。方案提出有序多值屬性訪問結構和有序多值屬性集，固定每個屬性的位置，減少參數及相關計算，提高了方案的效率；采用Hash和對運算實現訪問結構的隱藏，保護了訪問結構的安全性與用戶身份的隱私性；在密鑰生成時計算具體屬性取值的哈希值，從而達到區別多值屬性取值的不同；同時，采用倒序索引結構和Merkle樹建立數據認證樹，實現對云服務器返回密文的完整性認證并確保外包解密的正確性，防止云服務器對數據的惡意篡改和返回不正確的結果。此外，充分利用云的計算能力，支持外包解密以降低用戶側的計算量。安全性分析和實驗表明，本文方案可實現云中共享數據的可驗證性、關鍵字不可區分性和關鍵字不可鏈接性，且是高效的。在未來工作中，將探索云存儲中的關鍵字的更新和文件的刪除和添加。

表2 功能比較

表3 通信開銷比較

表4 計算開銷比較

圖7 密鑰生成階段

圖8 門限生成階段

圖9 搜索階段

圖10 解密階段

圖11 多關鍵字搜索階段

圖12 多關鍵字門限生成階段