Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

DS300 Homework 3 Instruction

Overview – In this homework, you are required to implement a two-party private set intersection (PSI) protocol based on a simple 1-out-of-2 oblivious transfer construct (). Some of the technical details can be found in Lecture 9. You are required to complete (finish the lines indicated by TODO: and submit the attached notebook file (psi.ipynb).

Setup – Make sure you have a Python running environment available. If not, Google Colab (https://colab.research.google.com) is strongly recommended as it includes most of the li-braries necessary  for this homework.

        In this protocol, Alice and Bob, who hold two item_set and wish to find out the intersection securely, serve as the receiver and sender Process, respectively, and communicate with the other through a Pipe. Specifically, Alice holds one end of the pipe (end_a) and can send and receive messages through the pipe by calling end_a.send() and end_a.recv(); Bob can perform similar operations on (end_b). The communication part has been implemented.

        We assume that Alice and Bob have the same number of items (num item). All the parameters have been defined (key_length, item_bit_length, mask_bit_length).

ElGamal – The  construct is based on ElGamal, a public key crypto system. In the home-work, we use the implementation in the elgamal library (https://pypi.org/project/elgamal/). Following are a few hints:

(1) To get the j-th bit of an integer item:

bit = item >> (item_bit_length-1-j) & 1

where item_bit_length is the total length of item (in bits).

(2) The function newkeys return a pair of keys, PublicKey and PrivateKey. A PublicKey pk consists of three integers (p, g, y);

pk, sk = ElGamal.newkeys(key_length)

print('public key:', pk.p, pk.g, pk.y)

(3) To simulate the oblivious key generation algorithm, we use the randint function:

random_y = randint(1, pk.p-1)

where pk is the public key in (1).

(4) For Bob to encrypt a message using Alice’s public key (whether it is the true public key or fake one), he needs to first construct an ElGamal object using the public key received from Alice. To reconstruct the public key at Bob’s side:

pk = PublicKey(p, g, y)

where (p, g, y) are the different parts of the received public key.

(5) To encrypt an integer integer using public key pk:

cipher = Elgamal.encrypt(bytes(str(integer), 'utf-8'), pk)

(6) To decrypt a cipher cipher to its plaintext (an integer) using secret key sk:

integer = int(Elgamal.decrypt(cipher, sk))

(7) To compute the bit-wise XOR of two integers integer1 and integer2 (and save the result in integer1):

integer1 ^= integer2

Private Equality Test – The PSI protocol is a na¨ıve extension of private equality test. That is, for each item x of Alice, it securely checks against each item y of Bob, whether x = y (x and y are assumed to have the same length). For each bit, Bob creates a pair of masks, mask0 for ‘0’ and mask1 for ‘1’; starting from the first bit, Alice maintains the bit-wise XOR of the masks (according to the bits of x) she has fetched from Bob; Bob maintains the bit-wise XOR of the masks (according to the bits of y); at the last bit, Bob sends Alice his overall mask mask_b, which Alice compares against her overall mask mask_a, and decides whether x = y by checking whether mask_a = mask_b.