安全KNN

构造安全KNN加密函数的要求——非距离可恢复

在这里插入图片描述
满足以下条件，就不是距离可恢复加密了，便可以用于构造安全KNN

上面的定义就要求，E(q)!=E(p)，即使q==p

最简单的构造是这样的：
p和q的标量积可以表示为p^TIq=(p^TM)(M^-1q),那么我们让p’=E_T(p,K)=M^Tp,同时q’=E_Q(q,K)=M^-1q

那么满足要求（i）p’^Tq’=p^TMM^-1q = p^Tq
同时满足要求（ii）p1’^Tp2’=p1^TMM^Tp2 != p^Tq

在这里插入图片描述
比较方法：

这两个(d+1)维点的标量积可以表示为

但是这种方案不能对抗选择密文攻击
证明如下：

将查询向量q或者数据点p一分为二，假如
在这里插入图片描述

将d维向量扩展为d’维,（d<d’）并保证增加的维度的乘积为零