计算同态加密向量之间的距离度量

Question

有没有一种方法可以在同态加密向量之间计算距离度量（欧几里得距离、余弦相似度或曼哈顿距离）？

具体来说，我想使用变换器生成文档嵌入（embedding），对这些嵌入进行同态加密，并希望计算嵌入之间的距离度量以获得文档相似性分数。

我已经评估了像concrete-numpy、TenSEAL和Pyfhel（HE库）这样的库，每个库似乎都缺少特定的数学运算，无论是除法、累积和还是绝对值，这都阻止了生成上述任何列出的距离度量。

（我找到了这个：https://github.com/ibarrond/Pyfhel/blob/master/examples/Demo_8_HammingDist.py 它计算加密向量之间的汉明距离，但这个度量标准对于文档相似性没有帮助）。

- Brian Behe

---

您可以在Pyfhel存储库中提出同样的问题，作为GitHub问题，并且我可以确保为您提供适当的答案！一些指针是，除法/绝对值在大多数FHE方案中不被广泛支持（那些支持它的方案，都是通过近似实现的）。 - ibarrond

Answer 1

[感谢ibarrond - 答案在此处找到：https://github.com/ibarrond/Pyfhel/issues/155]

确实有方法！您只需要依靠一些技巧来克服CKKS/BFV方案中支持操作的限制（主要是加法和乘法）：

余弦相似度：表示为CS(x, y) = (sum(xᵢ * yᵢ))/(||x|| * ||y||)，它需要一个除法和一个范数。

技巧：将向量归一化为x' = x / ||x||和y' = y / ||y||，加密x'和y'并执行简单的标量积sum(xᵢ' * yᵢ')以获得余弦相似度（请查看Demo_7_ScalarProd.py如何做到这一点）。

欧几里得距离：表示为ED(x, y) = sqrt( sum(xᵢ² - yᵢ²))，它需要一个平方根。

诀窍：使用平方欧几里得距离（Squared Euclidean Distance），其中SED = sum(xᵢ² - yᵢ²)。在Pyfhel中，您可以原生地执行逐元素平方（Demo_3），然后使用Pyfhel.cumul_add进行累积求和（在Demo_7和Demo_8中有一些示例）。

曼哈顿距离：定义为MD(x, y) = sum(|xᵢ - yᵢ|)，需要计算绝对值。

诀窍：如果只加密二进制值（即，x̂，ŷ s.t. x̂ᵢ，ŷᵢ）∈{0,1} ∀ i），则可以重新定义MD(x̂, ŷ) = sum((x̂ᵢ - ŷᵢ)²) = HD(x̂, ŷ)，即汉明距离，它在Demo_8中实现。对于非二进制向量，您至少可以计算平方曼哈顿距离SMD(x, y) = sum((xᵢ - yᵢ)²)，缺少一个平方根以获得MD。

一般提示： 在加密之前（例如归一化）和解密之后（例如结果的平方根）利用您可以执行的操作来避免在FHE中计算非线性函数！

参考演示可以在这里找到：https://github.com/ibarrond/Pyfhel/tree/master/examples

- Brian Behe