I am basically trying to perform euclidean distance calculation in the encrypted domain (Paillier encryption). Using the homomorphic properties of Paillier, the squared euclidean distance formula can be written as (paper):

$\newcommand{\opn}{\operatorname}$ $$\underbrace{\opn{Enc}\left(\sum^d_{i=1}p_i^2\right)}_{\text{(I)}}\cdot \underbrace{\opn{Enc}\left(\sum^d_{i=1}q_i^2\right)}_{\text{(II)}}\cdot \underbrace{\prod^d_{i=1}\opn{Enc}(q_i)^{-2p_i}}_{\text{(III)}}$$

I tried implementing this in matlab using two sample vectors a and b but I seem to be getting a completely wrong distance when decrypted. The euclidean distance of the two vectors without encryption is 100.5883 but when applying the above formula and then decrypting the result I get 10118

%I'm using the variable precision integer toolbox (vpi) to handle large numbers in Matlab
a = [10, 58, 23, 59, 78, 11];
b = [87, 15, 12, 32, 41, 22];

p = 708481;
q = 708497;
r = 461563;

n = p * q;

% calculating (I) from above equation, i.e. a^2
encA =vpi(zeros(size(A))); %initialize vector for encrypted values
sumA = 0;

for i=1:length(A)
    encA(i) = PaillierEncrypt(A(i), p, q, random_r); %this will encrypt the value at index i in the vector
    sumA = sumA + (A(i))^2;

enc_sumA = PaillierEncrypt(sumA, p, q, random_r); %now encrypt the summed value

% below is for (II) and (III) in the equation i.e. b^2 -2ab
encB =vpi(zeros(size(B)));
sumB = 0;
enc_prodAB = vpi(1);

for i=1:length(B)
    encB(i) = PaillierEncrypt(B(i), p, q, random_r);
    sumB = sumB + (B(i))^2;

%the below block is to assist in determining the mod of a negative exponent, basically it allows for this to run without error: mod((encA)^(-2*vpi(B)), n*n);
    a2 = encA(i); %the encrypted base
    d2 = (-2)*vpi(B(i)); %the exponent that is a non encrypted scalar
    n3 = n*n;

    negpowermod = @(a,d,n2) minv(powermod(a,abs(d),n2),n2); 

    result = negpowermod(a2,d2,n3);

    enc_prodAB = enc_prodAB * result;

enc_sumB = PaillierEncrypt(sumB, p, q, random_r);

dist = enc_sumA * enc_sumB * enc_prodAB;

Ive commented the above code as best I could to explain what I am doing. I'm sure I messed up the implementation somehow.

Some guidance would really be appreciated. Thanks

  • 1
    $\begingroup$ Other issues, in no particular order: n3 is used where n2 should be. Passing pand qas separate parameter to PaillierEncrypt is a huge design mistake showing a lack of understanding of what public/private key is about. Why compute the encB(i) when they do not get used? Not using encB(i) is correct if and only if the bare the $p_i$, but choosing that convention is an accident waiting to happen. A 40-bit n is dozens times too small for even mild security; execution time grows roughly as the cube of that; thus execution time may be underestimated by thousands... $\endgroup$ – fgrieu Jun 7 '18 at 22:00
  • $\begingroup$ ...To demonstrate something useful, the encryption of whatever the $q_i$ are must be done first, then the result passed to a party holding the $p_i$, which the code does not illustrate. What about modular reduction of enc_prodAB and friends like the final enc_sumB? If aand Aare the same thing, use the same case. How does random_rget an approriate random value? Is not that logically the job of PaillierEncryptto draw a random value, trimming a parameter and encapsulating encryption better? Ad nauseam. $\endgroup$ – fgrieu Jun 7 '18 at 22:00
  • $\begingroup$ @fgrieu Thanks for the detailed response. At the time I am interested in the implementation of euclidean distance in Paillier I am currently not targeting security or execution time. The values selected are random values just for the sake of getting this to work. At implementation stage I will focus on security, but right now I am teaching myself this and was hoping on understanding why my implementation was not working.. Also n3 is the same as n2 I just gave created a separate variable for my own clarity. $\endgroup$ – StuckInPhD Jun 8 '18 at 3:56
  • $\begingroup$ If "n3 is the same as n2" "for clarity", and the code contains affectation of n then n3 = n*n but no affectation of n2, I quit reviewing it. I'm still happy I learned that application of Paillier encryption where we can compute Euclidean distance between two points known by two respective parties, and have a third one decipher the outcome. $\endgroup$ – fgrieu Jun 8 '18 at 4:37
  • $\begingroup$ I'm glad this question helped you learn something but I'm still where I was yesterday. :( - Also n2 was used in an anonymous function negpowermod and since it was used there I did not want to pass value to it using the same variable name.. It would have worked but it would still have been clearer to use a different variable than the one used in the function handle.. thats why I used n3 to pass in the value to n2. Thats what I meant by for clarity $\endgroup$ – StuckInPhD Jun 8 '18 at 10:32

I don't see your problem. 10118 is indeed the square of the euclidian distance ~100.5883

  • $\begingroup$ oh my.. I dont know how I missed that.. how embarrassing.. Im glad that my implementation is correct. Many thanks for pointing that out $\endgroup$ – StuckInPhD Jun 8 '18 at 14:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.