python/homomorphic/Goldwasser–Micali.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import math\n",
    "import numpy as np\n",
    "import sympy\n",
    "from sympy import jacobi_symbol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# pick two primes\n",
    "p = 101\n",
    "q = 113\n",
    "\n",
    "assert sympy.isprime(p)\n",
    "assert sympy.isprime(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = p*q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "non-residue x: 3361\n"
     ]
    }
   ],
   "source": [
    "# find non-residue x\n",
    "while True:\n",
    "    x = random.randint(1, n-1)\n",
    "    if (\n",
    "        math.gcd(x, n) == 1 \n",
    "        and jacobi_symbol(x, p) == -1 \n",
    "        and jacobi_symbol(x, q) == -1\n",
    "    ):\n",
    "        break\n",
    "\n",
    "print(f'non-residue x: {x}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert jacobi_symbol(x, n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# encryption"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def encrypt_bit(b: int, r: int):\n",
    "    '''\n",
    "    Encrypt a bit\n",
    "    Args:\n",
    "        b (int): 0 or 1\n",
    "        r (int): random integer that co-prime to n\n",
    "    Returns:\n",
    "        encrypted bit (int)\n",
    "    '''\n",
    "    return ( pow(r, 2, n) * pow(x, b, n) ) % n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_random():\n",
    "    '''\n",
    "    Generate random that co-prime to n\n",
    "    Returns:\n",
    "        random number (int)\n",
    "    '''\n",
    "    while True:\n",
    "        r = random.randint(1, n)\n",
    "        if math.gcd(r, n) == 1:\n",
    "            break\n",
    "    return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def encrypt(m):\n",
    "    '''\n",
    "    Encrypt an integer message\n",
    "    Args:\n",
    "        m (int): plaintest\n",
    "    Returns:\n",
    "        ciphertext (int)\n",
    "    '''\n",
    "    m_binary = bin(m)[2:]\n",
    "    \n",
    "    # number of bits\n",
    "    k = len(m_binary)\n",
    "\n",
    "    c = []\n",
    "    for i in range(0, k):\n",
    "        mi = int(m_binary[i])\n",
    "        ri = generate_random()\n",
    "\n",
    "        ci = encrypt_bit(mi, ri)\n",
    "        c.append(ci)\n",
    "    return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = 17"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "c = encrypt(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7840, 348, 10743, 2612, 5414]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Decryption"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decrypt(c: list):\n",
    "    '''\n",
    "    Decrypt a ciphertext\n",
    "    Args:\n",
    "        c (list): ciphertext - encrypted bits of plaintext\n",
    "    Returns:\n",
    "        plaintext (int)\n",
    "    '''\n",
    "    m_binaries = []\n",
    "    for i in c:\n",
    "        xp = i % p\n",
    "        xq = i % q\n",
    "\n",
    "        if pow(xp, int((p-1)/2), p) == 1 and pow(xq, int((q-1)/2), q) == 1:\n",
    "            m_binaries.append(\"0\")\n",
    "        else:\n",
    "            m_binaries.append(\"1\")\n",
    "        \n",
    "    m_binary = \"\".join(m_binaries)\n",
    "    return int(m_binary, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "decrypt(c) == m"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# homomorphic features"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "args = [\n",
    "    [0, 0],\n",
    "    [0, 1],\n",
    "    [1, 0],\n",
    "    [1, 1]\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "for b1, b2 in args:\n",
    "    r1 = generate_random()\n",
    "    r2 = generate_random()\n",
    "\n",
    "    c1 = encrypt_bit(b1, r1)\n",
    "    c2 = encrypt_bit(b2, r2)\n",
    "\n",
    "    assert ( c1 * c2 ) % n == encrypt_bit(b1+b2, r1*r2)\n",
    "    b1_xor_b2 = b1 ^ b2\n",
    "    assert decrypt([( c1 * c2 ) % n]) == b1_xor_b2"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}