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 filereport.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)