Cryptography meets algorithms (15893)
Special topics: Cryptography meets algorithms (15893) Spring 2024

Instructor: Elaine Shi

Monday/Wednesday 9:30am - 10:50am

GHC 4303 + Zoom

Course Description

In this course, we will learn a few selected interesting topics in cryptography:

  1. Private Information Retrieval (PIR): PIR allows a client to privately read a public database without the server learning the actual query made by the client. We will cover a few classical constructions of PIR (information-theoretic, computational) and some new constructions in the preprocessing model.

  2. Oblivious RAM (ORAM): ORAM allows a client to safely delegate storage to a server and then read/write the storage without the server learning the access pattern. We will cover generic constructions (PathORAM, Hierarchical ORAM and OptORAMa), some specific oblivious data structures/algorithms, lower bounds on oblivious algorithm and some applicaions of ORAM.

  3. Zero Knowledge Proofs (ZKP): ZKP allows a prover to prove a statement to a verifier, while the verifier only learns the trueness of the statement and nothing else. We will cover how to construct ZKP for special statements, and then generic constructions.

(The content is subject to change.)

Students are required to (1) work on scribe notes; (2) read and present relevant papers; (3) explore relevant research topics.

Prerequisites:

  • Comfortable with writing formal mathematical proofs.

  • Familiar with probabilities.

  • Solid background of algorithms.

  • At least undergrad-level cryptography course. (Or a solid background on randomized algorithms)

Course Staff

Instructor: Elaine Shi (rshi@andrew.cmu.edu)

TA: Mingxun Zhou (mingxunz@andrew.cmu.edu)

When sending an email to the Instructor/TA, start with "15893: " in the email title.

Attendance Options

We require in-person attendance. There'll be 10% of participation grade for in-person attendance and attending 80% of the lectures will get you a full score. If you can't attend the lecture in person, you can choose one of the following options:
  • You can attend the lecture synchronously via Zoom.
  • You can also watch the recorded lecture videos asynchronously on Panopto.
Please email the TA if you can't attend the lecture in person, otherwise points may be deducted.

Helpful Materials