基于动态累加器的去中心化加密搜索方案

张琰，王瑾璠，齐竹云，杨镕玮，汪漪



基于动态累加器的去中心化加密搜索方案

张琰1,2，王瑾璠1,2，齐竹云2，杨镕玮1,2，汪漪1,2

（1. 南方科技大学未来网络研究院，广东 深圳 518055； 2. 鹏城实验室网络通信研究中心，广东 深圳 518055）

近年来区块链技术取得广泛关注，涌现出众多基于区块链技术的新型应用，其中以StorJ、Filecoin为代表的去中心化存储应用取得了较好的市场反响。对比传统中心化存储，去中心化存储为用户提供了全新的数据存储思路，令用户在获得更好的服务伸缩性的同时，有效降低数据存储的成本。但在现有的去中心化存储方案中，用户的隐私不能得到有效保护。基于此，介绍了一种利用加密搜索技术对去中心化存储方案进行加强的方法。新方法将动态累加器算法引入加密搜索过程中，保障用户存储内容隐私并提供了更好的加密搜索性能。

区块链；去中心化存储；加密搜索；动态累加器

1 引言

区块链概念被提出和首次实现来自于中本聪2009年1月3日所发表的比特币[1]。近年来，区块链技术[2-3]取得持续发展，其中最具代表性的成果之一是由Vitalik Buterin在2013年提出的以太坊（Ethereum）及以太坊虚拟机（EVM），令区块链网络中的节点具备执行图灵完备代码的能力，从而使区块链网络成为去中心化应用（DApp）的部署平台。区块链技术当前仍处于探索及持续发展的状态，但基于区块链技术构建的新型应用已经开始部署并取得了一定的成功。以StorJ、FileCoin为代表的去中心化存储应用正在逐步被人们所接受。

去中心化存储为用户提供了更灵活的扩展存储方式以及更低的存储成本，但用户存储安全及隐私的相关问题也逐渐暴露出来。加密搜索[4-8]技术是解决这一问题的关键方法，其基本原理是通过关键词搜索及对关键词信息、文件信息进行加密达到保护隐私的目的。在传统中心化存储方案中，加密搜索在保护文件安全及客户隐私方面已经获得了成功运用。目前已有一些工作[9]尝试将加密搜索引入去中心存储方案中，但加密搜索方法在去中心化运用中的使用仍具有较大的可优化空间。

本文阐述了一种基于动态累加器的去中心化加密搜索方案，该方案涉及区块链智能合约、加密搜索技术以及动态累加器技术。本文的主要贡献如下。

1) 保护用户隐私的安全去中心化数据存储：将加密搜索技术运用于去中心化存储中，证明了加密搜索技术在去中心化存储场景中运用的技术可行性，在保障存储数据安全的同时保护了用户隐私。

2) 改善加密搜索效率：引入动态累加器[10-11]到加密搜索方案中，将搜索令牌（Token）比对次数由()=次降低到()=次（为文件数，为每个文件拥有的平均搜索关键字数）。

2 背景知识

2.1 区块链技术概述

从数据形态上看，区块链是一串有序串联的数据块（block）所形成的链条（chain），且每个新增数据块都会包含前一数据块的特征信息（即区块的散列值）。当包含了前一区块散列值的新增数据块被加入区块链上，前一区块中所包含数据的特征值将被唯一确定并记录。因此，数据一旦写入区块链，将被认为是不可篡改、不可删除的，从而形成了前后相连、环环相扣的链状结构。

与传统的分布式数据库（distributed database）改善高并发数据访问性能的诉求不同，区块链基于密码学理论及创新的数据结构，能够在缺乏信任的分布式网络（对等网络）环境中保证极致的链上数据的强一致性和不可篡改特性。目前，区块链最成功的应用是以比特币为代表的加密货币（cryptocurrency）。在加密货币场景中，区块链是所有用户所共同编写的“超级账本”，所有加密货币交易（transaction）都会被永久记录在区块链上。

2.2 去中心化存储

随着区块链生态的逐步发展，一系列去中心化存储应用涌现出来，提供了新型的商业模式。区块链技术的出现，使人们有机会摆脱第三方出租自己的存储空间，有效降低云存储的成本，同时也避免了存储资源限制。

在现有去中心化云存储系统中，通过技术手段验证服务的可用性、安全性等，利用区块链特性对服务相关信息进行记录与清算，形成对消费者、服务提供者行为的约束，保证整个系统的良好运转。

2.3 加密搜索

传统的搜索技术是基于明文的，用户提交的查询关键字及存储信息均以明文形式存在，恶意服务提供商（service provider）、运营商、黑客都有机会获取或截获用户的查询关键字、查询结果及存储的明文数据等信息，造成严重的隐私泄露及数据安全风险。为了解决这一问题，加密搜索技术[4-9]应运而生，提供了对密文进行搜索查询的方案，在这种模式下，搜索过程将不会泄露查询关键字等任何与明文有关的信息，有效保护了用户数据安全及隐私。目前，加密搜索技术已经在云计算场景中得到了较好的应用。

2.4 动态累加器

动态累加器由Camenisch等[10]首先提出，其作用是将一组值累加成一个值，使输入的任意一个值证明自己被累加到这个累加值中，并且，动态累加器允许动态地添加和删除一些值。2008年，Wang等[11]对动态累加器做了正式的定义。下面将对动态累加器做形式化描述。

3 基于动态累加器的加密搜索方案设计

3.1 功能定义

本节详细介绍本文方案中的主要算法，其中算法1、2、4由用户客户端本地完成，算法3、5由区块链中智能合约完成。当用户添加新文件或新的搜索令牌时，由客户端本地完成密钥生成、加密文件、生成加密搜索令牌及累加值算法，而后区块链中的智能合约完成建立索引过程。当用户执行搜索操作时，由客户端本地完成搜索令牌生成算法，智能合约执行对应的搜索过程返回搜索结果。

算法1 初始化算法

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

5) 客户端生成空列表。

6) 如果这是一个新文件且没有动态累加值，

算法3 区块链添加搜索令牌算法

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

算法5 搜索算法

图1 系统基本流程

3.2 系统流程

4 方案分析

4.1 令牌、动态累加器的安全性分析

1) 令牌安全性

2) 动态累加器安全性

4.2 性能分析

图2 给定文件，keyword数量增加，搜索令牌比对次数（仅一个文件）对比

图3 keyword数量不变，文件数量增加，搜索令牌比对次数（10 Keyword/file）对比

5 结束语

本文首先阐述了区块链技术、加密搜索和动态累加器的相关背景知识。针对现有的去中心化存储场景阐述了基于加密搜索方法的去中心化存储数据安全及用户隐私保护方案，提出了基于动态累加器算法的加密搜索改进方案并通过实验证明了该方案的可行性及有益效果。实验结果表明，新方案有效提升了去中心化存储场景中的加密搜索效率，有效保护用户数据安全及隐私。

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

[2] 戴千一, 徐开勇, 周致成, 等. 分布式网络环境下给予区块链的密钥管理方案[J]. 网络与信息安全学报, 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] 章峰, 史博轩, 蒋文保. 区块链关键技术及应用研究综述[J]. 网络与信息安全学报, 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]. 网络与信息安全学报, 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− ），男，河南郑州人，硕士，鹏城实验室工程师，主要研究方向为区块链、信息安全。

王瑾璠（1990− ），男，安徽合肥人，博士，南方科技大学、鹏城实验室助理研究员，主要研究方向为网络架构、区块链、云计算、信息安全。

齐竹云（1983− ），女，山东寿光人，鹏城实验室高级工程师，主要研究方向为信息中心网络、软件定义网络、区块链、软件工程。

杨镕玮（1990− ），女，山西侯马人，南方科技大学及鹏城实验室访问博士生，主要研究方向为网络测量、高效算法设计。

汪漪（1983− ），男，浙江杭州人，博士，南方科技大学副教授，主要研究方向为未来网络体系架构、信息中心网络、软件定义网络、高性能网络器件设计与实现、高性能网络设备、网络测量、智能网络体系架构、网络智能化。

2018−12−07；

2019−02−17

汪漪，wy@icee.org

国家自然科学基金资助项目（No.61872420）

张琰，王瑾璠，齐竹云, 等.基于动态累加器的去中心化加密搜索方案[J]. 网络与信息安全学报, 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.