同态加密与处理正则表达式有多近？

Question

是否有任何合理的同态加密协议支持一些有意义的正则语言/表达式片段和/或编辑距离界限？

我怀疑同态加密从来不会处理这种“插入有界的任意垃圾”，但可能是具有不同界限的正则表达式的子集，或者可能达到某种绑定编辑距离。

这个问题是在关于CryptDB的讨论中提出的。

Answer 1

一般来说，目前对加密数据的搜索仍然是相当有限的。除了CryptDB，SADS是我见过的另一个。然而，如果不了解更多关于您的安全需求，就很难确切地说明(例如，regex是保密的还是仅与其匹配的数据是保密的？)有值得信赖的第三方吗？等等)。

就我个人而言，我从未见过允许对数据集进行完全正则搜索的系统，在这种情况下，查询或数据都是保密的。我看到的最好的是关键字匹配和AND和OR布尔逻辑(参见SADS)。DARPA继续程序的第二阶段寻找某种正则搜索能力。取决于这一阶段的成功程度，一年后我们可能会有一些进展。

顺便提一下，从我对全同态加密(FHE)的了解来看，一个完全同态的系统似乎可以执行这种搜索。然而，FHE系统目前还不太成熟，因为研究人员仍在努力研究如何使其实用化。