基于区块链的公平可靠密文检索系统*

唐梦菲, 蒋 芃, 张芷璇, 李彦霖, 祝烈煌

北京理工大学 网络空间安全学院, 北京 100081

1 引言

云计算因其便利访问、弹性服务和按需付费等特点, 受到了广泛关注, 数据存储形式大多从本地存储转变为外包存储, 来降低本地的存储和计算代价. 用户在将数据外包给第三方云服务器后, 失去了对这些存储数据的直接控制, 导致数据极大程度上面临各种威胁, 比如数据可能会被窃取和篡改等. 因此数据安全是外包存储必须面临的一个重要问题. 随着《中华人民共和国数据安全法(草案)》的发布, 数据安全已然成为了国家网络安全保障中的重要一环. 为了保护数据的机密性, 传统的方法是采用先加密再存储的方式, 这给数据的有效查询和利用造成了一定的困难. 当用户想要使用某个特定数据时, 若把服务器上所有密文下载到本地, 解密之后再进行搜索, 会造成巨大的时间与空间开销; 若把密钥给服务器, 让服务器解密后再进行查询, 数据的机密性无法得到保障.

可搜索加密机制(Searchable Encryption, SE) 应运而生[1]. 用户首先使用SE 机制对数据进行加密并将密文存储在服务器中, 当用户需要搜索某个关键字时, 便将该关键字的搜索口令发送给云服务器, 云服务器将接收到的搜索口令与各个密文进行匹配, 若匹配成功则说明该密文中包含此关键字, 遍历后云服务器将匹配成功的密文返回给用户. 根据所使用的密码学机制的不同, 现有的可搜索加密机制分为公钥可搜索加密(Public key Encryption with Keyword Search, PEKS)[2]和对称密钥可搜索加密(Symmetrickey Searchable Encryption, SSE)[3]. 相比SSE 而言, PEKS 因无需复杂的密钥管理且能实现数据共享,成为了国内外研究的热点. 在PEKS 机制中, 数据以密文的形式存储在服务器中, 用户通过提供关键字陷门给服务器, 让服务器能够在对关键字相关信息一无所知的情况下检索出相应的密文, 这种密文检索方式可以有效进行密文形式的查询, 同时保障了用户的关键字隐私. 公平性和可靠性是用户判断数据查询服务的重要标准. 本文中, 公平性指的是各个参与者能够获得自己应该获得的酬劳, 并且酬劳分配结果能得到广泛支持; 可靠性是指系统能够在规定时间内正确地完成检索任务. 通常的可搜索加密机制会默认服务器能够诚实且严格地执行搜索协议, 然而, 各种利益诉求和软件入侵都会引起服务器的恶意转变, 导致其偏离搜索协议, 只返回部分检索结果甚至是不正确的检索结果, 而用户所支付的费用不会被返还. 这种恶意服务器严重破坏了检索过程中的公平性和可靠性. 如何面向恶意服务器实现公平可靠的密文检索方案成为必须解决的问题.

2008 年, 中本聪[4]首次提出了区块链的概念. 区块链是以分布式时间戳服务器以及P2P 数据传输网络为基础构建的完全无需第三方的分布式账本, 它的目标是实现一个只允许添加、不允许删除的去中心化分布式账本. 区块链由全网节点共同维护, 共识机制无需可信的第三方, 分布式的网络架构可以避免中心节点受到攻击或破坏, 系统稳定性较高, 这些优势能够较好地用于解决数据可靠性的问题. Szabo[5]在1994 年提出了智能合约的概念, 智能合约是相互不信任的参与者之间的协议. Clack[6]提出区块链可以作为底层技术用来支持智能合约, 可以让智能合约在没有第三方干涉的情况下进行可信交易. 智能合约内置了丰富的转账功能, 它的这些机制可以较好地判断合约参与方的诚信并根据他们做出的行为分配相应的激励, 从而可以较好地保障公平性.

为了解决目前PEKS 方案中出现的公平性和可靠性的问题, 本文将区块链技术与公钥可搜索加密技术相结合, 通过编写智能合约来控制检索各方的参与. 我们使用区块链来管理和代替第三方服务器, 可以保障存储的数据是可信的、不可篡改的, 可以解决原有的PEKS 方案及其优化版本的安全性需要依赖诚实服务器的问题. 此类基于区块链的密文检索系统可以应用在一些对可靠性要求较高的场景中, 如医疗档案管理、学历档案管理和犯罪记录等. 在一次搜索中, 把搜索数据过程中的交易记录在区块链中, 链中数据不可篡改并且所有节点都可验证该交易, 而区块链的共识机制保障了每个以太坊节点的一致性. 这种情形下, 交易的结果具有可靠性. 区块链可以保障智能合约各个参与方的激励发放是准确和可靠的, 那么搜索的公平性也就得到了保障. 现有的区块链与可搜索加密方案结合的案例都是将区块链与对称密钥可搜索加密机制相结合, 由于对称密钥可搜索加密机制的密钥不可公开, 所以数据拥有者面临着大量密钥管理工作, 并且不支持加密数据的共享, 而区块链由于共识机制的存在是面向共享的, 所以两者的结合会丧失区块链原有的共享性. 本文将区块链与公钥可搜索加密机制进行结合, 既可以利用区块链的去中心化与不可篡改性保障数据的可靠与安全, 也可以在方案中继续延续区块链的共享性, 从而实现加密数据的可靠与共享之间的平衡.

本文旨在设计和实现一个基于区块链公钥可搜索加密系统(Blockchain-based PEKS), 此系统具有关键字隐私性、公平性和可靠性, 可以解决恶意服务器带来的安全问题. 本文的贡献主要有以下三点.

(1) 本文在PEKS 方案的基础上, 结合区块链技术, 提出了一个基于区块链的公钥加密可搜索方案通用架构.

(2) 本文采用了分层的形式, 利用智能合约构造了一个四层级化的基于区块链公钥可搜索加密系统.在系统设计中, 不同层具有不同的功能与角色, 每层之间的交互保证整个系统稳定运行, 从而实例化一个安全可靠的基于区块链公钥可搜索加密方案.

(3) 基于上述所提出的具体方案, 本文实现了基于区块链公钥加密可搜索的原型系统, 并对原型系统进行了性能测试与分析, 证明了本文构造的可行性与实用性.

2 研究现状

本节介绍公钥可搜索加密PEKS、区块链和智能合约等技术的研究现状, 以支撑基于区块链的公钥可搜索加密系统的设计.

2.1 PEKS

PEKS 是在大型数据库中检索加密数据的方法之一. 为了解决加密数据上信息如何有效查询利用的问题, Boneh 等人在2004 年提出了PEKS 模型来减少对称可搜索加密面临的复杂的密钥问题[2]. 在PEKS 体系中, 发送方在进行数据加密时, 使用所发信息的关键字和接收方的公钥来生成搜索密文; 而接收方解密时, 利用自己的私钥以及关键字生成关键字陷门(Trapdoor) 以匹配搜索密文, 当Trapdoor 与密文匹配成功后, 服务器将相应的数据密文返回给接收方.

近年来, 各类学者就查询方式和安全性两个重要方面, 对PEKS 展开了研究. 查询方式方面, Park[7]等人在2004 年提出了连接关键词公钥加密可搜索方案; Boneh 和Waters[8]在2007 年提出了在加密数据上的连接、交集、和范围查询; Yang 和Ma[9]在2016 年提出了增强查询表达能力和支持多关键字组合密文检索的方法; 而Zheng[10]等人和Jiang[11]等人提出了通过用户属性或指定关键字的方式来控制检索的方法. 安全性方面, Byun[12]等人和Yau[13]等人指出基本PEKS 方案不能抵抗关键词猜测攻击(Keyword Guessing Attack, KGA). Rhee 等人[14,15]提出了指定测试器的PEKS 模型, 从而抵抗外部KGA; Jiang 等人[16]通过在可搜索密文中引入发送方身份验证的方式, 实现了公钥可搜索在外部攻击下的安全性.

2.2 区块链技术

2008 年中本聪在比特币论坛首次提出区块链的概念[4]. 区块链是以分布式时间戳服务器以及P2P数据传输网络为基础构建的完全无需第三方的电子现金系统, 它的目标是实现一个只允许添加、不允许删除的去中心化分布式账本. 这个“账本” 以一个线性链表作为基层结构, 该链表由若干区块串联组成, 每个区块中记录了本区块的编号、签名、时间戳、交易信息以及前一个区块的哈希值. 网络中的任何节点都能通过共识机制的确认向区块链中申请添加一个新的区块, 同时可用计算哈希值的方式验证某区块是否合法. 区块链的结构如图1 所示.

图1 区块链的基层结构Figure 1 Basic structure of blockchain

区块链技术因其去中心化、高自治性等特点得以迅猛发展, 它的构造糅合了密码学、计算机科学、数学等诸多领域的知识.

交易(Transaction): 交易是导致账本状态改变的一次操作, 由输入、输出和数字签名三部分组成,一段时间内所有有效交易以某种结构(譬如Merkle 树) 连接到一起, 由矿工填充入区块.

区块(Block): 区块是对当前账本状态的一次共识, 记录着某段时间发生的全部交易信息.

链(Chain): 区块按照顺序线性连接形成链, 记录着整个账本的所有交易和状态变化.

共识协议(Consensus protocol): 区块链因其去中心化的性质并没有中央权威机构, 因此它依靠共识协议做出决策. 共识协议决定了记录下一个区块的矿工人选, 矿工们可以通过工作量证明(PoW) 或股权证明(PoS) 等方式来获取新区快的写入资格.

P2P 网络(P2P network): 区块链使用的P2P 网络是一种分布式应用程序体系结构, 其网络上的节点拥有相同的权力, 共同构成和维护整个网络的服务与数据的传输和写入. 这种去中心化的存储和传输方式天生具有不可篡改的特点, 部分节点遭受攻击也不会对整个系统造成大的影响.

哈希算法(Hash): 哈希算法是将变长输入映射为定长输出的二进制串的过程, 在加密和查找算法中应用广泛. 在区块链中, 数据的存储依靠哈希算法产生哈希值, 譬如, 使用SHA256 算法产生Merkle 树的结点信息, 使用Keccak-256 算法产生以太坊账户地址, 等等. 一个安全的哈希函数的输出与随机数串别无二致.

区块链范式(Blockchain paradigm): 将区块链看作一个基于交易的状态机[4], 每个状态包含了现实世界信息的数据, 譬如账户余额、随机数等. 每次记录交易之后, 状态机将从创始状态更新为最终状态.假设区块链当前状态为a, 在记录了事务Tx之后, 区块链状态变为at+1, 使用F表示区块链执行的任意计算, 则事务Tx记录前后的有效状态转换可以表示为:at+1=F(at,Tx).

2.3 以太坊智能合约

1994 年, Szabo 提出了智能合约的概念[5], Clack[6]讨论了如何利用区块链技术实现智能合约. 抽象地说, 智能合约是相互不信任的参与者之间的协议, 可以由区块链的共识机制自动执行从而可以不再依赖于中心化的权威机构. Buterin[17]指出, 目前最适合实现智能合约的区块链框架为以太坊. 以太坊[18]是基于P2P 网络与密码学建立起来的区块链机制, 在以太坊中智能合约可以通过图灵完备的编程语言来实现.

以太坊智能合约的正确执行是其有效性的必要条件, 否则敌手可能会通过篡改执行来从一个合法参与者中获取非法利润. 但是仅凭智能合约的正确执行还不足以确保合约的安全, Delmolino[19]和Luu[20]通过实际开发经验和对以太坊智能合约的静态分析发现了以太坊智能合约的几个漏洞. 其中的一些漏洞在现实生活中被黑客利用来攻击以太坊智能合约窃取利润.

以太坊漏洞主要来自三个层面: Solidity 编程语言、EVM 以太坊虚拟机[18]和区块链. Solidity 编程语言是以太坊上支持智能合约编写的编程语言, 编程人员的理解与Solidity 的实际语义的不一致产生了许多漏洞, 针对这些漏洞的攻击有: DAO 攻击[21]、“King of the Ether Throne”攻击[22,23]和GovernMental攻击[24,25]等. 智能合约漏洞的另一来源为EVM 以太坊虚拟机, 针对以太坊虚拟机安全漏洞的攻击主要有: Rubixi[26,27]攻击和GovernMental 攻击[24,25]. 还有针对区块链级别的攻击: GovernMental 攻击[24,25].

尽管Eyal[28]和Luu[20]还指出了区块链的一致性协议的效率中存在一些安全漏洞, 但Garay[29]和Sompolinsky[30]的研究理论表明, 只要诚实的节点控制了区块链网络中大部分的计算资源, 那么区块链的安全性还是可以得到保障.

2.4 基于区块链的SSE

传统的可搜索加密机制(SE) 存在重大缺陷, 需要依靠诚实的服务器来保证检索过程的安全. 而区块链作为一个新兴技术, 具有不可篡改性和去中心化的性质, 能够和SE 结合解决上述的缺陷.

迄今为止的相关研究中, 区块链技术都是与对称密钥可搜索机制(SSE) 相结合. 在这个基础之上, 相关工作主要被分为两类: 一类是采用智能合约作为执行搜索匹配的实体, 借助智能合约的内在公平性避免传统服务器的恶意行为, 从而保证搜索可靠性[31]; 另一类在原有的SSE 框架下增加区块链系统作为一个额外的实体[32], 服务器仍然保留原有的搜索功能, 通过与区块链的交易来保证服务器和用户之间的利益公平.

SSE 在理论上对于数据的共享有一定的限制, 而区块链的设计就是面向数据共享的, 所以两者结合过程中会有一定冲突. 若把存储与检索都放在区块链上, 智能合约承受不了如此大的计算量, 会变得缓慢和昂贵. 比如在上述提到的Hu 等人[31]在2018 年实现的基于区块链的对称密钥可搜索系统, 在10 万条数据中检索一次平均耗时为24 分钟.

为了避免SSE 理论上限制共享与区块链面向共享的冲突, 本文把区块链技术与公钥可搜索加密(PEKS) 相结合, 并通过设计分层化的模型来避开前人工作中出现的检索速度慢与开销大的问题, 从而实现一个具有实用价值的公平可靠的基于区块链公钥可搜索加密系统.

3 预备知识

3.1 符号描述

符号标记如表1 所示.

表1 符号描述Table 1 Symbol description

3.2 PEKS

PEKS 方案由四个概率多项式时间算法构成, 分别为KeyGen(s)、PEKS(pk,W)、Trapdoor(sk,W)、Test(pk,s,TW). 具体算法构造如下:

• KeyGen(s). 输入安全参数s. 随机选取α ∈Z∗p以及生成元g和构造群G1, 输出公钥pk =(g,h=gα), 私钥sk=α.

• PEKS(pk,W). 输入公钥pk 和关键字W. 随机选取r ∈Z∗p, 计算t=e(H1(W),hr)∈G2, 输出搜索密文PEKS(pk,W)=[gr,H2(t)].

• Trapdoor(sk,W). 输入关键字W和私钥sk. 输出关键字的搜索口令TW=H1(W)α ∈G1.

• Test(pk,s,TW). 输入公钥pk、搜索密文CW和搜索口令TW, 其中CW= PEKS(pk,W) =[gr,H2(t)]. 令CW=[A,B], 判断H2(e(TW,A))=B是否成立, 若成立, 则输出1, 否则输出0.

3.3 智能合约架构

以太坊智能合约[17]架构如图2 所示. 以太坊在每个运作的节点上都运行着一个以太坊虚拟机(EVM), 可以用来执行完整的程序. 这些程序在以太坊中称为智能合约(smart contract). 智能合约可以用来处理数据, 也内置了转账功能, 可以交易加密货币. 智能合约部署后放在以太坊公链上, 部署时会花费费用给矿工, 每次通过智能合约写入或读取计算结果需要提供交易费用, 计算能力由所有以太坊节点提供. 提供计算能力的任何节点都将以Ether 数字货币作为资源支付. 智能合约是在每个以太坊节点上执行并验证的, 所以计算结果是可信任的.

图2 以太坊智能合约架构Figure 2 Structure of Ethereum smart contracts

以太坊开发出了web3.js 和web3.py, 让开发者可以用网页技术来撰写智能合约的操作界面. 这种网页操作界面又被称为分布式应用程序(DAPP). 以太坊提供了便于交易的加密货币—以太币, 可通过智能合约解决交易上的信任问题, 同时也可撰写DAPP 来提供友善的信息汇总与操作界面, 所以以太坊成为了一个非常理想的区块链底层技术. 开发者通过开发的去中心应用DAPP 来和智能合约进行交互, 通过DAPP 浏览器调用智能合约, 从而达到和以太坊交互的目的.

而燃料系统(gas system) 是智能合约特有的交易政策. 执行智能合约需要消耗与执行指令数量相当的以太币, 在智能合约中, 这些拿来消耗的以太币被称为燃料(gas). 当合约部署到以太坊上时, 需要附加一定数量的燃料. 当发送方调用智能合约发起交易时, 智能合约估算此交易需要花费的最大燃料, 只有当发送方的账户余额大于最大燃料时, 此交易才能被包含到区块链中执行.

以太坊智能合约如今也存在着一定的局限性, 以太坊区块链的速度和电脑执行的速度无法相比, 不适合快速交易; 无法满足需要存储较大数据的情境, 因为其上的存储成本昂贵.

在本方案中我们把以太坊智能合约与密文检索技术相结合, 把部分较大文件转移到服务器上存储来避开上述局限性.

4 问题描述

本文旨在设计一个基于区块链的公钥可搜索加密系统, 此系统具有关键字隐私性、公平性和可靠性,可以避免不可信云服务器带来的安全问题, 提高加密数据的安全性.

4.1 系统模型

系统模型如图3 所示, 主要的组成部分有: 数据拥有者, 智能合约, 用户和服务器.

图3 系统模型Figure 3 System model

•数据拥有者(Data Owner, DO). 数据拥有者上传搜索密文与编号至智能合约, 上传数据密文至服务器. 接收自身数据被检索带来的收益.

•智能合约(Smart Contract, SC). 智能合约通过交易存储数据拥有者上传的搜索密文和编号.根据用户的关键词陷门检索相应的密文, 并验证密文的完整性与正确性, 并通过交易将检索结果下发给用户. 管理检索过程中的费用的分配与发放.

•服务器(Server, S). 服务器接收数据拥有者存储的数据密文与编号, 接收以太坊智能合约下发的密文编号, 检索相应的密文, 并将结果上传至智能合约等待验证.

•用户(User, U). 用户设置搜索口令, 并将佣金上传至智能合约中. 接收来自智能合约的验证过的检索结果.

在一次完整的存储与检索流程中, 首先数据拥有者先把搜索密文与搜索密文编号上传至智能合约, 同时将数据密文与编号上传至服务器中. 拥有权限的用户就可以检索到此文件, 用户检索文件时设置搜索口令, 并将佣金上传至智能合约中. 智能合约根据搜索口令在搜索密文中进行检索, 检索到之后使用编号向服务器请求密文, 然后验证服务器返回的密文的完整性, 根据验证结果来分发佣金.

4.2 设计目标

关键字隐私性.服务器在仅提供密文的情况下不能知道任何明文相关的内容. 在数据拥有者未授权的情况下, 其他用户不能查询到此数据拥有者的数据; 数据检索方除了查询结果之外不能得知检索关键词的相关信息. 本方案基于PEKS 密文检索方案保障关键字的隐私性. 用户提供关键字陷门, 数据检索方可通过陷门检索出对应的密文, 此时尽管检索方正确地检索出了相应的结果, 但是对关键词相关信息一无所知.

公平性.公平性是本文在密文检索中引入的重要性质. 本文公平性保障灵感主要来源于现实世界中的交易财政政策. 我们的公平性主要保证以下两点: 数据拥有者只要付费给检索方就可以取得自己正确的检索结果, 检索方只要诚实地检索数据并且返回正确的结果就可以挣得报酬. 当数据需要共享时, 用户只要付费给检索方和数据拥有者, 就可以取得自己正确的检索结果, 数据拥有者如果想要共享自己的数据来获取报酬的话, 只要公开令牌即可. 总的来说, 我们的公平性政策保证了各方能够被激励从而去做诚实并且正确的工作, 如果某方违背了协议, 他将得不到报酬.

可靠性.本文可靠性保障主要来源于区块链的不可篡改机制. 篡改存储在区块链上的数据, 需要篡改此数据位置之后所有区块的哈希和相关记录, 理论上若要篡改数据需要控制51% 的节点, 此操作难度极高, 所以区块链拥有不可篡改性. 密文保存在区块链中使得其不能被篡改, 也就保障了数据是正确的和可靠的.

4.3 安全定义

本小节采用安全游戏的方式, 定义了基于区块链PEKS 系统的安全模型.

(1) 关键字隐私性

关键字隐私性主要考虑抵抗选择关键字攻击的语义安全(semantic security against chosen keyword attack), 即敌手不会从密文中获得关键字的任何信息. 若系统拥有关键字隐私性, 那么敌手A不会从密文中获得关键字的任何信息. 其可以通过挑战者C与敌手A之间的安全游戏进行定义. 在这个安全游戏中,A不是授权用户, 所以A无法获得某个密文的关键字. 在这个安全游戏中, 现允许A进行CKA, 并尝试区分一个可检索密文对应的关键字W0和W1. 敌手A与挑战者C的安全游戏定义如下.

初始化阶段: 挑战者C运行KeyGen(s), 生成公钥pk 和私钥sk, 挑战者C将公钥pk 发送给敌手A.

询问阶段1: 敌手A向C询问一系列关键字Wi ∈{0,1}i的陷门, 挑战者C运行Trapdoor(sk,W)生成关键字陷门, 并将陷门告诉敌手A. 然后敌手A向挑战者C询问一系列与Wi对应的搜索密文, 挑战者C执行PEKS(pk,W) 生成关键字密文, 并将其发送给攻击者A.

挑战阶段: 敌手A随机选取两个不同的关键字W0、W1发送给挑战者C,W0、W1要求是不能在询问阶段1 询问过的关键字. 挑战者随机选取一个b ∈{0,1}生成挑战密文C=PEKS(pk,Wb), 并将改挑战密文发送给敌手A.

询问阶段2: 与询问阶段1 方式类似, 敌手A继续向挑战者C请求关键字陷门, 但是不允许询问关键字W0、W1的陷门信息.

猜测阶段: 敌手输出一个b′∈{0,1}, 如果b=b′, 那么敌手A在安全游戏中获胜, 否则失败. 我们将敌手A赢得上述安全游戏的优势定义为如下形式:

定义1基于区块链的公钥可搜索加密系统具有关键字隐私性, 如果对于任意概率多项式时间(Probabilistic Polynomial Time, PPT) 的敌手A, 其赢得上述安全游戏的优势ϵ是可忽略的, 即AdvCKAA

(2) 公平性

我们采用基于模拟的安全来定义系统的公平性. 系统的公平性分析是通过比较现实世界与理想世界中的交易执行情况来定义的. 在现实世界中, 用户U通过我们系统中的智能合约来获得服务, 而在理想世界中, 用户通过一个理想的受信任的第三方来保证服务的准确性. 无论是现实世界还是理想世界, 都有一个特殊的环境Z, 它的作用是协调各个参与方的输入与输出.

•在理想世界中, 我们设置一个理想的受信任的第三方L.U可以被L所验证, 也就是说L可以验证出不诚实的参与者来保障整个交易的公平性. 我们将理想世界中交易输出定义为IdealU,S(T,f,v(iu)), 其中T是由U发起的交易,f是服务费,v(iu) 是验证函数, 其中iu 是U提供的输入.

•在真实世界中,U可以被智能合约所验证. 交互的公平性被我们系统中的一系列机制所保障. 我们将真实世界中交易的输出定义为RealU,S(T,f,v(iu,is)).U执行sendRawTransaction() 来发起交易, 如果U发起交易失败, 则交易被系统终止, 费用被返回给U. 如果U是一个诚实的用户, 那么Verify() 将输出“True”, 整个交易结束; 否则Verify() 输出“False”, 同时,U的费用被退回.

我们假定不诚实的用户U′的目的是为了从服务方获得免费的服务, 而不是恶意地消耗服务方的计算能力.

定义2基于区块链的公钥可搜索加密系统是公平的, 如果任意现实世界中的不诚实的用户U∗运行了时间t, 在理想世界中都存在一个用户U∗′运行了时间t′, 它们在任意的交易T, 验证函数v(iu) 和服务费f, 在所有PPT 环境Z中都有:

5 基于区块链的公钥可搜索加密系统设计

为了让智能合约与PEKS 密文检索方案更好地交互, 本方案采用分层的形式构造了一个基于区块链的公钥可搜索加密系统. 在本方案的分层构造中, 不同层具有不同的功能与角色, 每层之间通过约定好的接口交互以保障整个系统稳定地运行, 从而实现一个安全可靠的设计方案.

5.1 系统概述

系统整体设计如图4 所描述, 主要分为四层: 客户端、检索层、智能合约层和服务器.

图4 基于区块链的公钥可搜索加密系统设计图Figure 4 Blockchain-based public key encryption with keyword search system scheme

•客户端(Client, C): 当数据拥有者存储明文时, 客户端接收数据拥有者的明文并传入检索层. 当用户想要检索明文时, 客户端接收用户的关键字与佣金并传入检索层. 接收来自检索层传入的明文, 将结果下发给用户. 总的来说客户端的作用是提供一个与用户交互的平台.

•检索层(Retrieval, R): 接收客户端传入的明文并执行加密, 将数据密文与编号传入服务器, 将搜索密文与编号传入智能合约层, 将编号集合存为索引存储在本层. 接收客户端传入的佣金与关键字, 生成搜索口令并把佣金传入智能合约层. 接收来自智能合约层的搜索密文, 并用搜索口令检索,将检索结果传入智能合约层. 接收来自智能合约层的数据密文, 解密并将明文传入客户端. 总的来说检索层执行与密文检索相关的算法.

•智能合约层(Smart content, SC): 存储来自检索层传入的搜索密文与编号. 接收来自检索层的佣金, 并作为押金暂时存放在智能合约, 再将搜索密文传入检索层. 接收来自检索层的检索结果,并且将对应的编号传入服务器. 接收来自服务器的数据密文并且验证此数据密文是否正确, 若正确则将佣金付给数据拥有者, 并将数据密文传给检索层. 总的来说智能合约层执行佣金的管理与发方.

•服务器层(Sever, S): 接收来自检索层传入的数据密文和编号并存储. 接收来自智能合约的编号,并返回相应的数据密文传入给智能合约层. 总的来说, 服务器负责存储密文并诚实地返回密文.

5.2 方案构造

基于区块链的公钥可搜索加密方案包含以下7 个阶段, 该方案基于PEKS[2]的构造来实现搜索口令的生成和密文检索, 结合智能合约技术来处理各个账户之间的交易以保障方案的安全性和可靠性.

(1) 初始化阶段

KeyGen(s)→(pk,sk), 系统初始化. 选择一个安全参数s作为输入, 随机选取α ∈Z∗p以及群G1和生成元g, 输出公钥pk 和私钥sk 如下

智能合约初始化, 数据拥有者注册得到账户$Bowner并设置检索单价$offer, 用户注册得到账户$Buser, 用户需向$Buser中存款, 智能合约设置押金账户$deposit. 智能合约交易相关的账户如表2 所示.

表2 交易涉及的各个账户及其含义Table 2 Accounts involved in the transaction

(2) 密文生成阶段

Enc(m,W,pk)→(Cm,PEKS(pk,W)). 该算法由检索层进行计算, 输入为明文m、关键字W和公钥pk, 输出为数据密文Cm和搜索密文PEKS(pk,W). 计算密文, 明文m通过RSA 非对称加密算法得到数据密文Cm. 计算搜索密文, 随机选取r ∈Z∗p, 首先计算t=e(H1(W),hr)∈G2, 得到搜索密文, 记为

数据拥有者将Cm与PEKS(pk,W) 进行编号, 得到对应的编号N. 将数据密文Cm与编号N进行哈希得到Hm. 将N添加至检索层的检索索引I中, 将数据密文Cm与编号N上传至服务器进行存储, 将PEKS(pk,W)、N与Hm上传至智能合约等待查询.

(3) 搜索口令生成阶段

Trapdoor(sk,W′)→TW′. 该算法由检索层进行计算, 把私钥sk 与用户想要检索的关键字W′作为输入, 输出搜索口令如下

用户将搜索口令上传至检索层,并用自身账户$Buser向智能合约的账户$deposit 存款$Buser→$deposit.

(4) 交易发布阶段

sendRawTransaction($Buser,I)→txHash. 该算法由智能合约进行计算, $Buser为用户的账户,I为检索索引, 包含了所有搜索密文PEKS(pk,W) 对应的编号, 作为此交易的参数传入.

首先检查$Buser是否合法. 然后智能合约估算此次交易需要的费用$cost←$offer +Glimit×$gasprice, 并检查押金账户$deposit 中用户预存的押金是否满足依次此次交易所需费用$cost, 若满足则继续发布交易, 过程如下.

首先使用$Buser对应的公钥与secp256k1 椭圆曲线对传入的参数I签名. 然后使用RLP(Recursive Length Prefix), 递归长度前缀编码对签名数据进行编码. 将此交易的指针指向其前一个区块, 验证该交易并将其广播到P2P 网络中. 最后的产生txHash 为交易ID. 若交易发布成功, 则将I中对应的搜索密文PEKS(pk,W) 集合上传至检索层.

若用户预存的押金$deposit 不满足此次交易所需费用$cost, 则终止交易, 并将$deposit 中预存的押金返回给用户的账户$Buser.

(5) 检索阶段

Search(TW′,I)→N. 该算法由检索层进行计算,I为检索索引,TW′为搜索口令. 首先对于I, 向智能合约请求对应的搜索密文PEKS(pk,W) 集合.

对于每个PEKS(pk,W), 执行Test(pk,CW,TW′), 其中CW= [A,B] = PEKS(pk,W). 判断H2(e(TW′,A))=B是否成立, 若成立输出1, 否则输出0.

若Test(pk,CW,TW′) 输出为1, 则表明检索成功, 将对应的N下发给智能合约.

若不存在能使Test(pk,CW,TW′) 为1 的PEKS(pk,W), 则表明数据拥有者存储的密文未包含用户想要检索的文档. 此时将N置为−1, 并下发给智能合约.

(6) 验证阶段

Verify(Cm,N)→0|1. 该算法由智能合约进行计算. 当智能合约接收到来自检索层的编号N时, 智能合约首先判断N是否为−1, 若为−1, 则直接输出0. 若N不为−1, 智能合约将N告诉服务器, 服务器中存储了N与密文Cm的对应关系, 此时服务器可以直接返回对应的Cm.

此时智能合约需要验证服务器是否返回了错误的密文或者数据是否被恶意破坏和篡改. 首先智能合约通过N得到存在本层的对应的Hm, 然后将Cm与N进行哈希运算得到Hm′, 若Hm′=Hm, 表明验证成功, 输出1, 否则输出0.

(7) 账户更新阶段

该流程由智能合约执行. 若Verify(Cm,N) 为1, 则计算$cost←$offer+G×$gasprice, 将$cost转入至数据拥有者的账户$Bowner中, 此时$deposit←$deposit−$cost, 将$deposit 退回到用户的账户$Buser中. 并将数据密文Cm传入检索层, 由检索层解密后将明文m传入客户端.

若Verify(Cm,N) 为0, 则直接将$deposit 退回到用户的账户$Buser中.

5.3 安全性分析

定理1如果底层的基于双线性对的加密机制在PPT 时间内不能被攻破, 那么基于区块链的公钥可搜索加密系统在随机预言机模型下具有关键字隐私性.

证明:在CKA 中, 现假设存在一个PPT 的敌手A, 它能以优势ϵ成功地攻破系统. 再构造一个模拟器B, 将系统的公钥pk 告诉B.

初始化阶段:B运行KeyGen() 获得公钥pk 与私钥sk, 将公钥pk 发送给敌手A.

ˆH-询问阶段:B得到一个初始为空的哈希列表L(wi,hi). 每当收到一个对应于wi的 ˆH-询问并通过访问签名预言机获得一个δ(wi), 如果δ(wi) 已经在列表L中,B就返回对应的hi来作为敌手A的预处理关键字, 否则B将hi设置成如下形式.

然后B将(δ(wi),hi) 添加到L中, 并将ai返回给A.

询问阶段1:A发起一系列的询问. 如果A询问的是一个关键字wi对应的关键字密文或者陷门,B通过访问签名预言机获得一个预处理的关键字hi, 然后B通过使用密钥对(pk,sk) 得到关键字密文Cwi或者陷门Twi, 并将其发送给A.

挑战阶段: 一旦接收到来自A的挑战关键字w0和w1,B随机选取一个b ∈{0,1}, 并生成wb的关键字密文Cwb, 并将其返回给A.

询问阶段2:A继续向B询问关键字的密文或者陷门,B的响应行为类似于询问阶段1. 限制条件是A不能询问有关w0或w1的信息.

猜测阶段:A输出一个猜测值b′∈{0,1}.

定理2如果区块链不能在PPT 时间内攻破, 那么基于区块链的公钥可搜索加密系统是具有公平性的.

证明:我们考虑了在系统中存在不诚实用户的情形. 对于在现实世界中的每一个不诚实的用户 ˆU,在理想世界中都存在着一个不诚实的用户U, 它们两个的输出在计算上是不可区分的. 我们假定ˆU被给定了一个合法的区块链账户, 但是它只想要通过不诚实的手段获得免费的服务.U在理想世界中执行如下所示的算法1.

算法1 理想世界中交易的详细流程理想世界中, 服务提供方S 与用户U 和信任的第三方L 之间的交互流程.sendRawTransaction()• U 发起一个交易T, 交易金额是d, 由可信任第三方L 执行v(iu).• L 检查T, 如果其是一个有效的交易, 受信任的第三方L 将T 执行, 如果T 是个无效的交易, 那么L 将会终止T,并且输出False.Search()• 系统执行来自L 的交易T.• 服务执行完毕, 创建交易T′ 并将其回执给L.Verify()• L 使用验证函数v(iu), 如果通过, L 接受交易T′, 否则L 拒绝交易T′.• 如果L 接受了交易T′, U 则从L 接收交易T′, U 获得相应的服务, 并且输出“True”.• 如果L 拒接了交易T′, U 将获得其被退回的费用, L 终止整个交易, 并输出“False”.

我们通过构造两种混合的游戏可以得出模拟器和现实世界的输出在计算上非常接近.

游戏H0由理想世界模拟器执行.

游戏H1为混合游戏, 其中没有受信任的第三方, 而是让U与区块链系统进行交互.

我们将证明H0和H1在计算上是不可区分的. 因为工作证明算法在区块链系统中稳定运行, 区块链系统在交易中被视为是诚实的, 并且在区块链系统中运行的所有交易都不能被篡改, 所以H0和H1是计算上不可区分的. 因此现实世界系统的输出和理想世界中系统的输出是计算上不可区分的, 并且不诚实的用户ˆU不可能成功地伪造一个有效的交易. 因此, 系统的公平性得以保障.

定理3如果以太坊环境的安全性得到保障, 那么我们的方案是可靠的.

证明:假设以太坊环境是安全的, 那么交易发布之后, 交易相关信息会被记录在区块链中, 通过共识机制所有区块链节点都能与相同的区块链进行交互, 而恶意参与者无法控制以太坊区块链上超过51% 的节点, 所以交易一旦发布就不能被篡改. 如果智能合约能够在以太坊环境中得到正确执行, 那么检索结果将会以区块的形式存储在区块链中. 区块链上的区块是公开的且是不可篡改的, 所有以太坊节点都可以验证该数据. 以太坊各个节点的一致性保证了在检索过程中每个步骤执行的正确性和可靠性. 可靠性的另一方面由公平性支撑, 通过智能合约我们能保障交易各方能够得到应得的激励, 交易各方都承认检索结果的公平性, 那么本方案的可靠性也得到了保障. 由于可靠性主要由以太坊环境和智能合约来实现, 其证明无法采用定理1 和定理2 的规约范式. 受文献[31] 的启发, 本文也采用了类似于文献[31] 的方式来分析基于区块链PEKS 系统的可靠性.

6 原型系统实现与性能评估

根据5.1 节系统设计的4 层架构, 我们使用了5000 多行代码来实现系统的原型. 本方案原型基于以太坊平台搭建, 使用的操作系统为Ubuntu 18.04. 客户端使用了Django 框架与html5、Javascript 技术来保证其与后端的交互, 检索层采用Python 3.0 编写以实现加解密与搜索口令的生成, 主要使用pypbc库、hashlib 库和rsa 库来实现PEKS 方案, 智能合约使用了Solidity 语言编写, 为了实验结果的准确并减少其它因素的干扰, 智能合约部署在以太坊私链中.

6.1 原型系统实现细节

对于PEKS 算法实现, 本方案采取一个固定的参数, 使双线性映射固定下来, 便于后续操作能够在同一参数的基础上运行. 表3 为使用到的密码学参数说明. 在密钥生成函数KeyGen() 中, 输入安全参数qbits 和rbits. 本方案选取的值为qbits = 512, rbits = 160, 这样就将群G1和G2以及返回的params固定下来. 在实例化双线性对对象时, 直接利用pypbc 库中的Pairing() 函数, 将params 参数输入, 生成双线性对对象pairing. 同时, 对于群G1生成元的选取, 也直接调用pypbc 库中的Element.random() 函数, 输入之前生成的双线性对对象pairing 以及群G2, 随机生成. 本方案的哈希函数H1和H2直接引用hashlib 的库hashlib.sha256 生成.

表3 PEKS 使用到的密码学参数说明Table 3 Cryptography parameter description for PEKS

对于RSA 的实现, 本方案使用到了Python 中的rsa 库. 对明文进行加密, 对密文进行解密. 对于密钥对的生成, 调用函数rsa.newkeys(512) 随机生成, 其中参数选择512, 表示用来加密的数据长度为512 bits. 生成之后将文件以pem 格式保存下来. 对明文用RSA 加密函数之前先将明文进行utf-8 编码. 对应的, 解密之后用utf-8 解码.

对于智能合约的实现, 本方案的主要环境为以太坊. 本方案中的智能合约主要用来验证检索结果与费用分发. 对于搜索密文与编号的存储, 智能合约主要采用了映射(mapping) 的数据结构, 把编号存为映射的键(key), 搜索密文存为映射的值(value). 同样地, 智能合约通过mapping 将数据密文的哈希进行存储, mapping 的key 位编号, value 为对应的数据密文哈希值. 当智能合约收到来自服务器返回的数据密文时, 智能合约首先在自己存储的mapping 中找到对应的哈希值, 再将数据密文计算得出一个新的哈希,对比两个哈希即可验证服务器返回的结果是否正确. 通过调用各个参与方的转账函数即可实现费用的发放与收取.

6.2 性能测试与分析

本节分别在私链和公链环境中对系统的性能作出测试, 将从实验部署、仿真过程和数据结果三个方面分别进行介绍.

6.2.1 实验部署

本小节主要介绍私链以及公链上智能合约的部署.

(1) 私链上的部署

首先, 在以太坊环境中搭建了一条私链作为智能合约的运行环境, 此条私链的chainId 为528, 创世区块的timestamp 为0x5ddf8f3e, difficulty 为0x002, 私链的端口为3333, rpc 端口为4444. 接着我们在此私链中部署了我们的智能合约, 部署后得到智能合约的地址为0xc4ca68caa8ecc4a46b475161e3161eb228b 0e01a. 关键参数如表4 所示.

表4 智能合约部署关键参数表Table 4 Smart contract deployment key parameter table

(2) 公链上的部署

实验选择了以太坊官方提供的公有测试链Ropsten 来进行智能合约的部署. 我们使用infura 作为代理节点, 使用remix 加metamask 进行了部署. 部署好后, 用户地址和合约地址如下所示.

• 0x87E08e9E27D6c1645b773A37Ac4BD09773B3dd94

• 0x03fc28689d09d461d3b60dd75463ad457d5a67b5

6.2.2 仿真过程

实验在具有4 个Intel i7-7500 内核的PC 上执行, 操作系统为Ubuntu 18.04, 内存为5.8 G. 在私链上的实验过程中, 启动服务器, 保持合约启动状态并持续地进行挖矿; 在公链上只需要启动服务器, 保持infura 账号登录状态. 然后分别使用Apache Bench 进行压力测试. 主要测试点为本方案中存储明文与密文检索两个关键功能模块的功能完整性、可用性及性能. 在对每个功能模块的测试实验中, 将请求总数固定为600, 并固定传输数据长度, 改变系统面对的并发请求数量, 对用户平均等待时间、服务器平均请求处理时间等指标进行统计与分析, 从而验证本文方案的可行性. 实验中涉及的参数如表5 所示.

表5 实验相关参数Table 5 Experiment related parameters

公私链上实验参数设置完全相同, 对应情况下的每次实验都分为两大组进行, 每组根据VU 的不同又分为15 组参数, 每组参数重复测试3 次取平均值, 总共进行了90 次测试. 在对消息发送模块进行测试时,保持请求总数为600, 消息长度为4640 bytes, 改变VU 数量使其在10 到600 的范围内递增, 记录每组数据下用户平均等待时间、服务器平均请求处理时间、TPS 以及DTR 的值. 同样地, 在对密文检索模块进行测试时, 保持请求总数为600, 消息长度为3247 bytes, 改变改变VU 数量使其在10 到600 的范围内递增, 并记录上述性能参数数值.

6.2.3 实验结果分析

(1) 私链实验结果分析

图5 和图6 显示了在其他条件不变的情况下, VU 数量从10 增加到600 时, 消息发送模块用户平均请求等待时间、服务器平均请求处理时间以及RPS 和DTR 的变化情况.

经测试, 整个实验过程模拟用户失败的请求个数都是0, 也就是说, 正常情况下, 服务器对用户请求的响应能力维持着较高的水平. 各个功能也能完整而稳定地运行.

图5、图6 可以直观地展示出用户等待时间与系统响应时间同时与DTR 有关. DTR 越高, TPS 越大, 用户的请求等待时间越短. 另一方面, 当VU 在10 到600 范围内变化时, 信息发送模块用户请求等待时间和服务器请求处理时间也随VU 线性地增加, 相应的TPS 逐渐下降. 可以推测, 在并发数600 之内, 系统可以正常且完整地完成信息发送, 但是并发数增大时, 系统的响应时间会有一定延长.

图5 私链信息发送模块用户等待和服务器处理时间Figure 5 Variation of user’s waiting time and server’s processing time with VU in information sending module on private chain

图6 私链信息发送模块TPS 和DTRFigure 6 Variation of TPS and DTR with VU in information sending module on private chain

图7 和图8 是当其他条件不变、VU 在10 到600 范围内变化的情况下, 密文检索模块各性能参数的变化情况.

图7 私链密文检索模块用户等待和服务器处理时间Figure 7 Variation of user’s waiting time and server’s processing time with VU in ciphertext retrieval module on private chain

图8 私链密文检索模块TPS 和DTRFigure 8 Variation of TPS and DTR with VU in ciphertext retrieval module on private chain

密文检索模块各参数随VU 的变化与信息发送模块的变化趋势大同小异, 从图7 和图8 中可以看到,用户的请求等待时间依然与DTR 呈负相关, 而TPS 与DTR 呈正相关. 当其他条件不变、VU 在10 到600 之内增加时, 用户平均等待时间和服务器请求处理时间都随之延长, 而DTR 随之下降, TPS 也降低.需要说明的是, 服务器响应时间与用户等待时间在很大程度上依赖于网络上的数据传输速率, 因此在不同时刻、不同网段中使用同一套参数重复验证时, 尽管数据由于网速的变化而大不相同, 但是各参数之间的依赖关系和变化趋势依然不会改变.

(3) 公链实验结果分析

在公链上, 控制其他条件不变并让VU 从10 到600 变化, 分别对发送模块和检索模块进行测试. 可以得到用户平均请求等待时间、服务器平均请求处理时间以及RPS 和DTR 的变化情况. 其中, 图9 和图10 表示的是发送模块的数据折线图, 图11 和图12 记录的则是检索模块的数据折线图.

图9 公链信息发送模块用户等待和服务器处理时间Figure 9 Variation of user’s waiting time and server’s processing time with VU in information sending module on public chain

图10 公链信息发送模块TPS 和DTRFigure 10 Variation of TPS and DTR with VU in information sending module on public chain

图11 公链密文检索模块用户等待和服务器处理时间Figure 11 Variation of user’s waiting time and server’s processing time with VU in ciphertext retrieval module on public chain

图12 公链密文检索模块TPS 和DTRFigure 12 Variation of TPS and DTR with VU in ciphertext retrieval module on public chain

从图中可以看到, 各指标随并发数的变化趋势并没有受公私链改变的影响, 用户等待时间与服务器响应时间也维持在相同的量级. 由此可以看出, 本文方案在公链上推行有一定的可行性.

在网络状况良好的情况下, 系统能够稳定地完成数据的传输、加密和检索, 但是随着并发数增大, 系统依然面临性能上的挑战, 不过这依然无法掩盖基于区块链的密文检索方案在大数据时代诸多领域的广阔应用前景和无限的可能性.

6.3 实际应用场景

通过以上的测试可以得出, 系统在网络状况良好的情况下能够稳定地完成数据的传输、加密和检索.并且系统使用区块链来管理第三方服务器, 具有公平性和可靠性, 同时本身的PEKS 方案具有关键字隐私性, 在网络安全形势愈发严峻的今天是非常值得推广的.

但是, 由于区块链是所有节点可验证并且需要矿工挖矿来上传数据的, 所以系统的存储成本似乎看起来比较昂贵, 但是该系统仍然可以应用到许多的真实场景中. 例如, 个人的医疗档案是非常重要的, 现实生活中医生只有获取到了病人的真实健康状况才能够做出正确的判断; 个人学历档案或者是犯罪档案也是不可被随意篡改的, 并且需要很高的隐私性. 在这些场景中, 由于对数据的安全可靠要求异常苛刻, 所以为了检索高可靠的密文, 高花费是值得的.

如图13 所展示的, 基于区块链的公钥可搜索加密系统在个人学历档案场景中的应用.

图13 系统在个人学历档案场景中的应用Figure 13 Application in personal education record system

系统中存储公民的个人学历, 个人学历信息只有具有权限的校方才能够修改, 并且修改频率有一定的限制, 例如高中学历校方每三年才能修改一次, 大学学历校方每四年修改一次. 而在这种场景中每个人无法修改自己的学历, 他们只能查看自己的学历, 或者截图以向外证明自己的学历. 所以在个人学历档案场景中, 政府为每个公民凭借身份证号创建一个唯一的档案账户, 档案账户的私钥分发给权威的校方机构,校方凭借私钥可以修改公民的学历档案, 由于区块链的不可篡改性, 除了有私钥的校方可以修改档案, 档案不会被任何其他方篡改; 档案账户的公钥分发给公民本人, 公民使用此公钥可以查看自己的学历档案,但不能作任何的修改.

7 结束语

为了解决目前PEKS 方案针对恶意服务器的搜索可靠性问题, 本文在PEKS 方案的基础上, 结合区块链技术, 提出了一个基于区块链的公钥加密可搜索系统. 具体而言, 采用分层的思想, 利用智能合约构造了一个四层级化的基于区块链公钥可搜索加密方案, 并对其进行了安全性分析, 证明了所提出的方案可以有效抵抗恶意服务器带来的不良影响, 从而保障系统的关键字隐私性、公平性和可靠性. 基于上述方案,本文实现了基于区块链公钥加密可搜索的原型系统, 并对原型系统进行了性能测试与分析, 证明了本文构造的可行性与实用性.