Proof-of-Concept: Private Set Intersection

psi-poc.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# Private Set Intersection (PSI)\n",
        "\n",
        "PSI computes the cardinality of the intersection of two sets between two parties, respectively, without revealing the contents of the sets to the other party.\n",
        "This is achieved using [homomorphic encryption](https://en.wikipedia.org/wiki/Homomorphic_encryption), and the Paillier-system in particular, which has useful algebraic characteristics like *E(m_1 ⋅ m_2) = E(m_1) ⋅ E(m_2)* and others (cf. [Paillier 1999, Section 8](https://link.springer.com/content/pdf/10.1007/3-540-48910-X_16.pdf)).\n",
        "\n",
        "**Goal:** Build a proof of concept for the algorithms described as *Protocol II* in [Zeilemaker et al. (2013)](https://www.paolopalmieri.com/pdf/Zeilemaker_Erkin_Palmieri_et_al_WIFS2013.pdf) and or *PM-Semi-Honest Protocol* in [Freedman et al. (2004)](https://www.researchgate.net/publication/2869590_Efficient_Private_Matching_and_Set_Intersection).\n"
      ],
      "metadata": {
        "id": "ZVqApegX7TC8"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "!pip install tenseal"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "yrkKqxrHLe-U",
        "outputId": "e774499a-0f24-480e-b953-803edd9a9ee0"
      },
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Collecting tenseal\n",
            "  Downloading tenseal-0.3.14-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (4.9 MB)\n",
            "\u001b[2K     \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m4.9/4.9 MB\u001b[0m \u001b[31m4.6 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hInstalling collected packages: tenseal\n",
            "Successfully installed tenseal-0.3.14\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 29,
      "metadata": {
        "id": "eElJToE5BUq6"
      },
      "outputs": [],
      "source": [
        "import tenseal as ts\n",
        "import numpy as np\n",
        "import random\n",
        "\n",
        "# Regarding the parameters: Bigger numbers allow for bigger polynomials with\n",
        "# bigger numbers but will affect computational performance.\n",
        "# Ref: https://github.com/OpenMined/TenSEAL/blob/main/tutorials/Tutorial%203%20-%20Benchmarks.ipynb\n",
        "context = ts.context(ts.SCHEME_TYPE.BFV, poly_modulus_degree=32768, plain_modulus=270794753)\n",
        "\n",
        "# Alice's and Bob's secret sets\n",
        "A = [1, 2, 4, 8, 16, 32, 64]\n",
        "B = [2, 4, 6, 8, 10, 12, 32]\n",
        "\n",
        "# Alice computes and then encrypts her coefficients\n",
        "coefficients = np.poly(A).tolist()\n",
        "coefficients = [ts.bfv_vector(context, [int(coeff)]) for coeff in coefficients]\n",
        "\n",
        "# Bob proceeds with his calculations based on Alice's encrypted coefficients\n",
        "bobs = []\n",
        "for b in B:\n",
        "    p = sum(c * (b ** i) for i, c in enumerate(reversed(coefficients)))\n",
        "    r_vector = ts.bfv_vector(context, [random.randint(0, 1<<10)])\n",
        "    encrypted_result = r_vector * p\n",
        "    bobs.append(encrypted_result)\n",
        "\n",
        "random.shuffle(bobs)\n",
        "\n",
        "# Alice decrypts the results to get the final values\n",
        "res = [bob.decrypt()[0] for bob in bobs]\n",
        "\n",
        "# The number of zeros in the result set determines the cardinality of the intersection between A and B.\n",
        "assert len(set(A).intersection(set(B))) == sum(x == 0 for x in res)"
      ]
    }
  ]
}