Welcome! This mathematics, cryptography, and theoretical computer science course will aim to introduce the theory of succinct non-interactive arguments of knowledge (SNARKs), including necessary background in abstract algebra, cryptographic primitives, and verifiable computation. This topic has extensive applications in production software used in the developing cryptocurrency and decentralized finance industries, and during the course we will aim to develop the theory sufficiently to study and understand the mechanics of at least one currently deployed SNARK system. For details on grading, policies, and a tentative weekly schedule, please see the course syllabus.

**Instructor:** Bryan Gillespie, Bryan.Gillespie@colostate.edu

**Class time and location:** Tuesdays and Thursdays 8:00-9:15 am, C364 Clark Building

**Office Hours:** Tuesdays 9:30-10:30 am and Thursdays 11:30-12:30 am, 119 Weber Building

**Textbook:** Proofs, Arguments, and Zero-Knowledge by Justin Thaler

**Final project presentations:** Thursday, Dec. 15, 9:40-11:40 am, C364 Clark Building

Assignments will be posted here in PDF and LaTeX format throughout the course.

Week # | Topic | Due Date | TeX | |
---|---|---|---|---|

1 | Freivalds' Algorithm | Sep. 1 | TeX | |

2 | Rings, Ideals, and Polynomials | Sep. 8 | TeX | |

3 | Algebraic Field Extensions and Irreducible Polynomials | Sep. 15 | TeX | |

4 | Finite Fields | Sep. 22 | TeX | |

5 | Elliptic Curve Arithmetic and Bézout's Theorem | Sep. 29 | TeX | |

6 | Elliptic Curves Over Finite Fields and Discrete Logarithms | Oct. 6 | TeX | |

7 | Discrete Probability | Oct. 13 | TeX | |

8 | Schwartz-Zippel Lemma and Sum-check Protocol | Oct. 20 | TeX | |

9 | Arithmetization and Interpolation | Oct. 27 | TeX | |

10 | Zero-knowledge, Proofs of Knowledge, and Commitment Schemes | Nov. 3 | TeX | |

11 | Zero-knowledge 3-colorability Protocol, Merkle Trees | Nov. 10 | TeX | |

12 | KZG commitments, Circuit and R1CS Satisfiability | Nov. 17 | TeX | |

13 | Interactive Oracle Proofs, IOP for R1CS-Sat | Dec. 1 | TeX | |

14 | SNARKs | Dec. 8 | TeX |

Week # | Topic | |
---|---|---|

2 | Rings and Polynomials | |

3 | Algebraic Field Extensions | |

4 | Finite Fields | |

5 | Elliptic Curves | |

6 | Elliptic Curve Cryptography | |

7 | Probability and the Schwartz-Zippel Lemma | |

8 | Interactive Proofs and the Multivariate Sum Check Protocol |

Final projects will consist of a write-up and short presentation on a chosen topic. Presentations will take place during the scheduled final exam block during finals week, and write-ups are due at this time. The project description, rubric, and topic ideas can be found here.