privacy-preserving-information-exchange.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Privacy-Preserving Information Exchange Using Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Imagine a scenario involving a vendor that offers two distinct digital products for sale at the same price (such as mobile apps or digital content) and a customer that would like to purchase exactly one of these two products. Furthermore, suppose that the customer and vendor are interested in performing this transaction in a way that preserves the privacy of the customer. To be more specific, whatever approach is used needs to satisfy the following two criteria:\n",
    "\n",
    "* the customer does not disclose to the vendor which of the two digital products they are purchasing , but\n",
    "* the vendor allows the customer to purchase exactly one of the two digital products.\n",
    "\n",
    "Is this even possible? One approach the vendor and customer can employ is to recruit a trusted third party. This third party can provide a kind of escrow service: retrieve a copy of each of the two products from the vendor and accept the selection from the customer, and then deliver to the customer only a copy of the selected product.\n",
    "\n",
    "This approach satisfies the two conditions, but it introduces a number of potential issues. Two of these include (1) the need to recruit (and potentially compensate) a third party and (2) the necessary disclosure of the customer's selection to the third party. The latter of these may be particularly problematic if the customer actually does not wish to disclose their selection to *any* third party (which just happens to include the vendor)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Exchanging Information via Oblivious Transfer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "In fact, it possible for the vendor and customer to perform this transaction while satisfying the original two conditions and *without* relying on a third party. Instead, the vendor and customer could each use a simple piece of software to communicate with one another via a cryptographic protocol known as *oblivious transfer*, or OT."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A technique first published in 1985 called [one-out-of-two oblivious transfer](http://www.lix.polytechnique.fr/~catuscia/teaching/papers_and_books/SigningContracts.pdf) is a form of secure computation that allows two parties to interact in exactly the way the vendor and customer in our scenario would like: a sender can deliver exactly one of two messages to a receiver without knowing which message it delivered. Since that time, generalized and streamlined variants of this technique have been developed, such as a [simple protocol](https://eprint.iacr.org/2017/370) published in 2015 by Genç, Iovino, and Rial."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Simple OT using Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The open-source [otc](https://pypi.org/project/otc/) Python library published by Nth Party provides an encapsulated implementation of the protocol published by Genç, Iovino, and Rial. How can the library be used to perform a privacy-preserving transaction that satisfies the original criteria?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The library lets programmers construct one of two objects: a sender object or a receiver object. In the transaction scenario, the vendor is the sender and the customer is the receiver. For the purposes of this example, the two products available for purchase are each a 16-byte string (this is not implausible in practice, as the two 16-byte strings could be cryptographic keys that can be used to decrypt larger files)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "At the beginning of a transaction, the vendor must create a sender object (assigned to the variable `s` in the example below) and send a public key `s.public` to the receiver. To learn more about why this is called a *public key* and how public keys are used in secure communication, you may want to delve deeper into the details of [public-key cryptography](https://en.wikipedia.org/wiki/Public-key_cryptography)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'\\x18\\x91\\xee\\xc9\\xe7|\\x81k\\xf5a\\xd2\\x9b\\xdbc\\x92\\xe9\\x8c\\xc4\\x1c)\\xb6u\\x90\\xb0\\xfc\\x91\\x04\\xc7\\x80\\xcd~z'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import otc\n",
    "s = otc.send()\n",
    "s.public # Public key to send to the receiver."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Once they receive the public key `s.public`, the customer can create a receiver object `r` and use it to build a query byte string (assigned to the variable `query` below) that effectively represents an encrypted request for one of the two items. In the example below, the receiver is requesting item `1` (the choices are `0` or `1`). Note that the sender *is not able to decrypt* this query and *cannot determine which item is being requested* by examining it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'z\\x01T\\xbc\\xa8\\r2\\xf0@v\\x16k\\xb7_\\x01\\x1a:\\xdd\\x8d\\xb2\\x8du1\\xee\\x99\\xd1\\xe0\\xd1|\\xe5\\xad\\x11'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import otc\n",
    "r = otc.receive()\n",
    "query = r.query(s.public, 1)\n",
    "query"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Once the sender receives the query byte string `query`, they can build a reply (assigned to the variable `replies` in the example below) consisting of a pair of byte strings. These two byte strings are the encrypted versions of the two products, but *only* the product originally selected by the receiver can be successfully decrypted. In the example below, the products offered by the vendor are two 16-letter words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(b'\\xd8\\xda\\xdf\\xf0\\x89JsJ\\xb5\\x9e0\\x0b\\xe8Kd\\xcf\\x1f\\x92\\xf2\\x18\\r\\xc6r\\xdc)\\x04\\xa0\\x990\\x93\\xc1f',\n",
       " b'\\xd0iy3\\xa2\\xb8\\xbf\\xefI\\x0eF\\xf9\\rI^\\xf9\\xaf\\x7fwO\\xbd\\x18\\x9cL\\x12\\xba>\\xd2V\\xed\\xec\\xb4')"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "replies = s.reply(\n",
    "    query,\n",
    "    'absentmindedness'.encode(),\n",
    "    'wholeheartedness'.encode()\n",
    ")\n",
    "replies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The receiver can now use the original receiver object `r` constructed at the beginning to obtain the product (which is selection `1` from the two choices `0` and `1`) to which they originally committed when they generated their query."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'wholeheartedness'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r.elect(s.public, 1, *replies).decode()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Note that reversing the two parts of the reply (in effect, attempting to decrypt the other product) will result in a decryption error."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Decryption failed. Ciphertext failed verification\n"
     ]
    }
   ],
   "source": [
    "try:\n",
    "    r.elect(s.public, 1, *reversed(replies)).decode()\n",
    "except Exception as e:\n",
    "    print(e)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Of course, having only two products that are each a 16-byte string is not a very realistic scenario. But these limitations can be overcome by creatively chaining multiple instances of the back-and-forth exchange presented in the example above. For now, we leave these generalizations of the approach as an exercise for the reader."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Implementation Details"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The [otc](https://pypi.org/project/otc/) library is an implementation of the [Genç, Iovino, and Rial protocol](https://eprint.iacr.org/2017/370) that relies on cryptographic primitives that consist of operations involving [elliptic curve](https://en.wikipedia.org/wiki/Elliptic-curve_cryptography) points and scalars. This OT library in turn leverages another library, [oblivious](https://pypi.org/project/oblivious/), that provides a single API that can seamlessly switch between [libsodium](https://libsodium.gitbook.io/doc/) and pure-Python implementations of the necessary primitives. This means the OT library can be used either in conjunction with a compiled instance of libsodium (yielding much better performance) or on its own (ensuring better portability at the expense of performance)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Practical Secure Computation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Hopefully, this article illustrates that incorporating cryptographic techniques like oblivious transfer into software applications that are implemented using contemporary, ubiquitous programming languages such as Python is becoming more practical. Visit the [Nth Party GitHub](https://github.com/nthparty) to find and/or contribute to [otc](https://github.com/nthparty/otc), [oblivious](https://github.com/nthparty/oblivious), and other libraries that you might find useful for your projects. And, of course, be sure to check back here in the future for more examples and tutorials like this one."
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3",
   "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}