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

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

?

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

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

（1. 南方科技大學(xué)未來(lái)網(wǎng)絡(luò)研究院，廣東 深圳 518055； 2. 鵬城實(shí)驗(yàn)室網(wǎng)絡(luò)通信研究中心，廣東 深圳 518055）

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

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

1 引言

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

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

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

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

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

2 背景知識(shí)

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

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

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

2.2 去中心化存儲(chǔ)

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

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

2.3 加密搜索

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

2.4 動(dòng)態(tài)累加器

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

3 基于動(dòng)態(tài)累加器的加密搜索方案設(shè)計(jì)

3.1 功能定義

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

算法1 初始化算法

算法2 客戶(hù)端添加令牌算法

5) 客戶(hù)端生成空列表。

6) 如果這是一個(gè)新文件且沒(méi)有動(dòng)態(tài)累加值，

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

算法4 客戶(hù)端生成搜索令牌生成算法

算法5 搜索算法

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

3.2 系統(tǒng)流程

4 方案分析

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

1) 令牌安全性

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

4.2 性能分析

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

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

5 結(jié)束語(yǔ)

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

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

[2] 戴千一, 徐開(kāi)勇, 周致成, 等. 分布式網(wǎng)絡(luò)環(huán)境下給予區(qū)塊鏈的密鑰管理方案[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 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ū)塊鏈關(guān)鍵技術(shù)及應(yīng)用研究綜述[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 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ìn)展綜述[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 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? ），男，河南鄭州人，碩士，鵬城實(shí)驗(yàn)室工程師，主要研究方向?yàn)閰^(qū)塊鏈、信息安全。

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

齊竹云（1983? ），女，山東壽光人，鵬城實(shí)驗(yàn)室高級(jí)工程師，主要研究方向?yàn)樾畔⒅行木W(wǎng)絡(luò)、軟件定義網(wǎng)絡(luò)、區(qū)塊鏈、軟件工程。

楊镕瑋（1990? ），女，山西侯馬人，南方科技大學(xué)及鵬城實(shí)驗(yàn)室訪(fǎng)問(wèn)博士生，主要研究方向?yàn)榫W(wǎng)絡(luò)測(cè)量、高效算法設(shè)計(jì)。

汪漪（1983? ），男，浙江杭州人，博士，南方科技大學(xué)副教授，主要研究方向?yàn)槲磥?lái)網(wǎng)絡(luò)體系架構(gòu)、信息中心網(wǎng)絡(luò)、軟件定義網(wǎng)絡(luò)、高性能網(wǎng)絡(luò)器件設(shè)計(jì)與實(shí)現(xiàn)、高性能網(wǎng)絡(luò)設(shè)備、網(wǎng)絡(luò)測(cè)量、智能網(wǎng)絡(luò)體系架構(gòu)、網(wǎng)絡(luò)智能化。

2018?12?07；

2019?02?17

汪漪，wy@icee.org

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61872420）

張琰，王瑾璠，齊竹云, 等.基于動(dòng)態(tài)累加器的去中心化加密搜索方案[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 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.