{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "d38674f6",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import sys\n",
    "import random\n",
    "import hashlib\n",
    "from collections import OrderedDict\n",
    "from numpy.polynomial import polynomial as P\n",
    "import time\n",
    "import tracemalloc\n",
    "import psutil\n",
    "import os"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "086ff489",
   "metadata": {},
   "outputs": [],
   "source": [
    "# please specify your parameters here\n",
    "m=\"Hello world\"\n",
    "d=100\n",
    "r=127"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "177eb816",
   "metadata": {},
   "outputs": [],
   "source": [
    "def one_v_poly(deg,r=127):\n",
    "  T=[[random.randint(0,r),0]]#used to store the result\n",
    "\n",
    "  for i in range(1,deg+1):\n",
    "    T.append([random.randint(0,r),i])\n",
    "\n",
    "  # print(T)\n",
    "  # if [0,0] in T:\n",
    "  #   T=T[1:]\n",
    "  return T#assume we have T[0][0]+T[1][0]*x+T[2][0]*x^2+...\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d7ed329",
   "metadata": {},
   "source": [
    "# Tropical Algebra"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "5ccc1f9a",
   "metadata": {},
   "outputs": [],
   "source": [
    "#let us code each monomial as an array\n",
    "#the first element indicates the coeff and the second element indicates the deg\n",
    "#2⨂x will be coded as [2,1]\n",
    "#5 will be coded as [5,0]\n",
    "#2⨂x⨂5=[2,1]+[5,0]=[7,1]\n",
    "def mono_otimes(A,B):#otimes for monomials\n",
    "  res=np.zeros(2)\n",
    "\n",
    "  res[0]=A[0]+B[0]\n",
    "  res[1]=A[1]+B[1]\n",
    "  return res\n",
    "\n",
    "def find_min_coef(A):#A is an array of array whose sec element are the same; find the minimal monomial of the same deg\n",
    "  if len(A)==1:\n",
    "    return A[0]\n",
    "  else:\n",
    "    res=np.zeros(2)\n",
    "    res[0]=A[0][0]\n",
    "    res[1]=A[0][1]\n",
    "    for i in A:\n",
    "      res[0]=min(res[0],i[0])\n",
    "      # res[1]=min(res[1],i[1])\n",
    "    return res\n",
    "\n",
    "\n",
    "def mono_oplus(A): #where A is an array of monomials\n",
    "  d=OrderedDict()\n",
    "  for i in A: #go through all the monomials\n",
    "    if i[1] in d:#check whether degree can be found in the dict\n",
    "      d[i[1]].append(i)\n",
    "    else:\n",
    "      d[i[1]]=[i]\n",
    "  # print(d)\n",
    "\n",
    "  sums=[]\n",
    "  for key,value in d.items():\n",
    "    if len(value)==1: #there is only one monomial of deg key\n",
    "      sums.append(value[0])\n",
    "    else:\n",
    "      sums.append(find_min_coef(value))\n",
    "  return sums\n",
    "\n",
    "#(A⊕B⊕C)⨂(D⊕E⊕F)\n",
    "def poly_otimes_poly(A,B):\n",
    "  res=[]\n",
    "  for i in A:\n",
    "    for j in B:\n",
    "      temp=np.zeros(2)\n",
    "      temp[0]=i[0]+j[0]\n",
    "      temp[1]=i[1]+j[1]\n",
    "      res.append(temp)\n",
    "  # print(res)\n",
    "  return mono_oplus(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "8e8cc139",
   "metadata": {},
   "outputs": [],
   "source": [
    "def pol_times_pol2(R,S):\n",
    "    d=len(R)-1\n",
    "    g=len(S)-1\n",
    "    res=OrderedDict()\n",
    "    for m in range(d+g+1):\n",
    "        res[m]=[]\n",
    "        for i in range(m+1):\n",
    "            if i<=d and m-i<=g:\n",
    "                res[m].append(R[i][0]+S[m-i][0])\n",
    "    pol_res=[]\n",
    "    for key,value in res.items():\n",
    "        pol_res.append([min(value),key])\n",
    "    return pol_res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "cae8ec49",
   "metadata": {},
   "outputs": [],
   "source": [
    "# pol_times1=[]\n",
    "# for i in range(100):\n",
    "#     start = time.time()\n",
    "#     poly_otimes_poly(X,Y)\n",
    "#     end = time.time()\n",
    "#     pol_times1.append(end - start)\n",
    "# print(\"running time1(pol times pol:\",np.average(pol_times1))\n",
    "\n",
    "# pol_times2=[]\n",
    "# for i in range(100):\n",
    "#     start = time.time()\n",
    "#     pol_times_pol2(X,Y)\n",
    "#     end = time.time()\n",
    "#     pol_times2.append(end-start)\n",
    "# print(\"running times2(poly times poly):\",np.average(pol_times2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a5525df",
   "metadata": {},
   "source": [
    "# Key Generation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "b3e3358e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def hashing_to_P(m,deg=150):\n",
    "  #hashing 512\n",
    "  hex_str=hashlib.sha512(m.encode()).hexdigest()#SHA-512 hash\n",
    "  hex_int=int(hex_str,16)#convert to decimal number\n",
    "  bin_str=format(hex_int,'b')#convert to binary number\n",
    "\n",
    "  #concatenate 3 copies of the bit string\n",
    "  B=\"\"\n",
    "  for i in range(3):\n",
    "    B=B+bin_str\n",
    "  #print(len(B)) #error check: bit string of len 1536\n",
    "\n",
    "  int7s=[]#convert each 7-bit block to an integer\n",
    "  for i in range(deg+1):\n",
    "    int7=B[(7*i):(7*i+7)]\n",
    "    int7s.append(int(int7,2))#convert to decimal\n",
    "  # print(min(int7s))\n",
    "  # #print(len(int7s))#we need 151 coefficients; additional one for constant\n",
    "\n",
    "  Ps=[]\n",
    "  for i in range(deg+1):\n",
    "    Ps.append([int7s[i],i])\n",
    "  # print(len(Ps))\n",
    "  return Ps"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fae91b83",
   "metadata": {},
   "source": [
    "# Scheme"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "e027cf32",
   "metadata": {},
   "outputs": [],
   "source": [
    "#two private polynomials\n",
    "X=one_v_poly(d,r)\n",
    "Y=one_v_poly(d,r)\n",
    "# print(X)\n",
    "# print(Y)\n",
    "\n",
    "#public\n",
    "M=pol_times_pol2(X,Y)\n",
    "\n",
    "#signing\n",
    "P=hashing_to_P(m,d)\n",
    "U=one_v_poly(d,r)\n",
    "V=one_v_poly(d,r)\n",
    "N=pol_times_pol2(U,V)\n",
    "sig_vec=[]\n",
    "sig_vec.append(pol_times_pol2(pol_times_pol2(P,X),U))\n",
    "sig_vec.append(pol_times_pol2(pol_times_pol2(P,Y),V))\n",
    "sig_vec.append(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "d1620358",
   "metadata": {},
   "outputs": [],
   "source": [
    "def pol_arr_tostring(A): \n",
    "    str_vec=[]\n",
    "    for i in A:\n",
    "        mo=[]\n",
    "        for j in i:\n",
    "            mo.append(str(j))\n",
    "        str_vec.append(\"_\".join(mo))\n",
    "    return \" \".join(str_vec)\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "957fb5fc",
   "metadata": {},
   "source": [
    "# verification"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "e98ce843",
   "metadata": {},
   "outputs": [],
   "source": [
    "#verification 1: check that the degree of the polynomial\n",
    "\n",
    "def deg_check_for_pol(A,deg,c):\n",
    "  d=OrderedDict()\n",
    "  for i in A: #go through all the monomials\n",
    "    if i[1] in d:#check whether degree can be found in the dict\n",
    "      d[i[1]].append(i)\n",
    "    else:\n",
    "      d[i[1]]=[i]\n",
    "  return c*deg in d\n",
    "\n",
    "#check neither polynomial in the signature pair is a constant multiple\n",
    "#(in the tropical sense) of P⨂M or P⨂N\n",
    "def constant_multiple_check(A,B):\n",
    "  if len(A)==len(B): #please make sure that A and B have the same deg before the check\n",
    "    coefs=np.zeros(len(A))\n",
    "    for i in range(len(A)):\n",
    "      coefs[i]=A[i][0]-B[i][0]#diff between coefficients for varying deg in A and B\n",
    "    return len(np.unique(coefs))==1\n",
    "  else:\n",
    "    print(\"tropical polys have diff degrees\")\n",
    "\n",
    "  \n",
    "def check_coef(A,d,r):\n",
    "  cnt=0\n",
    "  for i in A:\n",
    "    if i[0]>=0 and i[0]<=r*3:\n",
    "      cnt+=1\n",
    "  return cnt==3*d+1\n",
    "\n",
    "\n",
    "def check_coef2(A,d,r):\n",
    "    cnt=0\n",
    "    for i in A:\n",
    "        if i[0]>=0 and i[0]<=2*r:\n",
    "            cnt+=1\n",
    "    return cnt==(2*d+1)\n",
    "            \n",
    "def verification_all3():\n",
    "  if deg_check_for_pol(sig_vec[0],d,3) & deg_check_for_pol(sig_vec[1],d,3) & deg_check_for_pol(sig_vec[2],d,2) :\n",
    "    poly_toCheck1=pol_times_pol2(P,M)\n",
    "    poly_toCheck2=pol_times_pol2(P,N)\n",
    "    exp1=not (constant_multiple_check(sig_vec[0],poly_toCheck1))\n",
    "    exp2=not (constant_multiple_check(sig_vec[1],poly_toCheck1))\n",
    "    exp3=not (constant_multiple_check(sig_vec[0],poly_toCheck2))\n",
    "    exp4=not (constant_multiple_check(sig_vec[1],poly_toCheck2))\n",
    "    if exp1 & exp2 & exp3 & exp4:\n",
    "      if check_coef(sig_vec[0],d,r) & check_coef(sig_vec[1],d,r) & check_coef2(sig_vec[2],d,r):\n",
    "        W1=pol_times_pol2(pol_times_pol2(pol_times_pol2(P,X),U),pol_times_pol2(pol_times_pol2(P,Y),V))\n",
    "        W2=pol_times_pol2(pol_times_pol2(pol_times_pol2(P,P),M),N)\n",
    "        print(np.allclose(W1,W2))\n",
    "      else:\n",
    "        print(\"coefficient not within the range\")\n",
    "    else:\n",
    "      print(\"verification part2b failed\")\n",
    "  else:\n",
    "    print(\"verification part2a failed; signature not accepted\")\n",
    "\n",
    "verification_all3()"
   ]
  }
 ],
 "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}