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

Question

是否有方法计算两个同态加密向量之间的距离度量(欧几里德或余弦相似性或曼哈顿)？

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

我已经对库进行了评估，比如sum、TenSEAL和Pyfhel (HE库)，每个库似乎缺少一个特定的数学操作，无论是除法、累积和，还是绝对值，都无法生成上面列出的任何距离度量。

(我确实找到了这个：https://github.com/ibarrond/Pyfhel/blob/master/examples/Demo_8_HammingDist.py，它计算加密向量之间的hamming距离，但是这个度量方法无助于文档的相似性)。

Answer 1

信用归于ibarrond -答案如下: https://github.com/ibarrond/Pyfhel/issues/155

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

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

诀窍是:将向量x‘=x/而外x，y’，y，y，x‘，y’，并执行一个简单的标量乘积和(xᵢ‘* yᵢ')，以获得余弦相似性(请检查ᵢ如何做到这一点)。

欧氏距离：表示为ED(x，y) = sqrt(和(xᵢ2-yᵢ))，它需要一个平方根。

诀窍:用平方欧几里德距离代替，其中SED =sum(xᵢ2-yᵢ2)。在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̂ᵢ-ŷᵢ)2=HD(x̂，ŷ)，这是用∀实现的。对于非二进制向量，至少可以计算出平方曼哈顿距离SMD(x，y) =sum(xᵢ-yᵢ)，缺少一个平方根即可得到MD。

通用提示：利用您在加密之前(例如规范化)和解密后(例如，结果的平方根)可以执行的操作，以避免在FHE中计算非线性函数！

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