基于動態(tài)累加器的去中心化加密搜索方案

張琰，王瑾璠，齊竹云，楊镕瑋，汪漪

?

基于動態(tài)累加器的去中心化加密搜索方案

張琰1,2，王瑾璠1,2，齊竹云2，楊镕瑋1,2，汪漪1,2

（1. 南方科技大學未來網(wǎng)絡研究院，廣東 深圳 518055； 2. 鵬城實驗室網(wǎng)絡通信研究中心，廣東 深圳 518055）

近年來區(qū)塊鏈技術取得廣泛關注，涌現(xiàn)出眾多基于區(qū)塊鏈技術的新型應用，其中以StorJ、Filecoin為代表的去中心化存儲應用取得了較好的市場反響。對比傳統(tǒng)中心化存儲，去中心化存儲為用戶提供了全新的數(shù)據(jù)存儲思路，令用戶在獲得更好的服務伸縮性的同時，有效降低數(shù)據(jù)存儲的成本。但在現(xiàn)有的去中心化存儲方案中，用戶的隱私不能得到有效保護。基于此，介紹了一種利用加密搜索技術對去中心化存儲方案進行加強的方法。新方法將動態(tài)累加器算法引入加密搜索過程中，保障用戶存儲內(nèi)容隱私并提供了更好的加密搜索性能。

區(qū)塊鏈；去中心化存儲；加密搜索；動態(tài)累加器

1 引言

區(qū)塊鏈概念被提出和首次實現(xiàn)來自于中本聰2009年1月3日所發(fā)表的比特幣[1]。近年來，區(qū)塊鏈技術[2-3]取得持續(xù)發(fā)展，其中最具代表性的成果之一是由Vitalik Buterin在2013年提出的以太坊（Ethereum）及以太坊虛擬機（EVM），令區(qū)塊鏈網(wǎng)絡中的節(jié)點具備執(zhí)行圖靈完備代碼的能力，從而使區(qū)塊鏈網(wǎng)絡成為去中心化應用（DApp）的部署平臺。區(qū)塊鏈技術當前仍處于探索及持續(xù)發(fā)展的狀態(tài)，但基于區(qū)塊鏈技術構(gòu)建的新型應用已經(jīng)開始部署并取得了一定的成功。以StorJ、FileCoin為代表的去中心化存儲應用正在逐步被人們所接受。

去中心化存儲為用戶提供了更靈活的擴展存儲方式以及更低的存儲成本，但用戶存儲安全及隱私的相關問題也逐漸暴露出來。加密搜索[4-8]技術是解決這一問題的關鍵方法，其基本原理是通過關鍵詞搜索及對關鍵詞信息、文件信息進行加密達到保護隱私的目的。在傳統(tǒng)中心化存儲方案中，加密搜索在保護文件安全及客戶隱私方面已經(jīng)獲得了成功運用。目前已有一些工作[9]嘗試將加密搜索引入去中心存儲方案中，但加密搜索方法在去中心化運用中的使用仍具有較大的可優(yōu)化空間。

本文闡述了一種基于動態(tài)累加器的去中心化加密搜索方案，該方案涉及區(qū)塊鏈智能合約、加密搜索技術以及動態(tài)累加器技術。本文的主要貢獻如下。

1) 保護用戶隱私的安全去中心化數(shù)據(jù)存儲：將加密搜索技術運用于去中心化存儲中，證明了加密搜索技術在去中心化存儲場景中運用的技術可行性，在保障存儲數(shù)據(jù)安全的同時保護了用戶隱私。

2) 改善加密搜索效率：引入動態(tài)累加器[10-11]到加密搜索方案中，將搜索令牌（Token）比對次數(shù)由()=次降低到()=次（為文件數(shù)，為每個文件擁有的平均搜索關鍵字數(shù)）。

2 背景知識

2.1 區(qū)塊鏈技術概述

從數(shù)據(jù)形態(tài)上看，區(qū)塊鏈是一串有序串聯(lián)的數(shù)據(jù)塊（block）所形成的鏈條（chain），且每個新增數(shù)據(jù)塊都會包含前一數(shù)據(jù)塊的特征信息（即區(qū)塊的散列值）。當包含了前一區(qū)塊散列值的新增數(shù)據(jù)塊被加入?yún)^(qū)塊鏈上，前一區(qū)塊中所包含數(shù)據(jù)的特征值將被唯一確定并記錄。因此，數(shù)據(jù)一旦寫入?yún)^(qū)塊鏈，將被認為是不可篡改、不可刪除的，從而形成了前后相連、環(huán)環(huán)相扣的鏈狀結(jié)構(gòu)。

與傳統(tǒng)的分布式數(shù)據(jù)庫（distributed database）改善高并發(fā)數(shù)據(jù)訪問性能的訴求不同，區(qū)塊鏈基于密碼學理論及創(chuàng)新的數(shù)據(jù)結(jié)構(gòu)，能夠在缺乏信任的分布式網(wǎng)絡（對等網(wǎng)絡）環(huán)境中保證極致的鏈上數(shù)據(jù)的強一致性和不可篡改特性。目前，區(qū)塊鏈最成功的應用是以比特幣為代表的加密貨幣（cryptocurrency）。在加密貨幣場景中，區(qū)塊鏈是所有用戶所共同編寫的“超級賬本”，所有加密貨幣交易（transaction）都會被永久記錄在區(qū)塊鏈上。

2.2 去中心化存儲

隨著區(qū)塊鏈生態(tài)的逐步發(fā)展，一系列去中心化存儲應用涌現(xiàn)出來，提供了新型的商業(yè)模式。區(qū)塊鏈技術的出現(xiàn)，使人們有機會擺脫第三方出租自己的存儲空間，有效降低云存儲的成本，同時也避免了存儲資源限制。

在現(xiàn)有去中心化云存儲系統(tǒng)中，通過技術手段驗證服務的可用性、安全性等，利用區(qū)塊鏈特性對服務相關信息進行記錄與清算，形成對消費者、服務提供者行為的約束，保證整個系統(tǒng)的良好運轉(zhuǎn)。

2.3 加密搜索

傳統(tǒng)的搜索技術是基于明文的，用戶提交的查詢關鍵字及存儲信息均以明文形式存在，惡意服務提供商（service provider）、運營商、黑客都有機會獲取或截獲用戶的查詢關鍵字、查詢結(jié)果及存儲的明文數(shù)據(jù)等信息，造成嚴重的隱私泄露及數(shù)據(jù)安全風險。為了解決這一問題，加密搜索技術[4-9]應運而生，提供了對密文進行搜索查詢的方案，在這種模式下，搜索過程將不會泄露查詢關鍵字等任何與明文有關的信息，有效保護了用戶數(shù)據(jù)安全及隱私。目前，加密搜索技術已經(jīng)在云計算場景中得到了較好的應用。

2.4 動態(tài)累加器

動態(tài)累加器由Camenisch等[10]首先提出，其作用是將一組值累加成一個值，使輸入的任意一個值證明自己被累加到這個累加值中，并且，動態(tài)累加器允許動態(tài)地添加和刪除一些值。2008年，Wang等[11]對動態(tài)累加器做了正式的定義。下面將對動態(tài)累加器做形式化描述。

3 基于動態(tài)累加器的加密搜索方案設計

3.1 功能定義

本節(jié)詳細介紹本文方案中的主要算法，其中算法1、2、4由用戶客戶端本地完成，算法3、5由區(qū)塊鏈中智能合約完成。當用戶添加新文件或新的搜索令牌時，由客戶端本地完成密鑰生成、加密文件、生成加密搜索令牌及累加值算法，而后區(qū)塊鏈中的智能合約完成建立索引過程。當用戶執(zhí)行搜索操作時，由客戶端本地完成搜索令牌生成算法，智能合約執(zhí)行對應的搜索過程返回搜索結(jié)果。

算法1 初始化算法

算法2 客戶端添加令牌算法

5) 客戶端生成空列表。

6) 如果這是一個新文件且沒有動態(tài)累加值，

算法3 區(qū)塊鏈添加搜索令牌算法

算法4 客戶端生成搜索令牌生成算法

算法5 搜索算法

圖1 系統(tǒng)基本流程

3.2 系統(tǒng)流程

4 方案分析

4.1 令牌、動態(tài)累加器的安全性分析

1) 令牌安全性

2) 動態(tài)累加器安全性

4.2 性能分析

圖2 給定文件，keyword數(shù)量增加，搜索令牌比對次數(shù)（僅一個文件）對比

圖3 keyword數(shù)量不變，文件數(shù)量增加，搜索令牌比對次數(shù)（10 Keyword/file）對比

5 結(jié)束語

本文首先闡述了區(qū)塊鏈技術、加密搜索和動態(tài)累加器的相關背景知識。針對現(xiàn)有的去中心化存儲場景闡述了基于加密搜索方法的去中心化存儲數(shù)據(jù)安全及用戶隱私保護方案，提出了基于動態(tài)累加器算法的加密搜索改進方案并通過實驗證明了該方案的可行性及有益效果。實驗結(jié)果表明，新方案有效提升了去中心化存儲場景中的加密搜索效率，有效保護用戶數(shù)據(jù)安全及隱私。

[1] NAKAMOTO S. Bitcoin: a peer-to-peer electronic cash system[R].

[2] 戴千一, 徐開勇, 周致成, 等. 分布式網(wǎng)絡環(huán)境下給予區(qū)塊鏈的密鑰管理方案[J]. 網(wǎng)絡與信息安全學報, 2018, 4(9): 23-35.

DAI Q Y, XU K Y, ZHOU Z C et al. Blockchain-based key management scheme for distributed networks[J]. Journal of Network and Information Security, 2018, 4(9): 23-35.

[3] 章峰, 史博軒, 蔣文保. 區(qū)塊鏈關鍵技術及應用研究綜述[J]. 網(wǎng)絡與信息安全學報, 2018 ,4(4): 22-29.

ZHANG F, SHI B X, JIANG W B. Review of key technology and it’s application of blockchain[J]. Chinese Journal of Network and Information Security, 2018, 4(4): 22-29.

[4] 李穎, 馬春光. 可搜索加密研究進展綜述[J]. 網(wǎng)絡與信息安全學報, 2018, 4(7): 13-21. LI Y, MA C G. Overview of searchable encryption research[J]. Journal of Network and Information Security, 2018, 4(7): 13-21.

[5] CURTMOLA S, GARAY J A, KAMARA S, et al. Searchable symmetric encryption: improved definitions and efficient constructions[J]. Journal of Computer Security, 2011, 19(5): 815-934.

[6] CASH D, JAEGER J, JARECKI S, et al. Dynamic searchable encryption in very large databases: data structures and implementation[C]// NDSS. 2014.

[7] KAMARA S, PAPAMANTHOU C, ROEDER T. Dynamic searchable symmetric encryption[C]//ACM CCS. 2012.

[8] HAHN F, KERSCHBAUM F. Searchable encryption with secure and efficient updates[C]//ACM CCS. 2014.

[9] CAI C J, YUAN X L, WANG C. Towards trustworthy and private keyword search in encrypted decentralized storage[C]// Communication and Information Systems Security Symposium. 2017.

[10] CAMENISCH J, LYSYANSKAYA A. Dynamic accumulators and application to efficient revocation of anonymous credentials[M]// Advances in Cryptology[C]//CRYPTO. 2002:61-76.

[11] WANG P, WANG H, PIEPRZYK J. A new dynamic accumulator for batch updates[C]//International Conference Information and Communications Security (ICICS 2007). 2007: 98-112.

Decentralized searchable encryption scheme based on dynamic accumulator

ZHANG Yan1,2, WANGJinfan1,2, QI Zhuyun2, YANG Rongwei1,2, WANG Yi1,2

1. Institute of Future Networks, Southern University of Science and Technology, Shenzhen 518055, China 2. Research Center of Networks and Communications, Pengcheng Laboratory, Shenzhen 518055, China

Since the flourish of the blockchain technology, a series of applications based on blockchain technology are emerging, and the decentralized storage service becomes the killer App in the decentralized markets, such as StorJ, Filecoin. Comparing with the centralized storage, decentralized storage are more secure, cheaper and more scalable. However, client’s privacy cannot be protected in existed decentralized storage apps. The idea of implementing the searchable encryption scheme with decentralized storage was proposed to improve the user’s privacy and utilizing the dynamic accumulator to improve the search efficiency of the searchable encryption scheme.

blockchain, decentralized storage, searchable encryption, dynamic accumulator

The National Natural Science Foundation of China (No.61872420)

TP309.2

A

10.11959/j.issn.2096?109x.2019014

張琰（1992? ），男，河南鄭州人，碩士，鵬城實驗室工程師，主要研究方向為區(qū)塊鏈、信息安全。

王瑾璠（1990? ），男，安徽合肥人，博士，南方科技大學、鵬城實驗室助理研究員，主要研究方向為網(wǎng)絡架構(gòu)、區(qū)塊鏈、云計算、信息安全。

齊竹云（1983? ），女，山東壽光人，鵬城實驗室高級工程師，主要研究方向為信息中心網(wǎng)絡、軟件定義網(wǎng)絡、區(qū)塊鏈、軟件工程。

楊镕瑋（1990? ），女，山西侯馬人，南方科技大學及鵬城實驗室訪問博士生，主要研究方向為網(wǎng)絡測量、高效算法設計。

汪漪（1983? ），男，浙江杭州人，博士，南方科技大學副教授，主要研究方向為未來網(wǎng)絡體系架構(gòu)、信息中心網(wǎng)絡、軟件定義網(wǎng)絡、高性能網(wǎng)絡器件設計與實現(xiàn)、高性能網(wǎng)絡設備、網(wǎng)絡測量、智能網(wǎng)絡體系架構(gòu)、網(wǎng)絡智能化。

2018?12?07；

2019?02?17

汪漪，wy@icee.org

國家自然科學基金資助項目（No.61872420）

張琰，王瑾璠，齊竹云, 等.基于動態(tài)累加器的去中心化加密搜索方案[J]. 網(wǎng)絡與信息安全學報, 2019, 5(2): 23-29.

ZHANG Y, WANG J F, QI Z Y, et al. Decentralized searchable encryption scheme based on dynamic accumulator[J]. Chinese Journal of Network and Information Security, 2019, 5(2): 23-29.