psi.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "psi.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.8.8"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "metadata": {
        "id": "WIE6RCg2fdbj",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "037273b0-57aa-43fe-a8ee-80feab4e66bb"
      },
      "source": [
        "##########################################################################################\n",
        "\n",
        "!pip install PyCryptoDomex elgamal\n",
        "\n",
        "# You only need to run this line once to install the library and then comment it out\n",
        "\n",
        "##########################################################################################\n",
        "\n",
        "from multiprocessing import Pipe, Process\n",
        "from elgamal.elgamal import Elgamal, PublicKey, CipherText\n",
        "from random import randint, getrandbits\n",
        "\n",
        "# lengh of public key (bytes)\n",
        "key_length = 32 \n",
        "# length of item (bits)\n",
        "item_bit_length = 5\n",
        "# length of mask (lambda)\n",
        "mask_bit_length = 6\n",
        "# number of items\n",
        "num_item = 8\n",
        "\n",
        "##########################################################################################\n",
        "\n",
        "# Alice's process\n",
        "def Alice(end_a): \n",
        "  \n",
        "    # set held by Alice\n",
        "    item_set = [28, 15, 7, 3, 23, 20, 31, 19]\n",
        "\n",
        "    # intersection of Bob's and Alice's sets\n",
        "    intersection = set()\n",
        "\n",
        "    # iterate over each item of Alice's\n",
        "    for item in item_set:\n",
        "        \n",
        "        # indicator if x equals some item in Bob's set\n",
        "        b = False\n",
        "\n",
        "        # iterate over each item of Bob's\n",
        "        for i in range(num_item):\n",
        "            \n",
        "            # check whether item is in Bob's set using private equality test\n",
        "            for j in range(item_bit_length):\n",
        "            \n",
        "                # TODO: get the j-th bit of item\n",
        "                bit = item >> (item_bit_length-1-j) & 1\n",
        "\n",
        "                # TODO: generate a pair of public, secret keys of Elgamal\n",
        "                pk, sk = Elgamal.newkeys(key_length)\n",
        "\n",
        "                # TODO: generate a plausible random public key\n",
        "                random_y = randint(1, pk.p-1)\n",
        "\n",
        "                # TODO: construct the message of format\n",
        "                # (i, j, random_y, pk.y, pk.p, pk.g) if bit is 1 or (i, j, pk.y, random_y, pk.p, pk.g) if bit is 0\n",
        "                if bit:\n",
        "                    msg = \",\".join([str(t) for t in[i, j, random_y, pk.y, pk.p, pk.g]])\n",
        "                    \n",
        "                else:\n",
        "                    msg = \",\".join([str(t) for t in[i, j, pk.y, random_y, pk.p, pk.g]])\n",
        "\n",
        "                # send message to Bob\n",
        "                end_a.send(msg)\n",
        "\n",
        "                # receive message from Bob\n",
        "                masks = end_a.recv().split(',')\n",
        "\n",
        "                # TODO: construct the ciphertext corresponding to bit\n",
        "                cipher = CipherText(int(masks[bit*2]), int(masks[bit*2+1]))\n",
        "\n",
        "                # TODO: decrypt the ciphertext to get the message\n",
        "                mask = int(Elgamal.decrypt(cipher, sk))\n",
        "\n",
        "                # TODO: update Alice's overall mask by XOR with mask               \n",
        "                if j == 0:\n",
        "                    alice_mask = mask\n",
        "                else:\n",
        "                    alice_mask ^=  mask\n",
        "\n",
        "                if j == item_bit_length-1:\n",
        "                    bob_mask = int(end_a.recv())\n",
        "                    # TODO: check if Alice's and Bob's overall masks agree if it is the last bit\n",
        "                    b = alice_mask == bob_mask\n",
        "\n",
        "            if b:\n",
        "                intersection.add(item)\n",
        "                break\n",
        "\n",
        "    # indicate that the protocol is over \n",
        "    end_a.send('done!')\n",
        "    print('Alice and Bob\\'s intersection is:', intersection)\n",
        "\n",
        "\n",
        "##########################################################################################\n",
        "\n",
        "\n",
        "# Bob's process\n",
        "def Bob(end_b):\n",
        "\n",
        "    # set of items held by Bob\n",
        "    item_set = [14, 23, 2, 24, 7, 5, 17, 20]\n",
        "    \n",
        "    while True:\n",
        "          \n",
        "          # receive Alice's request\n",
        "          msg = end_b.recv()\n",
        "\n",
        "          # receive the signal that the protocol is over\n",
        "          if msg == 'done!':\n",
        "              break\n",
        "          \n",
        "          # retrieve fields from the request\n",
        "          fields = msg.split(',')\n",
        "          i, j, y0, y1, p, g = int(fields[0]), int(fields[1]), int(fields[2]), int(fields[3]), int(fields[4]), int(fields[5])\n",
        "            \n",
        "          # identify the item Alice is checking against \n",
        "          item = item_set[i]\n",
        "            \n",
        "          # reset bob's mask if Alice is checking a new item\n",
        "          if j == 0:\n",
        "              bob_mask = 0\n",
        "            \n",
        "          # identify the bit Alice is checking against\n",
        "          bit = item >> (item_bit_length-1-j) & 1\n",
        "            \n",
        "          # generate two masks for this bit\n",
        "          masks = [getrandbits(mask_bit_length), getrandbits(mask_bit_length)]\n",
        "          \n",
        "          # update Bob's overall mask by XOR \n",
        "          bob_mask ^= masks[bit]\n",
        "            \n",
        "          # encryption for the first mask\n",
        "          pk = PublicKey(p, g, y0)\n",
        "          mask0 = Elgamal.encrypt(bytes(str(masks[0]), 'utf-8'), pk)\n",
        "    \n",
        "          # encryption for the second mask \n",
        "          pk = PublicKey(p, g, y1)\n",
        "          mask1 = Elgamal.encrypt(bytes(str(masks[1]), 'utf-8'), pk)\n",
        "       \n",
        "          # send response back to Alice\n",
        "          msg = ','.join([str(t) for t in [mask0.a, mask0.b, mask1.a, mask1.b]])\n",
        "          end_b.send(msg)\n",
        "            \n",
        "          # send Bob's overall mask if it is the last bit      \n",
        "          if j == item_bit_length - 1:\n",
        "              end_b.send(str(bob_mask))\n",
        "\n",
        "##########################################################################################\n",
        "if __name__ == \"__main__\":\n",
        "\n",
        "    end_a, end_b = Pipe()\n",
        "    \n",
        "    # start Alice's process\n",
        "    alice_p = Process(target=Alice, args=(end_a,))\n",
        "    alice_p.start()\n",
        "\n",
        "    # start Bob's process\n",
        "    Bob(end_b)\n",
        "\n",
        "    # wait for Alice's process to end\n",
        "    alice_p.join()"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Requirement already satisfied: PyCryptoDomex in /usr/local/lib/python3.7/dist-packages (3.11.0)\n",
            "Requirement already satisfied: elgamal in /usr/local/lib/python3.7/dist-packages (0.0.5)\n",
            "Alice and Bob's intersection is: {23, 20, 7}\n"
          ]
        }
      ]
    }
  ]
}