homework/CS3990_HW_9.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CS 3990/5990: Secure Distributed Computation\n",
    "## Homework 9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "import hashlib"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Petersen Graph\n",
    "\n",
    "[The Petersen Graph](https://en.wikipedia.org/wiki/Petersen_graph) has 10 vertices and 15 edges, and can be colored with 3 colors.\n",
    "\n",
    "![alt text](https://upload.wikimedia.org/wikipedia/commons/thumb/9/90/Petersen_graph_3-coloring.svg/220px-Petersen_graph_3-coloring.svg.png \"Title\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "coloring = {\n",
    "    # outer five nodes, clockwise from top\n",
    "    0: 'red',\n",
    "    1: 'blue', \n",
    "    2: 'green',\n",
    "    3: 'red',\n",
    "    4: 'blue',\n",
    "    # inner five nodes, clockwise from top\n",
    "    5: 'blue',\n",
    "    6: 'red',\n",
    "    7: 'red',\n",
    "    8: 'green',\n",
    "    9: 'green'\n",
    "}\n",
    "print('Number of nodes:', len(coloring))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "edges = [\n",
    "    # outer shape, clockwise from top\n",
    "    (0, 1),\n",
    "    (1, 2),\n",
    "    (2, 3),\n",
    "    (3, 4),\n",
    "    (4, 0),\n",
    "    # inner shape, clockwise from top\n",
    "    (5, 0), (5, 7),\n",
    "    (6, 1), (6, 8),\n",
    "    (7, 2), (7, 9),\n",
    "    (8, 3), (8, 5),\n",
    "    (9, 4), (9, 6)\n",
    "]\n",
    "print('Number of edges:', len(edges))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Background\n",
    "\n",
    "**Your goal in this assignment** is to implement a zero-knowledge interactive proof protocol that allows the Prover to convince the Verifier that the Prover knows a valid 3-coloring for the Petersen graph - without revealing the coloring.\n",
    "\n",
    "Reference the description in lecture, the exercise, and [Matt Green's blog post](https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Protocol\n",
    "\n",
    "The Prover and Verifier perform the following steps $n^2$ times, where $n$ is the number of vertices in the graph:\n",
    "\n",
    "- **Step 1: shuffle and commit.** The Prover randomizes the colors and commits to the coloring. The Prover sends the commitment to the Verifier.\n",
    "- **Step 2: challenge.** The Verifier picks a random edge in the graph.\n",
    "- **Step 3: response.** The Prover opens the commitment for the two vertices connected by the chosen edge. If the two colors are the same, the Verifier rejects."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 1 (40 points)\n",
    "\n",
    "Implement the above protocol for an interactive zero-knowledge proof of the graph coloring."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "7308a3ee793a7fc944e06c5a0a4c65fc",
     "grade": true,
     "grade_id": "cell-cc0016e6effbce3a",
     "locked": false,
     "points": 40,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "class Prover:\n",
    "    def shuffle_and_commit(self, V):\n",
    "        # YOUR CODE HERE\n",
    "        raise NotImplementedError()\n",
    "\n",
    "        # send the commitment to the Verifier\n",
    "        V.receive_commitment(commitment)\n",
    "    \n",
    "    def response(self, edge, V):\n",
    "        # YOUR CODE HERE\n",
    "        raise NotImplementedError()\n",
    "        \n",
    "        # ask the verifier to check the response\n",
    "        V.check(c1, c2)\n",
    "\n",
    "class Verifier:\n",
    "    def receive_commitment(self, commitment):\n",
    "        # save the commitment for later\n",
    "        self.commitment = commitment\n",
    "    \n",
    "    def challenge(self, P):\n",
    "        # YOUR CODE HERE\n",
    "        raise NotImplementedError()\n",
    "\n",
    "        P.response(edge, self)\n",
    "\n",
    "    def check(self, color1, color2):\n",
    "        # YOUR CODE HERE\n",
    "        raise NotImplementedError()\n",
    "\n",
    "def run_protocol():\n",
    "    P = Prover()\n",
    "    V = Verifier()\n",
    "    for _ in range(15**2):\n",
    "        P.shuffle_and_commit(V)\n",
    "        V.challenge(P)\n",
    "    \n",
    "run_protocol()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 2 (10 points)\n",
    "\n",
    "In 2-5 sentences, argue that the protocol is zero-knowledge (it doesn't reveal anything about the witness)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "35cf9235354f6f3da043172fdbdfce6c",
     "grade": true,
     "grade_id": "cell-0efb4dc3f756e047",
     "locked": false,
     "points": 10,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 3 (10 points)\n",
    "\n",
    "What is the probability that a cheating Prover is *not* caught in this protocol, and why?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "166ca03fc75d6f0ce8d5b152cbe6fee3",
     "grade": true,
     "grade_id": "cell-b935648579557ab4",
     "locked": false,
     "points": 10,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  }
 ],
 "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.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}