notebooks/seal_bgv_scheme.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6162898e-dbae-4e89-891c-00ce70cb8f0e",
   "metadata": {},
   "source": [
    "# PySEAL \n",
    "\n",
    "In this notebook, we will explore the [PySEAL library](https://github.com/Huelse/SEAL-Python) - for BGV scheme. \n",
    "\n",
    "(NOTE: We have to build this inside the SEAL-python repo. This notebook will not run unless you clone a copy of the [repository](https://github.com/Huelse/SEAL-Python) and then follow the README.md to build first.)\n",
    "\n",
    "The BGV encryption scheme proposed in 2011 by Brakerski, Gentry and Vaikuntanathan. It is a fully homomorphic encryption scheme that works for both an LWE and an RLWE instance, but they achieve a better performance with the RLWE instance, therefore the focus here will be on the RLWE setup. The way they found for keeping the ciphertext error within a given bound was to use the technique of modulus switching as introduced by Brakerski and Vaikuntanathan. This modulo reduction maps a ciphertext `~c` defined in a ring `Rq`, to a ring `Rp`, where `p < q`, which keeps the error `e` contained within the ciphertext at the same level. This enables one to multiply two ciphertexts and keep the error level constant. By leveraging the bootstrapping technique, one can do this process indefinitely, which opens the way for an FHE scheme."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a5c972a5-b807-40be-9691-3daa28b94c82",
   "metadata": {},
   "outputs": [],
   "source": [
    "from seal import *\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "a72005bc-e716-4192-9be7-7beb5df20bfe",
   "metadata": {},
   "outputs": [],
   "source": [
    "# function to print the vector\n",
    "def print_vector(vector):\n",
    "    print('[ ', end='')\n",
    "    for i in range(0, 8):\n",
    "        print(vector[i], end=', ')\n",
    "    print('... ]')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "0b63a047-b9a0-4107-9b1e-19f7aff88b4a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialize the encryption parameters for BGV scheme\n",
    "parms = EncryptionParameters (scheme_type.bgv)\n",
    "\"\"\"\n",
    "Sets the degree of the polynomial modulus parameter to the specified value.\n",
    "The polynomial modulus directly affects the number of coefficients in\n",
    "PlainText polynomials, the size of CipherText elements, the computational\n",
    "performance of the scheme (bigger is worse), and the security level (bigger\n",
    "is better).\n",
    "\n",
    "Specifying the degree of the polynomial modulus parameter.\n",
    "This modulus is a power of 2 like 1024, 2048, 4096, 8192, 16384, or 32768.\n",
    "We chose 8192 here because we are taking in account a sample use case where \n",
    "poly_modulus_degree is the number of slots per plain text of elements to be \n",
    "encoded in single ciphertext in a 2 by n/2 rectangular matrix \n",
    "(Type 2^D for D in [10,16])\n",
    "\n",
    "\"\"\"\n",
    "poly_modulus_degree = 8192\n",
    "parms.set_poly_modulus_degree(poly_modulus_degree)\n",
    "parms.set_coeff_modulus(CoeffModulus.BFVDefault(poly_modulus_degree))\n",
    "parms.set_plain_modulus(PlainModulus.Batching(poly_modulus_degree, 20))\n",
    "context = SEALContext(parms)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c56e7ba-ab58-40bb-9665-834f1b59fd0e",
   "metadata": {},
   "source": [
    "Generate context for BGV scheme"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "c0dcf5f8-ea6f-4b0a-b363-9777e2826ea1",
   "metadata": {},
   "outputs": [],
   "source": [
    "keygen = KeyGenerator(context)\n",
    "secret_key = keygen.secret_key()\n",
    "public_key = keygen.create_public_key()\n",
    "relin_keys = keygen.create_relin_keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "828d32b1-80c3-4f49-b82f-2bd483b16a7d",
   "metadata": {},
   "outputs": [],
   "source": [
    "encryptor = Encryptor(context, public_key)\n",
    "evaluator = Evaluator(context)\n",
    "decryptor = Decryptor(context, secret_key)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "436a084f-7700-472e-b59f-f9900f775ad4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Plaintext matrix row size: 4096.0\n"
     ]
    }
   ],
   "source": [
    "\"\"\" Batch encoder Creates a PlainText from a given matrix. \n",
    "This function \"batches\" a given matrix of either signed or unsigned integers\n",
    "modulo the PlainText modulus into a PlainText element, and storesthe result \n",
    "in the destination parameter.\n",
    "\"\"\"\n",
    "batch_encoder = BatchEncoder(context)\n",
    "\n",
    "# The total number of batching slots available to hold data\n",
    "slot_count = batch_encoder.slot_count()\n",
    "row_size = slot_count / 2\n",
    "print(f'Plaintext matrix row size: {row_size}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "f3ea8c33-6ebf-425a-a57f-f60af97c47a5",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialize the pod matrix\n",
    "pod_matrix = [0] * slot_count\n",
    "pod_matrix[0] = 1\n",
    "pod_matrix[1] = 2\n",
    "pod_matrix[2] = 3\n",
    "pod_matrix[3] = 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "1e95586e-ee23-48b0-ac51-7b242960c970",
   "metadata": {},
   "outputs": [],
   "source": [
    "x_plain = batch_encoder.encode(pod_matrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "513121f4-bab7-4e8d-b677-4b8b0d1f23b2",
   "metadata": {},
   "source": [
    "#### Let's try and find the noise budget"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "8cb5531b-bdf3-40c6-b8b2-789f81fc99c3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "noise budget in freshly encrypted x: 145\n",
      "--------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "x_encrypted = encryptor.encrypt(x_plain)\n",
    "print(f'noise budget in freshly encrypted x: {decryptor.invariant_noise_budget(x_encrypted)}')\n",
    "print('-'*50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "a5fbf77d-5225-470c-942b-b190bf9bc325",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "size of x_squared: 3\n",
      "size of x_squared (after relinearization): 2\n",
      "noise budget in x_squared: 109 bits\n",
      "[ 1, 4, 9, 16, 0, 0, 0, 0, ... ]\n",
      "--------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "x_squared = evaluator.square(x_encrypted)\n",
    "print(f'size of x_squared: {x_squared.size()}')\n",
    "evaluator.relinearize_inplace(x_squared, relin_keys)\n",
    "print(f'size of x_squared (after relinearization): {x_squared.size()}')\n",
    "print(f'noise budget in x_squared: {decryptor.invariant_noise_budget(x_squared)} bits')\n",
    "decrypted_result = decryptor.decrypt(x_squared)\n",
    "pod_result = batch_encoder.decode(decrypted_result)\n",
    "print_vector(pod_result)\n",
    "print('-'*50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "5f35f04f-af48-4b53-907c-99a76550a552",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "size of x_4th: 3\n",
      "size of x_4th (after relinearization): 2\n",
      "noise budget in x_4th: 34 bits\n",
      "[ 1, 16, 81, 256, 0, 0, 0, 0, ... ]\n",
      "--------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "x_4th = evaluator.square(x_squared)\n",
    "print(f'size of x_4th: {x_4th.size()}')\n",
    "evaluator.relinearize_inplace(x_4th, relin_keys)\n",
    "print(f'size of x_4th (after relinearization): { x_4th.size()}')\n",
    "print(f'noise budget in x_4th: {decryptor.invariant_noise_budget(x_4th)} bits')\n",
    "decrypted_result = decryptor.decrypt(x_4th)\n",
    "pod_result = batch_encoder.decode(decrypted_result)\n",
    "print_vector(pod_result)\n",
    "print('-'*50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "f9db39da-4d90-4e85-809c-504b49c80333",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "size of x_8th: 3\n",
      "size of x_8th (after relinearization): 2\n",
      "noise budget in x_8th: 0 bits\n",
      "[ -184705, -229604, -73320, -487859, -396130, -483233, 61567, 259176, ... ]\n",
      "run out of noise budget\n",
      "----------------------------------------------------------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "x_8th = evaluator.square(x_4th)\n",
    "print(f'size of x_8th: {x_8th.size()}')\n",
    "evaluator.relinearize_inplace(x_8th, relin_keys)\n",
    "print(f'size of x_8th (after relinearization): { x_8th.size()}')\n",
    "print(f'noise budget in x_8th: {decryptor.invariant_noise_budget(x_8th)} bits')\n",
    "decrypted_result = decryptor.decrypt(x_8th)\n",
    "pod_result = batch_encoder.decode(decrypted_result)\n",
    "print_vector(pod_result)\n",
    "print('run out of noise budget')\n",
    "print('-'*100)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b1d4b8b-cc5a-4507-827c-d38a161df604",
   "metadata": {},
   "source": [
    "#### Now, let's find the noise budget with modulus switching."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "81cd9aeb-df4c-408e-ae7f-e3dd99f3f023",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "noise budget in freshly encrypted x: 145\n",
      "--------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "x_encrypted = encryptor.encrypt(x_plain)\n",
    "print(f'noise budget in freshly encrypted x: {decryptor.invariant_noise_budget(x_encrypted)}')\n",
    "print('-'*50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "e41d134a-0d8d-4301-9a1e-fb535ef1ed8b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "size of x_squared: 3\n",
      "noise budget in x_squared (with modulus switching): 101 bits\n",
      "[ 1, 4, 9, 16, 0, 0, 0, 0, ... ]\n",
      "--------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "x_squared = evaluator.square(x_encrypted)\n",
    "print(f'size of x_squared: {x_squared.size()}')\n",
    "evaluator.relinearize_inplace(x_squared, relin_keys)\n",
    "evaluator.mod_switch_to_next_inplace(x_squared)\n",
    "print(f'noise budget in x_squared (with modulus switching): {decryptor.invariant_noise_budget(x_squared)} bits')\n",
    "decrypted_result = decryptor.decrypt(x_squared)\n",
    "pod_result = batch_encoder.decode(decrypted_result)\n",
    "print_vector(pod_result)\n",
    "print('-'*50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "a8edc4ee-f4bc-4cf9-a553-3ed796def47c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "size of x_4th: 3\n",
      "size of x_4th (after relinearization): 2\n",
      "noise budget in x_4th (with modulus switching): 57 bits\n",
      "[ 1, 16, 81, 256, 0, 0, 0, 0, ... ]\n",
      "--------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "x_4th = evaluator.square(x_squared)\n",
    "print(f'size of x_4th: {x_4th.size()}')\n",
    "evaluator.relinearize_inplace(x_4th, relin_keys)\n",
    "evaluator.mod_switch_to_next_inplace(x_4th)\n",
    "print(f'size of x_4th (after relinearization): { x_4th.size()}')\n",
    "print(f'noise budget in x_4th (with modulus switching): {decryptor.invariant_noise_budget(x_4th)} bits')\n",
    "decrypted_result = decryptor.decrypt(x_4th)\n",
    "pod_result = batch_encoder.decode(decrypted_result)\n",
    "print_vector(pod_result)\n",
    "print('-'*50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "1a7592ff-c233-49a1-bd93-5cd03b06e881",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "size of x_8th: 3\n",
      "size of x_8th (after relinearization): 2\n",
      "noise budget in x_8th (with modulus switching): 14 bits\n",
      "[ 1, 256, 6561, 65536, 0, 0, 0, 0, ... ]\n"
     ]
    }
   ],
   "source": [
    "x_8th = evaluator.square(x_4th)\n",
    "print(f'size of x_8th: {x_8th.size()}')\n",
    "evaluator.relinearize_inplace(x_8th, relin_keys)\n",
    "evaluator.mod_switch_to_next_inplace(x_8th)\n",
    "print(f'size of x_8th (after relinearization): { x_8th.size()}')\n",
    "print(f'noise budget in x_8th (with modulus switching): {decryptor.invariant_noise_budget(x_8th)} bits')\n",
    "decrypted_result = decryptor.decrypt(x_8th)\n",
    "pod_result = batch_encoder.decode(decrypted_result)\n",
    "print_vector(pod_result)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "357247cd-dda4-4cb1-9b19-ad163d6edec7",
   "metadata": {},
   "source": [
    "## Conclusion"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f84ad44b-c087-4add-8f09-738c22354218",
   "metadata": {},
   "source": [
    "In this notebook, we have looked into the BGV scheme using SEAL-python which is a wrapper for [Microsoft SEAL](https://github.com/microsoft/SEAL). Even though Microsoft is great, the limitation for us is that it is written in C++ and the existing wrappers don't do justice to the original work. \n",
    "\n",
    "This library is not super convenient to use for operations and lacks documentation for the functinalities. Besides this, it needs to be built inside the repo for SEAL-python, and is not a python library that we could directly import and carry out our operations."
   ]
  }
 ],
 "metadata": {
  "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}