英语原文共 12 页
Order-Revealing Encryption: New Constructions,
Applications, and Lower Bounds
订单显示加密：新构造，应用程序和下限
|
Kevin Lewi Stanford University klewi@cs.stanford.edu |
David J. Wu Stanford University dwu4@cs.stanford.edu |
摘 要
在过去几年中，人们对开发搜索加密数据的方法产生了浓厚的兴趣。在范围查询的情况下，一种简单的解决方案是使用保持顺序加密（OPE）方案（即，支持对加密值进行比较的加密方案）来加密数据库的内容。但是，Naveed等人。 （CCS 2015）最近表明，OPE加密的数据库极易受到“推理攻击”的影响。
在这项工作中，我们考虑一个称为订单显示加密（ORE）的相关原语，它是OPE的概括，允许更强的安全性。我们首先为小消息空间构建一个新的ORE方案，该方案实现了“最佳可能”的ORE安全概念。接下来，我们介绍一种“域扩展”技术，并将其应用于我们的小消息空间ORE。虽然我们的域扩展技术确实会导致安全性损失，但我们获得的ORE方案比我们的分析更安全，我们也给OPE一个严格的下限，并表明没有有效的OPE方案可以最好地满足安全性，如果消息空间只包含三个消息。因此，即使是小型消息空间，实现强大的安全性概念也需要超越OPE。
最后，我们研究了新的ORE方案的属性，并展示了如何使用它构建一个有效的范围查询协议，该协议对Naveed等人的推理攻击具有很强的鲁棒性。我们还提供了新的ORE方案的完整实现，并表明我们的方案不仅比现有的OPE方案更安全，而且速度更快：加密32位整数只需要55微秒，速度提高65倍以上比现有的OPE计划。
ABSTRACT
In the last few years, there has been significant interest in developing methods to search over encrypted data. In the case of range queries, a simple solution is to encrypt the contents of the database using an order-preserving encryption (OPE) scheme (i.e., an encryption scheme that supports comparisons over encrypted values). However, Naveed et al. (CCS 2015) recently showed that OPE-encrypted databases are extremely vulnerable to “inference attacks.”
In this work, we consider a related primitive called orderrevealing encryption (ORE), which is a generalization of OPE that allows for stronger security. We begin by constructing a new ORE scheme for small message spaces which achieves the“best-possible”notion of security for ORE. Next, we introduce a“domain-extension”technique and apply it to our small-message-space ORE. While our domain-extension technique does incur a loss in security, the resulting ORE scheme we obtain is more secure than all existing (stateless and non-interactive) OPE and ORE schemes which are practical. All of our constructions rely only on symmetric primitives. As part of our analysis, we also give a tight lower bound for OPE and show that no efficient OPE scheme can satisfy best-possible security if the message space contains just three messages. Thus, achieving strong notions of security for even small message spaces requires moving beyond OPE.
Finally, we examine the properties of our new ORE scheme and show how to use it to construct an efficient range query protocol that is robust against the inference attacks of Naveed et al. We also give a full implementation of our new ORE scheme, and show that not only is our scheme more secure than existing OPE schemes, it is also faster: encrypting a 32-bit integer requires just 55 microseconds, which is more than 65 times faster than existing OPE schemes.
lowast;
The full version of this paper [43] with complete proofs is available at http://eprint.iacr.org/2016/612.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. CCSrsquo;16, October 24-28, 2016, Vienna, Austria
DOI: http://dx.doi.org/10.1145/2976749.2978376
引言
如今，大型企业和政府收集和存储的关于我们的个人信息比以往任何时候都多。 随着公司和组织（如Anthem [1]，eBay [39]和美国选民数据库[26]）的高调数据泄露变得异常普遍，我们必须开发实用的方法来保护我们的个人数据 在云端。
减轻数据库泄露造成的损害的一种方法是在将数据存储在云中之前加密数据。 然而，这是以功能为代价的：一旦数据被加密，在没有首先解密数据的情况下对数据执行搜索就更加困难。 因此，安全研究人员已转向开发既保护数据库内容又支持对加密数据进行有效操作（如搜索）的方法。
属性保留加密。支持在加密数据库上搜索的一种方法是通过属性保留加密（PPE）[9,48,21]。 PPE方案是一种加密方案，其中密文显示其底层明文的特定属性。示例包括确定性加密，其中密文显示消息之间的相等性，以及保序加密（OPE）[2,9]，其中密文显示消息的排序。确定性和保留订单的加密方案已经在Crypt DB [51] 中使用，并且还在Sky-high Networks，Cipher Cloud，Google Encrypted Big Query等商业中使用。 PPE用于加密关系数据库的主要吸引力之一是它们是轻量级的，因此可以在对现有数据库进行最小更改的情况下进行部署。例如，在OPE方案中，密文本身是数字的，并且密文的顺序精确地与明文的顺序一致。因此，搜索使用OPE加密的列与搜索未加密的列相同。
PPE和OPE的局限性。虽然PPE，特别是OPE为搜索加密数据提供了实用的解决方案，但这些方案还泄漏了大量有关其基础明文的信息。 例如，Boldyreva et al. [10] 表明单个OPE密文泄漏了其底层明文的最重要部分的一半！
最近，Naveed et al. [46] 描述了对使用确定性和保留顺序的加密方案加密的关系数据库的一系列推理攻击。 他们表明，只要加密数据库的数据转储以及来自公共数据库的辅助信息，攻击者就能成功地从各自的密文中恢复几乎所有基础明文值。。
我们的目标. 由于现有OPE方案的安全性有限以及对使用PPE加密的数据库进行推理攻击的新威胁，我们在这项工作中的目标是为比较构建一个实用的属性保留加密，与现有的OPE方案相比，实现了更强的安全保障。 同时提供针对离线推理攻击的鲁棒性，例如Naveed et al考虑的那些攻击。
订单显示加密。为了解决OPE的局限性，我们依赖于一种密切相关但更灵活的称为订单显示加密（ORE）的概念[12,22]。 在这项工作中，我们专注于非交互式和无状态方案 - 这是我们所知道的大规模部署的唯一方案。 我们在第8节中调查了替代解决方案的工作。在OPE方案中，明文和密文空间必须是数字和有序的。 此外，密文本身保留了底层明文的顺序。虽然此属性使OPE适合于对加密数据执行范围查询，但它也限制了OPE方案可实现的安全性。在他们最初的工作中，Boldyreva et al.[9] 为OPE引入了“最佳可能”语义安全的概念，该概念指出密文不会泄漏超出明文排序的任何信息。不幸的是，在同样的工作和后续工作[10]中，他们表明任何具有最佳安全性的OPE方案必须具有密文，其长度在明文的长度上呈指数增长。Popa et al. [50] 进一步扩展了这个下限，以适用于有状态的，交互式的OPE方案。这些下限排除了为大型消息空间构建有效OPE方案的任何希望。 作为妥协，Boldyreva et al.[9] 为OPE方案引入了较弱的安全概念（POPF-CCA），但很难量化POPF-CCA安全方案的泄漏。
最近，Boneh et al. [12] 引入了ORE的概念，它对密文空间的结构没有任何限制。ORE方案只需要存在一个可公开计算的函数来比较两个密文。通过放宽对密文空间的约束，Boneh et al.方案是第一个（非交互式和无状态）方案，以实现最佳的语义安全性。然而，它们的构造依赖于多线性图[14,27,23]，并且远非实际可行。最近，Chenette et al. [22] 为ORE引入了一种新的安全模型，该模型明确地模拟了ORE方案的信息泄漏。他们还提供了第一个有效实施的ORE方案。 然而，他们的方案还揭示了两个加密值之间的第一位的索引。
ORE的左/右框架
在描述我们的主要贡献之前，我们首先重点介绍我们在本工作中使用的订单显示加密的“左/右”框架。我们的概念改编自多输入功能加密的类似定义[33, 12]，其中加密功能在不同的“输入槽”上运行。在多输入功能加密方案中（其中ORE是一种特殊情况） ，只有当每个插槽都有一个密文时，才会显示有关明文的信息。
我们现在描述加密到不同输入槽的概念如何应用于订单显示加密。 在vanilla ORE方案中，有一种加密算法可以接收消息并输出密文。比较算法然后采用两个密文并输出两个基础消息的比较关系。在左/右框架中，我们修改此接口并将加密函数分解为两个单独的函数：“左”加密函数和“右”加密函数。这些加密函数中的每一个都接收消息和密钥，并分别输出“左”或“右”密文。接下来，比较函数采用左密文和右密文，而不是采用两个密文，并输出两个基础消息之间的比较关系（由左右密文加密）。我们注意到左/右框架
资料编号：[4150]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
