0
$\begingroup$

I want to implement Semi-Honest protocol proposed by Freedman and others in python. The code is shown below. However, I could not understand the result after decrypting. Please could you explain me, what I am doing wrong? How this protocol indicating to me that intersection/common point exist between two different sets of points. This is not a coding problem. The problem is how to interpret the algorithm for understanding. A numerical answer will be very helpful. But encryption is required which can not written as a numerical value. That is why code is provided which explains I much I could understand from the algorithm. And may be somebody can help to explain the cryptographic algorithm using coding.

Semi-Honest protocol

#pip install phe

from phe import paillier
public_key, private_key = paillier.generate_paillier_keypair()
"""
Alice has a set of numbers = [2 3]
Bob has a set of numbers = [4 5 6] 
Semi-Honest protocol will tell us, if there is any common point then this protocol
indicate that. 

1. Alice create a polynomial equation based on her values as roots
(x-2)(x-3) = x^2 - 5x + 6. the coefficients  of the equations are: 1,-5,6
Now, send this coefficients using Homomorphic Encryption. En(1),En(-5),En(6)
2. 
"""
# coefficients of the Alice equation
a1 = 1
a2 = -5
a3 = 6

encrypted_number_a1 = public_key.encrypt(a1) # En(1)
encrypted_number_a2 = public_key.encrypt(a2) # En(-5)
encrypted_number_a3 = public_key.encrypt(a3) # En(6)

# set value of Bob
b1 = 55
b2 = 56
b3 = 57

# Bob evaluates polynomial P(bk) 
En_P_bk = encrypted_number_a1*b1 + encrypted_number_a2*b2 + encrypted_number_a3*b3

# Bob selects a random number r
r = 7

# Alice can learn whether bk is in the intersection A \ B by decrypting E (bk) 
# with her private key and checking that D (E (b-k)) = b-k is in Alice. 
c1 = En_P_bk*r + b1
c2 = En_P_bk*r + b2 
c3 = En_P_bk*r + b3 

decrypted_number_x1 = private_key.decrypt(c1) 
decrypted_number_x2 = private_key.decrypt(c2)
decrypted_number_x3 = private_key.decrypt(c3)
print (decrypted_number_x1, decrypted_number_x2, decrypted_number_x3 )
$\endgroup$