SIS.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Collosion and quantum-resistant lattice hasher with accumulating properties"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Shortest integer solution problem:\n",
    "Given an integer `q`, a `k-times-m` matrix `M` picked uniformly at random (where `m >= k`) and a real `β`, find an integer vector `z`\n",
    "such that `M*z = 0 mod q` and `||z|| <= β`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Security parameter `k` and bound `n = poly(k)`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "k = 128\n",
    "n = k^8\n",
    "\n",
    "lmb = 1 # need to be > 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "parameter `q, mu, beta` for SIS problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "q: 1244142437461793964053\n",
      "mu: 18176\n",
      "beta: 9.71468927453313e18\n",
      "m: 9088\n"
     ]
    }
   ],
   "source": [
    "q = var('q')\n",
    "#assume(q>n)\n",
    "s = find_root(q/sqrt(log(q,2)+1) == sqrt(2)*n*k^(1/2 + lmb), 1, n^2)\n",
    "q = next_prime(s)\n",
    "RR(q/sqrt(ceil(log(q,2)))) >= RR(sqrt(2)*n*k^(1/2 + lmb))\n",
    "print(bool(q/sqrt(ceil(log(q,2))) >= sqrt(2)*n*k^(1/2 + lmb)))\n",
    "mu = ZZ(2*k*ceil(log(q,2)))\n",
    "beta = RR(n*sqrt(mu))\n",
    "m = ZZ(mu/2)\n",
    "G = GF(q)\n",
    "#print(\"Solution: \" + str(s))\n",
    "print(\"q: \" + str(q))\n",
    "print(\"mu: \" + str(mu))\n",
    "print(\"beta: \" + str(beta))\n",
    "print(\"m: \" + str(m))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Left and right matrices, uniform random from G"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "done\n"
     ]
    }
   ],
   "source": [
    "L = matrix([[G.random_element() for i in range(0, m)] for j in range(0,k)])\n",
    "#outf = open(\"/tmp/matrix\", \"w\")\n",
    "#outf.write(str(L))\n",
    "#outf.close()\n",
    "print(\"done\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Initial hash function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hash(x):\n",
    "    return (L*x) % q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "xvec = vector([G.random_element() for i in range(0, m)])\n",
    "Zp_result = hash(xvec)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Because the range and domain of the current scheme differs, we need to transform our hashes back to G to keep algebraic structures and achieve accumulating properties"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def transform(x):\n",
    "    return G(int(''.join([bin(i) for i in x]).replace(\"0b\",\"\"),2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "815150217032424563520"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "transform(Zp_result)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The final hasher procudes a `ceil(log2(q))+1` size output from an input at most `m` size:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hash(x):\n",
    "    t = (L*x) % q\n",
    "    return transform(t)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "reference sha: 240dfd9fe93b9520c273\n",
      "our hash: 1f8187eedd60a03e93\n"
     ]
    }
   ],
   "source": [
    "import hashlib\n",
    "sha = hashlib.sha1()\n",
    "xvec = random_vector(G, m)\n",
    "sha.update(str(xvec))\n",
    "print(\"reference sha: \" + sha.hexdigest()[0:20])\n",
    "print(\"our hash: \" + hex(ZZ(hash(xvec))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We want to prove that an element belongs to our 50-long array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "import hashlib\n",
    "test_data = [random_vector(G, m) for i in range(0, 5)]\n",
    "target_element = test_data[2]\n",
    "#print(target_element)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "acc = vector(G, [0 for i in range(0, 128)])\n",
    "for i in test_data:\n",
    "    acc += L*i "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "witness = acc + L*(target_element*-1) # we revoke our selected member from the accumulator in constant time!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "witness + L*(target_element) == acc # checking simply works by accumulating the member to our wittness"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 8.7",
   "language": "",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}