英语原文共 16 页，剩余内容已隐藏，支付完成后下载完整资料

大数据量数据库下的

动态可搜索加密：数据结构及其实现

摘要——本文设计并实现了动态对称的可搜索加密方案，能够对服务器上具有数百亿对 记录-关键字对的加密数据库进行私密地且高效地搜索。我们的基本理论结构支持单关键字搜索，并提供渐近最优的服务器索引，能支持完全并行搜索并最小化泄漏。我们的实施工作中得出了之前对粗粒度理论性能分析忽视的几个重要影响因素，包括底层的空间利用率，I/O并行性和有效吞吐量。因此，我们提出一些基于模型原型设计的特点，能达到理论结构最优化的优化策略，旨在克服这些因素。我们所有的策略和优化已经被证实为安全且对不信任服务器的信息泄露量是可精确计算的。评估我们的原型的性能使用了两个非常大的数据集：一个有1亿个记录，且每个记录含有数百个关键字的综合普查数据库和一个数百万的网页集（维基百科作为其中一个子集）。此外，基于上述的大数据量数据库，本文实现了可作为支持近期SSE发展的基础动态SSE方案，包括复杂的搜索查询（如：布尔查询）和更多的操作选项查询（如，查询组）。

I. 简介

背景——搜索的对称加密（SSE）允许一个数据存储在不受信任的服务器，并且在保持隐私的前提下允许通过一个给定的关键字来搜索数据记录（或文件）。最近的许多作品[ 3 ]–[ 5 ]、[ 7 ]、[ 9 ]、[ 14 ]、[ 15 ]、[ 17 ]、[ 19 ]、[ 21 ]研究所提供了许多解决方案，在安全性、效率，能够安全地更新经过加密数据并上传的能力间进行取舍。这些结构旨在实用效率，而通用加密工具（如同态加密或多方计算）虽是高度安全的，但不可能在实践中效率高。

数据量的大小促使存储外包，因此可用的SSE方案必须进行良好的规划。现有的SSE方案使用对称密码运算和标准数据结构，得出的实际效率已经非常具有潜力，但障碍依然存在。虽然大多数模型结构都有理论上最佳的搜索时间，因其仅缩放与匹配查询文档的数量（节省时间），但现对大型数据集的性能是不太清楚。降低上述理论的SSE方案的实际效率因素有很多，如I/O延迟，存储利用率，和现实世界中的数据集分布的方差。实践中完全缺乏局部性和并行性是实际效率低下的一个关键因素：执行一个搜索，大多数先前的SSE方案在伪随机位置处按存储顺序读取每个结果，已知的唯一的能避免顺序读取且保持隐私性的方案是需要服务器提供和维护一个相当大规模的索引。

贡献——本文给出了第一个可以加密和搜索含有上百亿记录-关键字对的数据集的SSE方案实现。要实现本文的设计，我们从一个新的，简单的，理论的SSE框架开始，通过使用一个泛型字典结构已经实现了对先前的SSE方案的渐进改进，能做到最少的泄漏，最优服务器的大小，实现搜索计算和并行搜索。这个设计的开始可以看作是[ 3 ]提及系统中特别技术的概括和简化。我们展示了如何动态地实现整个系统，这意味着加密后的数据可以改变。我们的系统可以很容易地支持数据的添加，以及通过撤销列表删除。

该设计使用的泛型字典本身没有安全特性，满足安全性证明条件下它仅允许几种扩展和只有微小变化的修改。特别地，我们在实施过程中表明，磁盘I / O利用率仍然是一个瓶颈，依然是设计的主要妨碍因素；因此，我们对设计的模型进行拓展，以改善局部性能和吞吐量。这些扩展在隐私保护方面存在略有不同的泄漏，我们都会进行形式化的安全性证明的分析。下面我们将更详细地描述结果背后的技术，从我们以后扩展的新理论计划开始，然后将我们的结果 与以前的工作进行比较。

基本框架——我们整个设计非常简单（图2），将记录-关键字对和一个伪随机标签相关联，然后在泛型字典数据结构中对每一个匹配都保存一个带上述标签的加密记录标识符。通过得到的标签，以便客户端输入关键字查询，可以计算特定关键字的短密钥，允许服务器通过重新计算标签来进行搜索，然后从字典中检索加密的标识符，最后解密匹配加密记录标识符。由加密索引泄露给服务器的唯一信息（除了匹配查询的索引之外）是字典中的数目，这个数目即是数据中的 记录-关键字 的数目。该方案易于正确地实现（与并行搜索）因为我们对设计的字典没有安全要求，从而允许实例化应用需求。

外部存储扩展——计算一个r匹配关键字搜索结果，我们的基本方案要求r次对字典的伪标签检索。假设字典检索的消耗是，这是渐近最优的。然而在实际情况中，与这个最优结论相差甚远，因为词典一般在外部存储器进行存储（如HDD设备）。因为每个随机查找都会产生磁盘读取。相比于一个明文系统 （a plaintext system） ，明文系统可以将所有的匹配存储在一个连续的内存区域中。鉴于这一现实，我们扩展了我们的设计，更谨慎地使用外部存储，同时保持隐私。首先我们展示如何安全地“包装”相关结果通过填充策略来减少字典检索数。我们发现，这个策略对我们的目标数据集来讲过于缓慢，特别是，我们注意到，真实数据集在关键字的匹配数中表现出极大的可变性：有很多关键词匹配的文件很少，然后一些关键字匹配整个数据库的一个重要部分。因此，我们填充策略变得不满意因为关键词(许多)匹配只有少数结果创建很多填充,并且返回大量结果的搜索仍会触发大量的词典检索。

为了解决这个问题我们提出进一步的修改,当处理大量的结果时，从数组中读取取代字典读取。这些修改会引起概要文件泄露方面产生些许不同，但是直觉上可以接受的(甚至更好)，我们将会在下面讨论。

扩展的更新——我们注意到,我们的设计很容易进行扩展,允许添加到数据后上传。我们只需要安排客户端为添加的新数据计算标签,然后向服务器发送标签并请求添加到字典。这要求客户端状态或通信与已添加或删除的关键字的总数成比例。我们维护一个(伪随机)撤销列表在服务器用于支持删除操作,满足过滤的结果应该被删除，我们必需定期进行重新加密用于确切地回收空间。

其他应用——近期SSE的研究成果支持更复杂的查询和作为一个黑盒使用的多客户端设置SSE[ 13 ]。因此我们的数据结构和相关的操作(包括支持动态数据库)随时准备支持极大数量级的数据库。在这些更丰富/复杂加密的搜索设置(见第二节的末尾)。

实施——我们的实现对比之前最具伸缩性[ 3 ]的系统，在两个数量级大数据集仍然是有效的，研究出了我们第一个支持含数百亿索引记录/关键字对的大数量级数据库的SSE系统。我们将在V部分介绍我们的原型设计和实验结果。

相比之前的工作——在图1 对我们的基本理论方案和之前的工作进行了比较。基本方案推广和极大的简化了文献[3]中的隐藏方法，其通过要求底层数据结构的安全性质来使分析复杂化。

对有N对记录-关键字的数据库,我们的基本方案生成一个加密的最佳大小的指标，方案仅泄漏大小N和匹配的记录id，在假设字典检索时间消耗为的前提下处理搜索r个结果时能达到最佳的时间。对于搜索操作而言，并行的进程数目影响不是特别大。大多先前的设计会有额外的信息泄露，如单一关键字的数量,单个关键字的最大匹配数目,等等。这些作品中的一些还将它们的加密索引填充到它们的输入大小的二次方（最差情况），这对于大数据集是完全不切实际的。之前的大部分工作凸显的一个显著问题是处理困难的并行性：除了[ 3 ]，之前能实现并行搜索的设计有两个，但都需要二次填充。就像[ 7 ]需要人工寻查一个加密的链表,完全没有并行可言。看到图1的“Ind Leak”，“Index Size”， “Search Time” 三列。

先前的动态方案要么有一个不切实际的大索引[ 14 ]，要么会泄漏添加文件的结构[ 15 ]，这意味着服务器学习了，指出了关键字在它们被添加时在哪些文档中出现的形式，与通常的SSE泄漏事实（如总数据库大小）相比，这是一种严重的泄漏形式。我们的动态扩展保持最优索引大小，且只泄露基本大小信息（而不是文档结构，如[15]）。与以前的动态方案不同，我们不会在每次删除后回收空间，相反，我们设想其中删除相对少的应用，或更一般地，其中执行数据的周期性完全重新加密（重新加密可能是期望用于减轻来自动态SSE方案进行更新时的泄漏）。

更多相关工作——我们认为SSE的概念源自Song，Wagner和Perrig的工作[19]。数个设计改进了原始计划以提供的安全性和效率。与我们的构建最相似的是Chase和Kamara [5]和Cash等人[ 3 ]。Chase和Kamara也使用字典，但是以填充的方式，在大数据集中不可能实现。Cash等人实现了类似于我们的基本构造的方案，但是不处理更新，或者如在V-E节中所示，他们的方法实现与本设计相同等级的实际可伸缩性。从[ 2 ]开始，还有一个关于可搜索的公钥加密的相关设计方向，所有这些都基于线性时间搜索而不缩放。我们处理的SSE的版本本质地泄漏匹配查询文件的标识符，当查询被重复时也一样。使用私人信息检索[6]或忽略的RAM [ 10 ]甚至可以隐藏这些信息。忽略的RAM的几个最近的改进使其进一步朝实用性[ 11 ]，[ 20 ]，但是远远不清楚，它们与SSE方案在规模上竞争，因为必须实现明文搜索作为抽象RAM程序，然后运行程序在ORAM方案下没有泄漏信息，例如，通过计时。

组织——初步定义在第II部分中给出。 我们的非动态（即静态）SSE结构在第III节中给出，动态扩展在第IV节中给出。 最后，我们报告第五节中的实施情况。（如表一所示）

表1 不同Scheme下的时间复杂度

II. 定义和工具

安全参数表示为lambda;。我们将使用可变输入长度PRFs的标准概念和对称加密方案（c.f. [16]）。对于这些原语，我们做出简化的假设，它们的密钥总是在{0,1}lambda;中，并且用于加密方案的密钥生成选择随机密钥。我们的一些结构将在随机预言机模型[ 1 ]中分析，随机的预言机表示为H。我们的结构将使用假定在选择明文攻击下具有伪随机密文的对称加密方案，我们称之为RCPA安全。形式上，这说明攻击者不能区分一个预言机返回的对选择消息的加密和长度等于密文的一个随机字符串。 ^{全文共29554字，剩余内容已隐藏，支付完成后下载完整资料}

资料编号：[143000]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

您可能感兴趣的文章

• 为非政府组织OG慈善基金会设计的基于社区的救灾管理系统外文翻译资料
• 基于UML建模的医疗系统电子健康服务软件外文翻译资料
• 开发一种具有增强现实功能的智能手机应用程序， 以支持护理学生对心衰的虚拟学习外文翻译资料
• 在开发 Web 应用程序中应用 Vue.JS 框架外文翻译资料
• 基于MES系统的生产车间信息管理研究外文翻译资料
• 基于Vue.js和MySQL的电子商务平台的设计与实现外文翻译资料
• 详细的Spring配置和SpringBoot外文翻译资料
• 基于NS2的DSR和AODV协议的性能比较研究外文翻译资料
• 不同仿真参数下NS2的TCP吞吐量性能外文翻译资料
• 基于Spring Boot和VUE的车辆管理系统实现外文翻译资料