撰写内容要求（可加页）：

用于搜索加密数据库的框架

摘要：

云计算是一种无处不在的范例，它造成了分布式计算执行方式的根本改变。服务器的安装、维护和可伸缩性的外包，加上具有竞争力的价格，使得这个平台对计算行业具有高度的吸引力。尽管如此，由于数据所有者无法真正控制处理硬件，因此对云中处理的数据的隐私保证仍然不足。这项工作提出了一种数据库加密框架，可以在不受信任的环境中保留数据保密性并保留搜索和更新功能。它使用揭示顺序的加密技术来完成时间复杂度为（logn）中的选择，并使用同态加密技术来实现密文上的计算。与现有技术相比，我们的方法提供了更高的安全性和灵活性。在MongoDB系统之上提供概念验证实现，并应用于Netflix大奖获奖解决方案所需的一些主要谓词的实现。

关键词：密码学，功能加密，同态加密，顺序显示加密，可搜索

加密、数据库

1. 介绍

云计算的大量采用导致了分布式计算执行方式的根本性变化。将服务器的安装、维护和可伸缩性外包出去的可能性，加上具有竞争力的价格，使得这项服务极具吸引力[1,2]。从移动计算到科学计算，该行业越来越多地接受云服务，并利用其潜力来提高可用性和降低运营成本[3,4]。然而，不能盲目信任云。恶意方可能获得对服务器的完全访问权，从而获得对数据的完全访问权。在这些威胁中，有利用漏洞的外部实体、请求信息的入侵政府、寻求不公平优势的竞争对手，甚至可能还有恶意的系统管理员。数据所有者对处理硬件没有真正的控制权，因此不能保证数据[5]的保密性。不充分和不安全使用云计算导致的机密泄露风险是真实和有形的。

隐私权保护的重要性经常被低估，其失败对社会造成的损害也常常被低估，因为隐私权侵犯的展开可能是完全不可预测的。标枪咨询服务公司的一份报告发现，数据泄露受害者和后来的金融欺诈受害者之间存在着令人痛心的联系。2016年，约75%的欺诈损失具有这一特点，相当于120亿美元[6]。这可以通过在用户端使用强加密来避免，即使在应用程序或云上也不会显示数据。

在整个数据库中使用标准加密的问题在于它消除了在没有加密密钥的情况下选择记录或评估任意功能的能力，从而将云减少为复杂且庞大的存储服务。为此，从匿名化和不提供正式隐私保障的启发式操作措施入手，提出了解决这一问题的替代方案。为数据库量身定制的加密方案(如可搜索加密)是一种很有前途的解决方案，可能会带来更明显的好处[7,8,9,10]。可搜索加密使云能够在不了解信息的情况下代表客户操作加密数据。因此，它解决了上述两个问题，既保持了云的机密性，又保留了一些有趣的特性。

1.1数据匿名化的挫折

2006年，Netflix与学术界分享了他们对改进向用户提供的推荐系统的兴趣。这种协同效应是针对3轮公开竞争，为最佳推荐算法提供财政奖励。Netflix商业模式的一个重要特点是，能够有效、果断地指导订户找到符合他们兴趣的内容。正确地这样做可以增强产品对休闲活动的重要性，巩固Netflix的商业地位，并确保客户的忠诚度[11]。

参赛者在1999年至2005年间接受了一套由Netflix订户提供的匿名电影收视率培训。该剧共有约50万名观众和约17000部电影，总收视率超过1亿。此数据集由电影标题、创建分级的时间戳、分级本身以及用于关联相同用户记录的标识号组成。没有共享有关客户的其他信息，如姓名、地址或性别。参加者的目标是根据他们之前在平台上观察到的行为，准确地预测有多少人会喜欢电影。

同年，美国在线(AOL)采取了类似的方法，发布了65.8万用户的数百万次搜索请求，目标是通过对真实数据[12]进行统计工作，为科学界做出贡献。与Netflix一样，美国在线(AOL)也在发布数据前努力匿名化数据。所有明显敏感的数据，如用户名和IP地址，都被禁止，由唯一的标识号代替。

在一些商业模型中，理解用户的兴趣并根据收集的数据预测用户行为的能力是可取的，因此这是科学文献中的一个热门话题[13、14、15]。然而，隐私保护的重要性仍然被低估，这是一个需要克服的挑战。例如，尽管Netflix进行了匿名化工作，但Narayanan和Shmatikov巧妙地展示了如何通过与公共知识库交叉引用信息来打破Netflix数据集的匿名性，正如互联网电影数据库（IMDB）所提供的那样[16]。使用类似的方法，《纽约时报》的记者能够将查询的一个子集与特定的人联系起来，将看似无辜的查询加入到非匿名的真实国家公共数据库中[17]。

1.2“意外”泄漏

这些事件引发了关于如何在不损害用户隐私的前提下安全收集和使用数据的讨论，但这一问题仍未得到解决。正如Narayanan和Felten所说，“数据隐私是一个难题”[18]。即使数据持有者选择了最保守的做法，从不共享数据，也可能发生系统破坏。

2013年，美国国家安全局(NSA)前雇员爱德华·斯诺登(Edward Snowden)披露了美国政府的一项大规模监控计划。它被命名为PRISM，其结构是一种大规模的数据拦截，用于收集信息进行后验分析。他们的技术可以说得到了美国法律体系的支持，甚至在数据所有者公司不知情的情况下也经常适用[19,20]。

两年后的2015年，阿什利·麦迪逊(Ashley Madison)网站数百万用户的个人数据被盗，被利用[21]安全漏洞的恶意团体泄露。结果，几起勒索甚至自杀的报道表明，数据泄露正变得越来越敏感。

同年，瑞典运输局决定将其IT业务外包给IBM。为了履行合同，后者选择在东欧的地点进行这些业务。这导致瑞典的机密数据被存储在外国数据中心，特别是捷克共和国、塞尔维亚和罗马尼亚。不出所料，这一决定导致了大规模的数据泄露，包括瑞典境内所有车辆的信息，包括警察和军用车辆。因此，数百万瑞典公民、军人、证人搬迁计划下的人的姓名、照片和家庭住址被曝光。

2016年，雅虎证实，一场可能是已知规模最大的大规模数据泄露事件影响了大约5亿个账户，并向世界披露了一个包含姓名、地址和电话号码的数据集[23]。

这些事件给我们带来了一种令人不安的感觉，即，尽管所有的努力都被忽视，但数据失信的风险随着可用数据的多少而以令人担忧的方式增加[24，25]。因此，一个看似显而易见的避免此类问题的策略就是简单地停止任何类型的数据集收集。

1.3通过放弃知识来保护隐私

历史证明，从第三方收集和存储数据的任务应该被视为有风险的。意外损害用户隐私的可能性太大，可能会带来极端后果。就像搜索引擎DuckDuckGo在一篇博客文章中说的那样，“唯一真正匿名的数据就是没有数据”，并因此宣称放弃存储用户数据的权利[26,27]。

处理这个问题的一种财务上更现实的方法不是完全放弃知识，而是通过在整个生命周期中对其进行加密来减少具有访问权限的实体:传输、存储和处理，对应用程序和云保密。因此，设置了一个新的安全屏障，将数据保密与正式的保证联系起来。

1.4我们的贡献

这项工作遵循当前的技术水平，并对可搜索加密数据库[28]的建模提出了指导意见。我们检测关系代数的主要原语，这些原语是保持数据库功能所必需的，同时还添加了增强的隐私保护属性。一组密码工具用于构造这些原语。它由允许数据选择的顺序显示加密、用于计算任意函数的同态加密和用于保护和增加一般数据处理灵活性的标准对称方案组成。特别是,我们建议选择原始的达到时间复杂度Theta;(logn)数据集的大小。此外，我们还提供了安全性分析和性能评估，以评估对执行时间和空间消耗的影响，以及验证框架的概念实现。它在MongoDB(一种流行的基于文档的数据库)上工作，并作为Python驱动程序的包装器实现。源代码是在GNU GPLv3许可证[29]下提供给社区的。

与CryptDB[7]相比，我们的建议提供了更强的安全性，因为即使在数据库和应用服务器受到损害的情况下，它也能够保持机密性。因为CryptDB将获取用户密钥的能力委托给应用服务器，所以它不能提供这样的安全保证。此外，我们的工作与数据库无关，它不仅限于SQL，还可以应用于不同的键值数据库。

这项工作的结构如下。第2节描述构建我们提出的解决方案所需的加密构建块。第3节和第4节定义了可搜索加密，讨论了相关的威胁，并介绍了现有的实现。第5节提出了我们的框架，第6节讨论了它在Netflix推荐系统中的适用性。我们的实验验证结果在第7节和第8节中给出。

2.构建块

密码系统的两大类主要是对称和非对称(或公钥)，由用户如何交换加密密钥来定义。对称方案使用相同的密钥进行加密和解密，或者等效地从另一个密钥有效地计算另一个密钥，而非对称方案生成由公钥和私钥组成的密钥对。前者是公开分发的，是向密钥所有者加密消息所需的唯一信息，而后者则应保密并用于解密。

除此之外，对于相同的消息密钥输入对，总是产生相同密文的密码系统被称为确定性密码系统。相反，当在加密过程中使用随机性时，称为概率论。接下来，我们回顾基本安全概念和特殊属性，它们使密码系统适合于特定的应用程序。稍后，我们将利用这些概念来分析我们提案的安全性。

2.1安全概念

密文不可分辨性是分析密码系统安全性的一个有用性质。当对手拥有或不具有对提供解密功能的Oracle的访问权限时，将考虑两种情况。通常情况下，通过一个游戏来评估这些信息，其中对手试图从挑战者生成的密文中获取信息[30]。

选择明文攻击下的不可区分性——IND-CPA在ind-cpa游戏中，挑战者生成一对加密密钥（pk，sk），使pk公开并保持sk秘密。对手的目标是识别从已知的两元素消息集中随机选择的消息创建的密文。允许通过pk和密文进行多项式有界的操作，包括加密（但不包括解密）。如果没有对手能够以不可忽略的概率实现目标，密码系统在选择明文攻击下是不可区分的。

选择密文攻击和自适应选择的密文攻击下的不区分性-- IND-CCA1和IND-CCA2这种不可区分性与IND-CPA不同，因为对手可以访问解密oracle。在这个游戏中，挑战再次是识别前面描述的密文，但现在攻击者能够使用解密结果。这款新游戏有两个版本，非自适应和自适应。在非自适应版本IND-CCA1中，攻击者可以使用解密oracle直到它收到质询密文。另一方面，在自适应版本中，即使在该事件之后，也允许他使用解密oracle。由于显而易见的原因，攻击者无法将挑战密文发送到解密oracle。如果没有对手能够以不可忽略的概率实现目标，则在选择的密文攻击/自适应选择的密文攻击下，密码系统是难以区分的。

选择关键字攻击和适应性选择关键字攻击下的不可区分性-- IND-CKA和IND-CKA2此安全性概念特定于基于关键字的可搜索加密的上下文[31]。它考虑了一个挑战者使用某些文档中的关键字集构建索引的场景。此索引使某人可以使用值Ťw ^，称为trapdoor，用于验证文档是否包含单词w。该游戏强制要求远程存储的文件或索引不应泄露任何信息，超出查询的结果和搜索模式。对手可以访问oracle，为任何单词提供相关的陷门。他的目标是使用这个神谕作为训练来应用所获得的知识并打破未知加密关键词的保密性。与IND-CCA1 / IND-CCA2游戏一样，该游戏的非适应性版本IND-CKA禁止攻击者在挑战者发送挑战陷阱后使用陷门oracle。另一方面，即使在此事件之后，适应性版本也允许使用陷门oracle。

如果每个对手与随机猜测相比只有微不足道的优势，那么密码系统在选择的关键字攻击下是无法区分的。

在有序选择的明文攻击下的不可区分性 -- IND-OCPA由Boldyreva等人引入，这个概念假设一个对手能够检索两个密文序列，导致任何两个消息序列的加密[ 32 ]。此外，他知道两个序列具有相同的排序。这个对手的目的是区分这些密文。如果没有对手能够以不可忽略的概率实现目标，则在有序选择的明文攻击下，密码系统是难以区分的。

2.2功能加密

被视为“功能性”的加密方案接收此类名称是因为它们支持对生成的密文执行一个或多个操作，因此不仅对安全存储有用。

揭示顺序加密（ORE）揭示顺序加密方案的特征是，除了通常的一组加密函数（如keygen和encrypt）之外，还具有一个能够比较密文并返回原始明文顺序的函数，如定义1所示。

定义1

（ore）让e是一个加密函数，c是一个比较函数，m1和m2是来自消息空间的明文。如果出现以下情况，则对（e，c）被定义为具有订单显示属性的加密方案，如果：

这是保序加密（ope）的一个推广，它将C固定为一个简单的数字比较[33]。

安全性 Lewi和Wu认为，ORE的“最佳可能”安全概念是IND-OCPA，这意味着有可能实现密文的不可分辨性，并且具有比OPE方案更强大的安全保障[ 34 ]。 。此外，与OPE不同，ORE本身并不具有确定性[ 35 ]。例如，Chenette等人。提出了一种在OPE方案中应用伪随机函数的ORE方案，而Lewi和Wu提出了完全建立在对称基元上的ORE方案，能够限

资料编号：[4171]