如何在同态加密向量间计算距离度量（欧氏/余弦/曼哈顿）？

核心结论 #

可以通过近似计算或组合库原生操作实现欧氏距离、余弦相似度、曼哈顿距离，但目前没有库能原生支持所有完整操作，需要针对不同度量做适配。

各距离度量的具体实现路径 #

1. 欧氏距离 #

公式核心：$\sqrt{\sum (x_i - y_i)^2}$

• 先计算加密向量的差向量：$d_i = x_i - y_i$，所有HE库基本都支持逐元素减法
• 逐元素计算平方：$d_i^2$，这也是多数HE库的基础操作
• 累积求和替代：将平方向量与全1加密向量做点积（多数库支持向量点积），结果等价于平方和
• 平方根处理：原生加密态开方几乎没有库支持，可通过泰勒展开多项式近似实现；如果只需要相似度排序，直接用平方和代替欧氏距离即可（单调性一致，不影响排序结果）

2. 余弦相似度 #

公式核心：$\frac{x \cdot y}{||x|| \cdot ||y||}$

• 分子直接用加密向量点积实现，无难度
• 分母模长计算：用欧氏距离的方法得到$\sqrt{\sum x_i^2}$和$\sqrt{\sum y_i^2}$，再做加密态乘法
• 除法处理：转为乘法逆元近似（比如泰勒展开$\frac{1}{z}$）；如果你的嵌入在加密前做过L2归一化，分母为1，直接计算点积就是余弦相似度，这是最简便的方案

3. 曼哈顿距离 #

公式核心：$\sum |x_i - y_i|$

• 绝对值近似：通过$\sqrt{a^2}$实现，用多项式近似开方完成加密态绝对值计算
• 累积求和：同样用点积全1向量的方法替代
• 部分库（如TenSEAL）的新版本已经提供了近似绝对值的API，可直接调用

针对你评估的库的适配建议 #

• TenSEAL：CKKS方案对浮点向量支持友好，原生支持点积、逐元素平方，近似开方和绝对值可通过自定义多项式实现，是当前最适合的选择
• Pyfhel：可通过循环逐元素累加实现累积求和（效率低但可行），绝对值和除法需自行封装近似逻辑，适合对精度要求不高的场景
• concrete-numpy：侧重整数运算，若嵌入已量化为整数，可将绝对值转为整数操作（负数取反加1），累积求和用循环实现，适合低精度场景

替代方案 #

如果纯加密态计算成本过高，可考虑半同态混合方案：将加密嵌入发送到可信第三方，让其计算点积、平方和等中间加密结果，本地完成开方、除法等非加密态操作，同时确保第三方无法还原原始嵌入。

内容的提问来源于stack exchange，提问作者Brian Behe