README.md



Machine Problem 1: Zero Knowledge Proofs
This is the first machine problem for ECE/CS498AC Applied
Cryptography at
the University of Illinois at Urbana-Champaign.
In this assignment you will need to implement several zero-knowledge proof
schemes for languages involving discrete logarithms. This assignment is intended
to provide:

A hands-on way to understand group theory
Practice implementing variations of a cryptographic protocol
Reinforcement of the concepts behind analyzing a protocol with "security
proofs" (You will have to implement in code the "Simulator" and the "Extractor"
that make up part of the proof.)


Getting started
This assignment uses a specific commonly used cryptographic group, secp256k1
(found in Bitcoin, for example). The implementation of secp256k1 used here is
due to Jeremy Kun, who has a fantastic series of
blogposts
explaining modular arithmetic, finite fields, and elliptic curves. His
implementation is included as a submodule, which can be cloned by running the
following commands:
git submodule init
git submodule update
The python files in this assignment can be converted to .ipynb using the tool
py2nb.

Assignment
The expression ZkPoK { (x): X = g^X } in Camenisch-Stadler notation means a
proof that you know a secret witness x such that X = g^x, where X is a
publicly known value (called the statement) and g is a generator of a large
cyclic group.
In class, we've discussed the Schnorr protocol for creating interactive proofs
for this language, as well as "Sigma Protocol" variants for other language
(arithmetic constraints, "OR" proofs, etc.), and how to make such protocols
non-interactive using a random oracle (the Fiat-Shamir trick).
The assignment provides an example implementation of the basic scheme. It also
provides skeleton code for incrementally more complicated variations (roughly
following the lectures), and a few simple test cases for each. The skeleton code
( zkp-assignment.py/ ) includes regions clearly marked #TODO that you must
fill out to complete the assignment. The number of points associated with each
portion is given in the file.

Submitting your solution
To submit your solution:

The due date is (SEE THE COURSE WEBSITE)
You must upload your mp1 folder as a zip file to Piazza
The upload must be marked "visible to Instructors"
The mp1 folder must contain a text file report.txt, which must include a short english-language narrative explaining:

Your net id
What parts you finished, attempted, couldn't figure out
Any parts you found interesting, challenging, questions you have
Length can be one paragraph, or several... this is not an essay, but it may be used to justify partial credit


No partners are allowed for this machine problem. You must do your own work on this MP.
Only modify the zkp-assignment.py file, since that is the only code we'll check
The file must run without throwing exceptions
You'll get points for every one of the included tests that passes (though the tests in the file are not comprehensive)