我在最近在各个地方（包括此处），但我不知道这种加密方案应该如何工作。我可以想到的允许对加密数据进行这种比较的任何明显方法都将导致灾难性的安全失败。
当然，我认为OPE与传统加密相比必须涉及某种安全权衡，但是它似乎已经得到了积极的研究和使用，似乎有可能以至少保留一定程度的有用安全性的方式来实现。我只是不知道如何。
鉴于Google的快速搜索并没有找到任何方便的Wikipedia文章或OPE的其他流行摘要，我想在跳水之前先在这里找一个进入学术文献。 （在最糟糕的情况下，如果没人能击败我，我可能会稍后回答我自己的问题。）
因此，总而言之，我的问题是：保留顺序的加密如何工作，以及什么？它提供安全性吗？
#1 楼
在过去的几周中，我对这方面的最新工作非常熟悉。我还遵循Boldyreva等人在“保留订单的对称加密”中介绍的算法，构建了保留订单的加密方案原型。我将尽力解释我刚刚实现的方法，该方法需要对离散概率和超几何分布有一定的了解。让$ M $和$ N $是两个正整数，使得$ M
我们继续进行，因为注意到我们不需要提前使用全部功能。如果我们能找到一种方法，仅在需要将其作为密文时才生成有序集的元素，那么我们会很笨拙。这称为延迟采样功能。要懒惰地采样我们建议的函数，我们首先需要对范围空间进行一些不同的观察。
让我们坚持使用我们的随机保序注入型函数$ f $，我们将其视为一个该范围的元素的有序列表。如果范围中的某个元素在列表中，则将其视为“已标记”；如果不在列表中，则将其视为“未标记”。现在，将范围内的所有元素（带标记的和无标记的）视为巨大的垃圾桶中的球。如果我们不替换而绘制球，则在$ y $样本后绘制的“标记”球的数量$ x $可以用超几何分布来表征。 HGD具有PMF $$ \ frac {\ binom {y} {x} \ binom {N-y} {M-x}} {\ binom {N} {M}} $$
如果您不知道什么是PMF，请不要大汗淋漓。我们真正需要了解的是OPF和HGD之间的联系，这就是我们可以通过将范围点视为一个样本中“样本”的数量来找出OPF的多少个点位于范围的给定点以下。超几何实验，其中标记的球为$ M $，未标记的球为$ NM $。
另外要知道的是，我们可以高效，确定性地对HGD进行采样，即给定$ y $，$ M $，$ N $和一些随机硬币$ cc $，我们总能生成一个$ x $描述了我们的大小为$ y $的样本中标记的球的数量。
我保证，我们很亲密。我们已经奠定了基础，我们只需要弄清楚如何从中获得加密方案即可。
我们的加密方案从上面自然而然地遵循了。给定一个纯文本$ m \ in [M] $和一个密钥$ k $，我们可以通过递归搜索域和范围来懒惰地采样我们的OPF并生成密文$ n \ in [N] $，如下所示：
从整个域$ [M] $开始，范围$ [N] $。将$ y \ leftarrow \ frac {N} {2} $称为我们的距离差距。现在使用密钥$ k $生成一些伪随机硬币，并将它们与$ y $，$ M $和$ N $一起提供给HGD采样例程。这给了我们一个$ x \ le y $，它描述了我们的订单保持函数的点数少于$ y $。将此$ x $称为我们的域名差距。现在，因为OPF的$ m $点是$ m $的密文，所以我们知道，如果$ m \ lt x $，则需要在小于或等于$ x $且小于等于或等于$ y $。如果$ x \ lt m $，则以大于$ x $和$ y $的点为准。当我们的域仅剩一个点时，我们将拥有一组可以保存密文的点作为我们的范围。从该集合中选取一个点并将其输出。
所以毕竟，这只是一个花哨的二进制搜索？是的，是的。如果您想了解所有混乱的细节以及如何真正确保其安全，请阅读原始的OPE论文或查看CryptDB的实现。我的Java实现也将很快开源，因此您也可以检查一下。
保存订单的加密有几个警告。要了解所有详细信息，请阅读Alexandra Boldyreva，Nathan Chenette和Adam O'Neill重新审视的“保留顺序加密：改进的安全性分析和替代解决方案”（在CRYPTO 2011程序中，或此处的全文）。它分析了随机OPF的安全性并描述了其泄漏。他们最明显的问题结果与对手的能力有关，他们能够大概猜测密文的底层明文在明文空间中的位置。从直觉上讲，它表示某些攻击者可以在给定密文的情况下学习纯文本的一半比特。对于某些应用程序，这种功能性的安全性交易是可以接受的，但是在任何情况下，重要的是要知道使用这些方案时会得到什么。
如果您想在上面进行澄清，请发表评论，我将尝试进行有力的编辑。
#2 楼
有很多方法可以做到这一点。最简单的方法是简单地添加一个数字。给定X键，它将显示：
A>B
A+X>B+X
当然，这无论如何都不是很复杂的方法，但是可以使用更复杂的公式给出相同的结果。一般而言，他们只需要保存符号即可，使用多种多项式方法可以通过多种方法来确保符号有效。以特定底为底的对数可以是另一个这样的例子，以及对数的组合等。
对于一些更高级的方法，请看一下本文，其中详细介绍了不同的方法。
评论
$ \ begingroup $
如果将相同的键用于所有值，则该方法并不安全。假设$ c_1 = OPE（a）= a + x $和$ c_2 = OPE（b）= b + x $。然后，攻击者获得k = c2-c1 = a-b。因此，他知道$ a $将在$ [a-b，OPE（a）] $范围内。如果$ X $不够大，则蛮力攻击者可以尝试该范围内的所有值。
$ \ endgroup $
–好奇
13年4月19日在11:08
$ \ begingroup $
@ pg1989，能否请您解释一下，随机比特串（cc）在OPE中的惰性采样算法中的作用是什么。我试图理解Boldyreva等人的原始论文。提前致谢。
$ \ endgroup $
–阿卜杜拉·加尼（Abdullah Gani）
17年9月3日在7:30
评论
$ \ begingroup $
感谢您的出色回答！我觉得这不仅仅应该是接受和支持，因此您将在一天左右的时间内获得50代表额外的赏金。
$ \ endgroup $
–伊尔马里·卡洛宁
2013年6月23日7:41
$ \ begingroup $
谢谢：）有趣的是，在我真正致力于学习这些东西之前，我发现了这个问题，希望它能提供一个非常全面的答案，因此我不必费劲。现在可以了，哈哈。
$ \ endgroup $
– pg1989
2013年6月23日23:52
$ \ begingroup $
您不需要所有值。实际上，您只需要域和范围中字符串的位长，因为这决定了任一个值中的唯一值的数量（对于n位字符串，有$ 2 ^ n $值等）。
$ \ endgroup $
– pg1989
13年10月28日在19:00
$ \ begingroup $
不，它表示如果要实现IND-OCPA目标，则密文空间必须在明文空间中是指数的。即对于IND-OCPA，指数密文空间是必要条件，但不是充分条件。
$ \ endgroup $
– pg1989
13年10月28日在21:49
$ \ begingroup $
我的代码即将发布
$ \ endgroup $
– pg1989
13-10-28在21:50