一种高效安全的密文电子病历多关键字检索方案

邓 兰 徐 进

(华中科技大学同济医学院附属同济医院 武汉 430030)

1 引言

随着医疗信息化建设和医药卫生体制改革的推进，电子病历得到广泛应用。云计算技术的日益成熟和医疗数据互联互通需求增强，促使电子病历存储在云服务器成为医疗信息化未来发展趋势。云存储应用既方便多方机构存储和交换数据，又能大幅节省医院构建和维护独立数据库的开支。电子病历作为医疗卫生信息的主要载体包含大量有价值信息，如患者身份信息、联络方式、治疗信息等，通过网络存储和传输时存在隐私泄露、非法访问等隐患[1]，一旦电子病历信息被泄露可能会给患者和医院带来较大损失[2]，影响医患关系。目前对电子病历安全性和隐私性的保护措施主要包括身份认证[3]、操作日志、数据脱敏[4]、数据加密[5-6]等。其中数据加密是保护电子病历安全性的重要手段，一经加密即使黑客非法窃取也难以解密获取信息。然而数据保密性与可用性之间难以平衡[7]是电子病历加密存储难以推广的重要原因，主要表现在电子病历加密后难以对其进行检索。电子病历数据一经加密，检索时需要对整个数据库解密，计算和通信成本过高。本文提出一种对密文电子病历进行关键字检索的方案，利用布隆过滤器和k最邻近(k-Nearest Neighbor,kNN)加密等工具，将可搜索加密中的正向和反向索引相结合，构造一个两级索引，使用户能够对密文电子病历进行多关键字检索且检索效率较高，从而平衡电子病历的保密性与可用性，使电子病历密文存储成为可能。

2 基础知识

2.1 可搜索加密

2.1.1 概述 2000年Song D X、Wagner D和 Perrig A提出可搜索加密问题[8]，2004年Dan B、Crescenzo G D和Ostrovsky R 等[9]提出可关键字检索的公钥加密(Public-Key Encryption with Keyword Search，PEKS)概念并提出第1个PEKS方案。可搜索加密最早应用于加密电子邮件的关键字检索，随着云计算的兴起，其在云存储领域得到广泛研究[10-12]。可搜索加密使用户能够在不全部下载并解密数据且不让云服务器获取数据和关键字明文的前提下对数据进行关键字检索。

2.1.2 基于索引的方案 较常用的可搜索加密方案[13]，即通过为数据额外生成1个安全索引，索引中记录关键字与数据的对应关系，从而实现关键字检索功能。索引分为正向和反向索引。正向索引是由数据条目指向关键字，优点是便于更新，缺点是在检索某个关键字时需要扫描整个索引，检索效率较低。反向索引则为每个关键字存储1个数据id列表，检索时可以直接获取某个关键字的检索结果，效率较高，但索引更新较麻烦且不便于支持多关键字检索。

2.1.3 多关键字检索 即搜索同时包含多个关键字的数据，考虑到数据量庞大，支持多关键字检索是提高检索效率、准确性和使用友好度的必要功能。

2.2 布隆过滤器

2.2.1 概述 布隆过滤器由Bloom B H[14]于1970年提出并由Eu-jin Goh[15]首先应用于可搜索加密中。布隆过滤器使用1个0、1数组代表集合S，S中的每个元素都通过k个哈希函数映射数组中的k个位置，这些位置被设为1，其他位置则为0。当检测1个元素是否属于S时只需计算出该元素对应的k个位置并查看这些位置是否全为1即可，见图1。

图1 布隆过滤器原理

2.2.2 原理 集合S中包含x、y、z3个元素，每个元素通过3个哈希函数对应3个位置，这些位置全部被置为1，可得出代表集合S的布隆过滤器。为检验元素w是否存在于集合S中时，通过计算w的3个哈希值，也得到1个布隆过滤器。两个布隆过滤器的内积为2，小于k=3，可知w并不属于集合S。布隆过滤器具有查询空间和时间效率较高的优点，因此可将其应用于密文电子病历检索，为每条电子病历生成1个布隆过滤器，在实现电子病历密文存储的同时保留关键字检索功能。

2.3 kNN加密

3 方案

3.1 系统模型

本系统成员包括电子病历管理员、使用者以及云服务器。管理员将电子病历加密并生成安全索引存储到云服务器中。使用者检索时只需发送关键字给管理员，由管理员使用密钥生成该关键字对应的搜索凭证并回复给使用者，其中管理员和使用者之间的身份认证不在讨论范围。云服务器收到搜索凭证后将其与安全索引做一定计算即可得出搜索结果并返回给使用者，见图2。在本方案中电子病历加密和索引生成是分开的，电子病历使用常规的对称加密算法，如AES、SM1、SM4、SM7、祖冲之密码等。

图2 系统模型

3.2 方案算法

3.2.1 初始化 管理员生成方案所需密钥包括伪随机函数F()的密钥K1、K2，以及kNN密钥KkNN=(K,M1,M2)。对于每条电子病历提取出若干关键字。对于每个关键字w，使用伪随机函数F()和密钥K1与其进行计算，得到tagw。使用F()和K2生成Kw，用Kw将w对应的每个病历id加密成E(id)，与tagw构成1个反向索引。 对于每条电子病历，用其包含的所有关键字生成1个布隆过滤器。对每个布隆过滤器使用kNN加密算法和密钥KkNN将其加密，所有加密的布隆过滤器即构成正向索引。将索引1和2连同加密的电子病历存储到云服务器中，见图3。

图3 初始化流程

3.2.2 生成检索凭证(图4)

图4 检索流程

从需要搜索的多个关键字中挑选出1个，如x，使用伪随机函数F()和密钥K1对其进行处理得到tagx。使用F()和K2，生成关键字x的id加密密钥Kx。使用哈希函数将需检索的所有关键字映射到1个布隆过滤器中。使用kNN加密算法和密钥Kknn对该布隆过滤器加密。将生成的搜索凭证即tagx、Kx和加密的布隆过滤器发送给云服务器。

3.2.3 密文检索 云服务器先根据tagx，在索引1中找到关键字x对应的所有病历id，使用Kx将其解密。对于每个病历id，从索引2中获取其对应的加密布隆过滤器，将搜索凭证中的加密布隆过滤器与每个id对应的加密布隆过滤器进行计算，得到的内积即是要搜索的关键字与每条电子病历的相似度。将内积值大于某个阈值的密文电子病历返回给使用者。

4 实践与分析

4.1 概述

在真实病历数据基础上用实验测试方案，方案可行性、安全性得到验证。实验证明该方案能够实现对密文电子病历的多关键字检索功能，且检索准确性和检索效率较高。

4.2 安全性

由于信息均被加密存储，攻击者无法从索引中获取信息。此外进行检索时由于kNN加密中使用1个随机数，每次生成搜索凭证都不相同，攻击者无法判断两次搜索的关键字是否完全相同。通过模拟攻击发现无法获取病历明文、关键字明文、未被检索的病历id、两次检索的关键字是否相同等关键信息，安全性得到保障。

4.3 时间和空间效率

表1 方案时间、空间成本

4.3.2 时间成本 耗时最长的步骤是索引生成，耗时与病历数量成正比。由于索引只需生成1次且索引2的生成可分散到每份电子病历提交时进行，因此是可接受的，更高性能的计算机可缩短生成时间。生成检索凭证耗时恒定，基本可以忽略。关键字检索耗时与被检索第1个关键字对应的病历数相关，与病历总数无关，第1个关键字对应的病历数越少检索越快。根据方案时间、空间成本统计，检索凭证的生成和检索操作耗时较短，因此检索效率得以保障。

4.3.3 通信成本 进行检索时使用者和云服务器之间只需1轮通信且搜索凭证大小恒定，通信成本较低。

4.3.4 存储成本 索引1的大小与关键字总数成正比，索引2的大小与病历总数成正比，且由于加密后的布隆过滤器由大量浮点数组成，因此需要的存储空间略多，但在云环境下这些存储量是可接受的。此外还可通过适当减小布隆过滤器的长度来缩减索引大小。

5 结语

针对云环境下密文电子病历无法进行关键字检索的问题，基于布隆过滤器和kNN加密算法，结合正向和反向索引，提出一种安全高效且支持多关键字搜索的电子病历加密方案，使电子病历加密并存储在云服务器、实现数据共享成为可能。此外检索方案和电子病历加密方案相互独立，电子病历可使用任何现有方案进行加解密，具有可部署性。目前该方案尚存在存储成本有待降低等不足，需在未来研究中继续完善。