今年早些时候，我参加了这次演讲，并对这种方法印象深刻。该产品称为 EncryptedQuery ，它试图解决Private Information Retrieval的（我认为相关的）问题。PIR 可能是比 SE 更强的要求，因为使用 PIR，即使数据库服务器也不允许知道您搜索的内容或返回的记录。

我的谈话笔记：

• 动机：您希望将数据访问模式保密的情况。
• PIR 与不经意传输和安全多方计算的问题交织在一起。
• 2016 年，NSA 开源了一个名为 PIRK 的 PIR 软件堆栈
• 2017年PIRK项目退役。Envieta 公司接手了该项目并将其更名为 EncryptedQuery
• 它使用 Paillier 加密，这是同态的，即明文空间中的加法变为密文空间中的乘法。

我对算法的理解（可能是错误的，虽然这在当时是有道理的）是​​请求者加密了一个字符串

encr_req = encr(0 0 0 0 0 1 0 0 0 0 ...}

其中k包含 1 的第 th 列是它想要检索的行号。一旦这个字符串被加密，服务器就不知道哪一列包含 1。

然后服务器遍历数据库做

sum_i( encr_req[i] * encr(data[i]) )

因为 Paillier 是同态的，并且除了一个明文值之外的所有值都是 0，这相当于

0*data[0] + 0*data[1] + ... + 1*data[k] + 0*data[k+1] + ...

所以当你解密时，你会得到你的结果。

decr( sum_i( encr_req[i] * encr(data[i]) ) ) = data[k]

优点：

• 服务器能够通过 ID 处理从数据库中检索项目，而无需知道请求的是哪个 ID。
• 响应带宽低：sum_i( encr_req[i] * encr(data[i]) )是单个数据库字段的宽度。
• 可以扩展为在同一个查询中请求多个项目。

缺点：

• 性能：对于每个请求，服务器需要遍历整个数据库，使用请求者的公钥加密每个条目。
• 数据库中的所有行必须具有相同的位宽（出于加密步骤的性能原因，您希望保持较小的位宽）。
• 数据库中的条目数及其顺序必须是固定的，并且请求者知道。
• 对于大型或结构较少的数据库，请使用更通用（但不太安全）的可搜索加密。

TL;DR我不确定这是否真的回答了 HelloWorld 关于什么是最好的可搜索加密的问题：/

它很少见，因为可搜索的加密很少实用。

通常，这意味着您要么使用非常弱的密码，要么正在解密所有内容。第一种情况很糟糕，因为您可以使用加密中的模式通过足够大的样本来破解它。第二种更可取的方法非常缓慢，因为您必须解密整个数据集才能运行单个查询。无论哪种方式，可搜索加密仅对非常小的数据集才真正实用。

如果您希望能够在单个员工记录中搜索关键字，则可以使用它的一个示例。员工的 ID 将是未加密的；因此，您可以使用它来仅查询该人的记录，然后您可以将他的整个记录​​集传递给您的应用程序进行解密。然后搜索解密的数据，只输出你需要的字段。

也就是说，只要您进行精确搜索，可排序加密就有很多希望。可排序加密将每个新加密字符串的范围设置在它应该排序的字符串之间；所以，可以说以下是正确的：

7iFA384S4BPmuXokR9rcMI37SKnClqnE = ant
E10ZJbnmvJHs3MOKkzDXw7sd037kLCUJ = cat
miHBVXxATe1Jg6G97ug86zv31BxrpRAa = dog
z0L9f8Py12euq9Nhy9Zk0e9L83F8MiBi = man

如果我想将“fox”添加到列表中，那么我的加密算法将在“miHBVXxATe1Jg6G97ug86zv31BxrpRAa”和“z0L9f8Py12euq9Nhy9Zk0e9L83F8MiBi”之间返回，结果如下：

7iFA384S4BPmuXokR9rcMI37SKnClqnE = ant
E10ZJbnmvJHs3MOKkzDXw7sd037kLCUJ = cat
miHBVXxATe1Jg6G97ug86zv31BxrpRAa = dog
Pe2624gcRjP6YGWOnhiW2xnRomAjDYQK = fox // sorts alphabetically between dog and man
z0L9f8Py12euq9Nhy9Zk0e9L83F8MiBi = man

这是因为加密字符串的第一部分只是排序信息，第二部分是实际的加密数据

SortingId(Pe2624gcRjP6YG), EncyptedData(WOnhiW2xnRomAjDYQK)

一旦你对加密进行了排序，这意味着两件事，一个是你可以像对未加密的数据一样轻松地对加密数据进行排序，这本身就非常了不起，但其次，这意味着你可以有选择地解密。我个人不知道哪些数据库实际上支持/不支持这个，但是在上面的列表中，如果我搜索“man”并解密“dog”，那么我知道前 2 项不是 man 所以我不必解密它们来搜索它们。这意味着您的数据集越大，您需要解密以查找内容的数据集的百分比就越小。