# COS 533 - Advanced Cryptography (Fall 2017)

## Course Information

## Course Description

This course will cover a selection of advanced topics in cryptography, including some or all of the following:

- Lattice-based cryptography
- Elliptic curve-based cryptography
- Quantum Cryptography
- Cryptanalysis techniques
- Fully homomorphic encryption - Computing on encrypted data
- Zero knowledge proofs - Proving a theorem without revealing the proof
- Traitor tracing - Finding the source of leaked keys
- Identity-based encryption - Encryption where your public key is simply your email address
- Private information retrieval - Retrieving a database record without the database knowing which record
- Secret sharing - Splitting a secret into pieces so that only qualified sets of users can reconstruct the secret
- Multiparty computation - Several mutually distrusting users computing joint function over their private inputs

This course is intended to be a natural follow-up to COS 433. That said, I will try to make the course as self-contained as possible, and will try to cover any cryptographic background as needed (though topics covered in COS 433 will be given only basic treatment). If you are interested in taking this course, but have not previously taken COS 433 or equivalent, please contact me.

**Prerequisites:** Familiarity with computability and complexity theory, such as that covered in COS 340 (Turing Machines, P vs NP, NP-completeness, etc). Basic number theory (arithmetic modulo primes, composites). Familiarity with crypto concepts (one-way functions, encryption, digital signatures, public key vs secret key
cryptography, etc) is recommended, though not strictly required.

## Example Schedule (subject to change based on student interest)

Lecture | Topic | Scribe Notes |

1 - W, 9/13 | Course introduction, review of basic crypto concepts | [1] |

2 - M, 9/18 | Cryptography from one-way functions | [2] |

3 - W, 9/20 | Cryptography from one-way functions, cont. | [3] |

4 - M, 9/25 | Cryptography from one-way functions, cont. | [4] |

5 - W, 9/27 | Multiparty Computation | [5] |

6 - M, 10/2 | Multiparty Computation, cont. | [6] |

7 - W, 10/4 | Multiparty Computation, cont. | [7] |

8 - M, 10/9 | Zero Knowledge Proofs | [8] |

9 - W, 10/11 | Zero Knowledge Proofs, cont. | [9] |

10 - M, 10/16 | Elliptic curve cryptography | [10] |

11 - W, 10/18 | Elliptic curve cryptography, cont. | [11] |

12 - M, 10/23 | Elliptic curve cryptography, cont. | [12] |

13 - W, 10/25 | Bitcoin (Guest lecture by Arvind Narayanan) | |

M, 10/30 | No Class - Fall recess |

W, 11/1 |

14 - M, 11/6 | Elliptic curve cryptography, cont. | [14] |

15 - W, 11/8 | Lattice-based cryptography | [15] |

16 - M, 11/13 | Lattice-based cryptography, cont. | [16] |

17 - W, 11/15 | Lattice-based cryptography, cont. | [17] |

18 - M, 11/20 | Lattice-based cryptography, cont. | [18] |

W, 11/22 | No Class - Thanksgiving |

19 - M, 11/27 | Cryptanalysis | [19] |

20 - W, 11/29 | Cryptanalysis | [20] |

21 - M, 12/4 | Quantum cryptography | [21] |

22 - W, 12/6 | Quantum cryptography, cont. | [22] |

23 - M, 12/11 | Quantum cryptography, cont. | [23] |

24 - W, 12/13 | Quantum cryptography, cont. | [24] |

## Homework Assignments

Homework 0. Due September 18

Homework 1. Due October 11

Homework 2. Due October 27

Homework 3. Due December 6

Homework 4. Due January 16

**Instructions for Homeworks:** Please type up your solutions (LaTeX preferred). Either email your solutions to

(preferred) or print them out and hand them in during class by the due date.

## Templates for Scribe Notes

ln.tex
template.tex
**Latex source files for first two lectures**
ln1.tex
ln2.tex