Safety KNN

Construction safety KNN Requirements for encryption functions —— Non distance recoverable

The following conditions are met , It is not distance recoverable encryption , Can be used to construct security KNN

The above definition requires ,E(q)!=E(p), Even if q==p

The simplest construction is like this ：
p and q The scalar product of can be expressed as p^TIq=(p^TM)(M^-1q), So let's make p’=E_T(p,K)=M^Tp, meanwhile q’=E_Q(q,K)=M^-1q

Then meet the requirements （i）p’^Tq’=p^TMM^-1q = p^Tq
Meet the requirements at the same time （ii）p1’^Tp2’=p1^TMM^Tp2 != p^Tq

A simple KNN structure

Comparison method ：

these two items. (d+1) The scalar product of dimensional points can be expressed as

But this scheme can not resist the chosen ciphertext attack
Prove the following ：

Able to resist selected ciphertext attacks KNN structure

Random Asymmetric Splitting

The query vector q Or data point p Split in two , If

take d The dimension vector is extended to d’ dimension

take d The dimension vector is extended to d’ dimension ,（d<d’） And ensure that the product of the added dimensions is zero