ECE598DA Topics in Information-Theoretic Cryptography

Description

In this course, we will study foundational and recent work on the use of information theory to design and analyze cryptographic protocols. We will begin by studying privacy attacks which motivate strong privacy and security definitions. Then, we will explore the basics of differential privacy and study some core works on zero-knowledge proofs. Finally, we will explore various applications, including watermarking of generative models and basic quantum cryptography protocols.

Meeting Times/Days

1hr 20 mins (9:30AM - 10:50AM) on Tuesdays and Thursdays

Location

Room 2015 in the Electrical & Computer Engineering Building

Instructor

Daniel Alabi

Office Hours: 11AM-12PM on Tuesdays (CSL 118) and by appointment

Prerequisites

• At least one of:
  • ECE 313/MATH 362: Probability with Engineering Applications
  • MATH 461: Probability Theory
• ECE/CS 374: Introduction to Algorithms and Models of Computation

Prerequisite overrides will be considered by the instructor on a case-by-case basis.

Recommended Textbooks

• Introduction to Cryptography with Coding Theory. By Wade Trappe, Lawrence C. Washington.

• Tutorials on the Foundations of Cryptography. Edited by Yehuda Lindell.

Schedule

Week 1: Introduction: motivations, one-time pad review, talking drums, probability theory review

Readings:

• Chapter 1 of The Information by James Gleick
• Chapters 1-3 of Introduction to Probability Models by Sheldon Ross

Exercises for Week 1

Week 2: Attacks on Privacy, Security, Valuation

Readings:

• Chapter 1, Chapter 2, Chapter 4 of Trappe-Washington
• Dinur-Nissim attack

Exercises for Week 2

Week 3: Standard Mechanisms for Differential Privacy and Composition

Readings:

• Chapters 1 and 2 of Vadhan

Exercises for Week 3

Week 4: Information-Theoretic Lower Bounds for Differential Privacy

Readings:

• Chapter 5 of Vadhan

Exercises for Week 4

Week 5: Differentially Private Statistical Estimation, Machine Learning, and Testing

Readings:

• Abadi et al.
• Gaboardi et al.
• McSherry-Talwar

Exercises for Week 5

Week 6: Privacy for Distributed Computing

Readings:

• Warner
• Kairouz et al.

Exercises for Week 6

Week 7: Zero-Knowledge Proofs

Readings:

• Goldwasser-Micali-Rackoff’89
• Goldreich-Micali-Wigderson’86

Exercises for Week 7

Week 8: Statistical Zero-Knowledge Proofs

Readings:

• Complete Problem for SZK
• Statistical Difference Beyond the Polarizing Regime

Exercises for Week 8

Week 9: Statistical Zero-Knowledge Proofs with Multiple Verifiers

Readings:

• PRIO: paper, application
• Secret Sharing: Chapter 10 of Trappe-Washington

Exercises for Week 9

Week 10: Fully Linear PCPs and Arithmetic Sketching

Readings:

• Fully Linear PCPs
• Arithmetic Sketching
• PINE: paper, IETF

Week 11: Multi-Party and Computational Differential Privacy

Readings:

• Chapter 9 and Chapter 10 of Vadhan

Week 12: Quantum Cryptography

Readings:

• Chapter 17 of Trappe-Washington
• Quantum SZK

Week 13: Watermarking and Information Hiding

Readings:

• Moulin and O’Sullivan
• He et al.
• Dathathri et al.

Week 14: Fall Break

Week 15: Project Presentations

Week 16: Project Presentations and Quiz

Grading Policy

Class Participation (30%)

• Attendance is mandatory for all lectures, with a maximum of three unexcused absences allowed.
• Each student must (co)scribe at least one lecture during the course.
• Students must attend final project presentations.

Exercises (0%)

• There will be weekly (optional) exercises/homework.
• These exercises will not be graded but you can ask the instructor for the solutions.
• The goal is to help you prepare for the quiz and to reinforce your understanding of the material.

Quiz (10%)

• There will be 1 (in-class) short quiz to gauge students’ understanding of the fundamentals.
• The quiz will take place towards the end of the semester (December 9).

Project (60%)

Students will work on projects related to one or more of the covered topics. The project is divided into four components:

• Proposal: 15% (October 2)
• Mid-term report: 15% (October 17)
• Final presentation: 15% (December 1-9)
• Final report: 15% (Dececember 18)