python/homomorphic/Paillier.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "d4881311",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8792beca",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_prime(x):\n",
    "    for i in range(2, x):\n",
    "        if x % i == 0:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "0a26f11f",
   "metadata": {},
   "outputs": [],
   "source": [
    "p = 13\n",
    "q = 17\n",
    "assert p != q\n",
    "assert is_prime(p)\n",
    "assert is_prime(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "4dcd1e3d",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = p * q\n",
    "phi = (p-1)*(q-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "82988601",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lx(x):\n",
    "    y = (x-1)/n\n",
    "    assert y - int(y) == 0\n",
    "    return int(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "26b60d48",
   "metadata": {},
   "outputs": [],
   "source": [
    "g = 1 + n\n",
    "lmbda = phi * 1\n",
    "mu = pow(phi, -1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "2a77757d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "private key is lambda = 192. use this decryption.\n",
      "public key is g=222, n=221, mu=160. use this encryption.\n"
     ]
    }
   ],
   "source": [
    "print(f\"private key is lambda = {lmbda}. use this decryption.\")\n",
    "print(f\"public key is g={g}, n={n}, mu={mu}. use this encryption.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "8f72199a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def encrypt(m, r):\n",
    "    assert math.gcd(r, n) == 1\n",
    "    c = ( pow(g, m, n*n) * pow(r, n, n*n) ) % (n*n)\n",
    "    return c\n",
    "\n",
    "def decrypt(c):\n",
    "    p = ( lx(pow(c, lmbda, n*n)) * mu ) % (n)\n",
    "    return p"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "baf787cd",
   "metadata": {},
   "source": [
    "# encrypt and decrypt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "c74733c0",
   "metadata": {},
   "outputs": [],
   "source": [
    "m = 123\n",
    "r = random.randint(0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "f2585f11",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "50"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "6d9361ea",
   "metadata": {},
   "outputs": [],
   "source": [
    "c = encrypt(m, r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "b4bcfcdd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "34951"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "9ad6e91a",
   "metadata": {},
   "outputs": [],
   "source": [
    "p = decrypt(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "691459e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "assert m == p"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f05cc446",
   "metadata": {},
   "source": [
    "# additive homomorphic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "c161e1c5",
   "metadata": {},
   "outputs": [],
   "source": [
    "m1 = 123\n",
    "r1 = random.randint(0, n)\n",
    "\n",
    "m2 = 37\n",
    "r2 = random.randint(0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "78a11fe3",
   "metadata": {},
   "outputs": [],
   "source": [
    "c1 = encrypt(m1, r1)\n",
    "c2 = encrypt(m2, r2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "27c70ddb",
   "metadata": {},
   "outputs": [],
   "source": [
    "assert ( c1 * c2 ) % (n*n) == encrypt(m1 + m2, r1*r2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "74f2c098",
   "metadata": {},
   "source": [
    "# neutral element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "599b1f4f",
   "metadata": {},
   "outputs": [],
   "source": [
    "m1 = 123\n",
    "r1 = random.randint(0, n)\n",
    "\n",
    "m2 = 0\n",
    "r2 = random.randint(0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "c690d6b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "c1 = encrypt(m1, r1)\n",
    "c2 = encrypt(m2, r2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "18a8b9a9",
   "metadata": {},
   "outputs": [],
   "source": [
    "c1_reencrypted = ( c1 * c2 ) % (n*n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "55c8cd06",
   "metadata": {},
   "outputs": [],
   "source": [
    "assert c1_reencrypted != c1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "efc09b96",
   "metadata": {},
   "outputs": [],
   "source": [
    "assert decrypt(c1_reencrypted) == decrypt(c1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8f5e1170",
   "metadata": {},
   "source": [
    "# multiplicative homomorphic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "ca49cbcc",
   "metadata": {},
   "outputs": [],
   "source": [
    "m1 = 123\n",
    "r1 = random.randint(0, n)\n",
    "\n",
    "m2 = 25\n",
    "r2 = random.randint(0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "038ab72c",
   "metadata": {},
   "outputs": [],
   "source": [
    "c1 = encrypt(m1, r1)\n",
    "c2 = encrypt(m2, r2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "af6a1945",
   "metadata": {},
   "outputs": [],
   "source": [
    "assert pow(c1, m2, n*n) == encrypt(m1*m2, pow(r1, m2, n*n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "7330f0cc",
   "metadata": {},
   "outputs": [],
   "source": [
    "assert pow(c2, m1, n*n) == encrypt(m1*m2, pow(r2, m1, n*n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "310ca7bb",
   "metadata": {},
   "outputs": [],
   "source": [
    "assert decrypt(pow(c1, m2, n*n)) == (m1*m2) % n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "8bb0e630",
   "metadata": {},
   "outputs": [],
   "source": [
    "assert decrypt(pow(c2, m1, n*n)) == (m1*m2) % n"
   ]
  }
 ],
 "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.9.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}