英语原文共 20 页

泄露信息有限的实用顺序揭露加密

Nathan Chenette, Kevin Lewi , Stephen A. Weis , and David J. Wu

Rose-Hulman Institute of Technology

Stanford University

Facebook, Inc.

摘要

在顺序保存加密模式中，加密算法产生一个保存原文顺序的密文。顺序保存加密方案在过去十年中被广为研究，但是人们对这种加密方案的安全性仍然所知甚少。最近，Boneh等人 (Eurocrypt 2015）提出了一种叫做顺序揭露加密的一般化顺序保存加密方法，并且提出了一种实现这种观念的最安全的构造。由于他们的构造依赖多线性的地图，对于很多应用来说不切实际，这就留下了理论上的结果。

在这方面，我们通过伪随机函数建立了一个高效的顺序揭露加密方法。我们提出了第一个高效的顺序揭露加密方案。通过一个能够精确量化加密方案泄露情况的函数，这个加密方案实现了基于仿真的安全概念。实际上，在我们的加密方案中，密文大概只比原文长的1.6倍。并且，我们展示了如何将我们的构造和已有的顺序保存加密模式组合起来，这也使得这种方案与先前的顺序保存加密方案相比更加安全。

1引言

如果一个对称加密方案的密文保留了很多潜在原文的顺序信息，那么这个对称加密方案就被称为顺序保存的。顺序保存加密(OPE)这个概念是由Agrawal等人提出的。[1]Agrawal等人展示了如何使用这种加密方案有效地解答加密数据的一系列问题，包括排序问题、搜索问题等。事实上，现有的OPE解决方案已经被使用来实现这些确切的目的。自从OPE的概念提出后，在密码学和数据库社区中，有相当多的工作在分析不同OPE模式的安全性。然而，问题是，尽管已经有许多OPE的实际应用，基于安全考虑的最佳候选OPE方案仍然没有被很好地理解。

之前的工作

第一个OPE方式是由Agrawal等人提出，依赖于启发式方法，缺乏正式的安全分析。随后，Boldyreva等人 给出了OPE方案的第一个正式安全性定义。Boldyreva等人为OPE方案提出了两个主要概念。第一个安全性概念被称为顺序选择原文攻击下的不可分辨性（IND-OCPA）。IND-OCPA刻意被视为是一般化的语义安全性，也就是说，一串消息加密后，不应该暴露任何关于其序列的潜在信息。然而，Boldyreva等人同时也提出没有高效的顺序保存加密方案能做这一点（IND-OCPA安全），即使是在密文空间比原文空间大指数级的设置中也不行。

由于IN-OCPA的限制条件，Boldyreva等人提出了一种要求更低的安全性概念POPF-CCA。其中，OPE方案的加密函数与一个随机的顺序保存函数比较，也就是说，加密算法表现为一个真实的随机顺序保存函数。同时，Boldyreva等人给出了一个显示结构来使OPE方案满足POPF-CCA。然而，POPF-CCA安全性定义并没有精确地说明满足这个定义的OPE方案泄露的信息。事实上，实现这个安全性概念的加密方案作为一个单一加密并没有满足语义安全。在接下来的工作中，Boldyreva等人表示在他们的OPE方案中，密文大概泄露了潜在原文的前半部分。除此之外，为了更好地量化满足POPF-CCA的OPE方案泄露的信息，他们提出了一些新安全性定义。

最近，Boneh等人提出了一个一般化的OPE方案，这个方案就是顺序揭露加密（ORE）。在OPE方案中，密文是用数值估值的，潜在原文的顺序由在数值上比较密文得到。在ORE中则相反，密文不需要被限制为任何特殊的形式，而是存在一个公开的可计算比较函数，输入两个密文后输出其潜在原文数值顺序。虽然这种一般化方法在第一眼看上去会比较晦涩，但Boneh等人通过多线性地图构建了一种ORE方案，尽可能地实现了和IND-OCPA概念相同安全性。

Boneh等人的ORE构建方法主要的缺点是依赖复杂的工具和这些工具带来的很多可能性，因此实际上并不可行。

• 1. 我们的成果

我们总结了这方面的主要成果，包括一个新的基于仿真的ORE安全概念以及实现这个安全概念的实际构建方案。同时我们也展示了我们的新构建方案如何被用来实现严格的安全性概念，也同其他无状态的高效可行的OPE和ORE加密方案作了比较。

安全模型

在我们的工作中，除了使用更有效地路线外，我们沿用了Boneh等人构建ORE方案的一般方法。我们的第一个成果是一个新的顺序揭露加密方案的安全性定义，它允许并且能清晰地模拟加密方案中的泄露。我们对这个新安全模型的设计目标包括两个层面：第一，这个安全性模型应该能够使得构建能高效的实施；第二，对于任何加密方案的信息泄露，应该能够提供一种精确地量化方法。Boldreva等人提出的两种主要安全概念即IND-OCPA和POPF-CCA，各自满足前面提到两个层面中的其中一个。特别地，所有实现IND-OCPA安全性的非交互式、无状态的ORE方案都需要坚实的加密环境，比如多线性地图或者不可分辨性混淆。因此，这并不是高效的可实行ORE方案。另一边的POPF-CCA很难精确量化ORE方案的顺序泄露情况。Boldyreva等人为原文从同一分配中产生的泄露提供了一些具体的限制，对于更一般的分配，这种泄露还是不清晰的。

在我们的工作中，我们对ORE的安全性定义给出了一个基于仿真的定义，关于对泄露函数L。换句话说，我们的定义表明无论攻击者能够从消息,...,的加密中推断出什么，他所推断出的信息也可以仅凭给出的函数L(,...,）来得到。ORE的“最佳”安全性应该符合一种情形，即对所有的消息对和来说，泄漏函数只是输出是否小于。通过考虑额外泄露的可能性，从标准设想中构建切实可行的ORE方案是可能的。因此，我们的构建方法提供一种具体的平衡安全性和效率性的方法。我们的安全性定义类似于在先前对称加密文献中可搜索的基于仿真的定义。

构建

在我们的主要构建中，我们展示了如何通过一个单项函数（更准确地说是一个伪随机函数）构建一个ORE方案。这个特殊的ORE方案比潜在信息序列揭露了更多一些的信息。具体地说，两端密文消息和也揭露了和第一个比特序列的不同。换句话说，我们的ORE方案泄露了一些关于潜在消息的相关距离的信息。

关于我们的基于伪随机函数的构建方法，我们给出了一个简要的概述。我们方案中的秘钥包含一个伪随机函数值k，伪随机函数的输出空间是一个{0,1,2}的集合。每个密文都有一串被伪随机函数输出值掩饰过的比特串作为前缀。更准确地说，为了加密一串长为n比特的消息，加密算法有效地计算：

可以注意到，为了支持可变化的伪随机函数输入值，我们简单地填充了下输入值。我们将在第三节详细描述我们的构建方法。经过伪随机函数，密文将变为未知的元组。

为了比较由消息m和mrsquo;得到的密文元组ct和ctrsquo;，评估者首先要找到两个元组中第一个不同项的标记i，因为和是m和mrsquo;前i比特的函数值，所以两个元组中第一个项不相同的下标i是m和mrsquo;不同的第一个比特。确定两个元组第i个比特不同后，使用和来确定消息在i比特位置是0还是1。相反地，如果两个元组相同，那么两个消息m和mrsquo;也相同，这种构建的安全性就符合伪随机函数。

在我们的候选方案中，密文大概是个比特，n是消息的比特长度。作为一个比较点，Boldyreva等人的OPE方案中的密文只有n 1个比特长。尽管在我们的方案中密文要更长（通过一个乘数因子），[8]文献的作者注意到，在Boldyreva等人的方案中，即使密文空间的大小增加到超过n 1比特，他们的构建安全性也不会提高明显的数值。

接下来我们在3.2节解释了如何将我们的ORE方案转化为OPE方案，这将以较长的密文为代价。这种转化对那些具有比较大的密文空间并且希望顺序关系不需要经常用比较函数去计算的应用来说很有用。我们的这种转化方法是很自然的，也不会降低原来的ORE方案的安全性。此外，我们注意到产生的OPE方案没有表现得像随机顺序保存函数。因此，我们的方案能够实现更高的安全性。

与现有的方案相比

首先，我们注意到在2.3节中，任何OPE方案的安全性都是能够使用ORE加密来增强的。产生的ORE方案的安全性至少是和原来的OPE方案相同的，并且继承了ORE方案的安全属性。因此，通过已存在的OPE构建来组建我们的ORE构建，我们获得的ORE方案至少是安全的。

通过ORE方案来组成OPE方案时会产生一个至少和原来的OPE方案一样安全的方案。我们展示了即使没有这个组成，根据Boldyreva等人提出对于随机顺序保存函数泄露的one-wayness标准[8]，我们的基础ORE方案仍旧能够实现更强的安全保证。在我们的工作中，我们提出了两种产生的one-wayness概念，并且展示了在统一的原文分发机制下，与满足POPF-CCA安全的OPE方案相比，我们的基础ORE方案能够实现严格强大的安全性。具体地说，Boldyreva等人展示了一个随机顺序保存函数泄露了消息一半的最重要比特串。相反，在相同的环境下，我们能够展示我们的基础ORE方案将不会泄露消息比特串的任何恒定部分。

• 1. 相关工作

近几年来，有很多关于顺序保存加密的工作和与之相关的理念[1,7,8,42,47,36,35,38,44]。在这个部分，我们将列出一些相关工作。

安全性定义

虽然Boldyreva等人提出的POPF-CCA安全性定义和伪随机函数PRF安全相似，却不能立即表明随机顺序保存函数的输出泄露了输入的哪些信息。在后续的工作中，Boldyreva等人提出了一些观念来捕获POPF-CCA安全方案泄露的信息。他们发现随机顺序保存函数泄露了每个消息至少一半的比特串。

Teranishi等人也提出基于不可分辨性的观念的OPE方案，包括这些实现安全性更强观念的构建。值得注意的是，他们的定义保证了在统一消息分配下，消息低序列比特的任何部分都是隐藏加密的。

最近，Naveed等人在实际应用情形下分析了顺序保存加密泄露的信息。

模块化OPE

Boldyreva等人还提出了模块化OPE的观点作为标准OPE的扩展。在模块化OPE中，在应用OPE之前，模块的转变应用于每个原文。这样做使得方案不是顺序保存的，但是自然而然地支持环绕式处理范围查询。他们的模块化OPE方案加入了一个额外的安全层，但应该注意，小规模的信息泄露暴露的转移值会使得添加的安全性失效。随后，Mavroforakis等人设计了一些工具来避免泄露使用模块化OPE方案时的转移值。

可变OPE

Popa等人提出了一个相关的观念，可视为双方协议的可变顺序保存编码方案允许一个使用者在一个数据库中增加和存储加密值，这样数据库就能够在不知道更多关于这个值得信息的情况下执行比较和范围查询。他们的构建是交互式的，利用了状态加密。在这种环境下工作，作者能够规避Boldyreva等人顺序保存加密的下限并且他们的方案是符合IND-OCPA安全的。

在接下来的工作中，Kerschbaum和Schrouml;pfer以提高客户端状态量的代价提升了Popa等人构建的通信复杂性。更确切地说，在他们的构建中，客户端需要维持的持久状态量根据插入数据库中元素的量线性增加。最近，Kerschbaum[35]提出一个频率隐藏OPE的新观念，在是否隐藏多重密文加密同一个值中引入了另外的不可预测性。与IND-OCPA相比，他们的观念提供了更强的安全保证。

最近，Roche等人提出了部分顺序保存编码，优化了那些需要巨量插入查询但是只需要适量范围查询的环境。与Popa等人的协议相比，他们的协议提高了插入的复杂性，而且客户端比Kerschbaum和Schrouml;pfer他们的构建维持更少的状态[36]。这里描述的所有方案都需要状态加密并且使用交互式加密过程。

ORE

Boneh等人提出的顺序揭露加密方案提供了另一种规避Boldyreva等人下限的方法。在ORE方案中，公共比较操作不需要大量地比较密文。事实上，密文本身不需要很多元素和有序集。先前Pandey和Rouselakis考虑过这种类型的缓和。在属性保存加密方案中，有一个公共可计算函数可以被用来评估密文，以确定有序属性的值。因为这个比较操作，顺序保存加密可以被视为属性保存加密方案。Pandey和Rouselakis提出并研究了一些属性保存加密的基于不可分辨性的安全观念，然而，他们并没有构建一个顺序保存加密方案。

就我们所知，所以已存在的提供IND-OCPA安全的ORE方案要么依赖于像不可分辨性困惑和多重线性地图那样很强的但不切实可行密码原语，要么仅仅实现了像公钥加密那样很低的安全性。ORE方案的安全性有条件地取决于猜测的密码多重线性地图安全性。然而，最近几个月中，出现了许多针对多重线性地图的攻击，这使得这种多重线性地图的安全性受到怀疑。

避免多重线性地图有利于充分研究数论或者基于格的假设，可以应用参数放大技术[3,12]去实现基于更简单设想的单输入函数加密方案，比如错误学习[30]或者语义安全公钥加密[45,32]。然而，由于潜在函数加密方案的限制，产生的ORE方案仅仅提供“受限的消息”，也就是说，安全性只能够在消息数量有最大值的先天界限下才能被保证。并且，在这个

资料编号：[4169]