*Location and Hours:*- Wolfson 130, Thursday 10:00 - 13:00
*Instructor:*- Nir Bitansky
*Reception Hours:*- Please coordinate by moc.liamg|yksnatibn#liame

## Overview

Cryptography is magical, it solves paradoxical problems such as communicating privately without ever meeting, proving you know a secret without revealing it, or computing over encrypted data. This magic is, in fact, based on a rigorous theory with beautiful definitions and proofs of security founded on computational complexity. The course will provide a graduate-level introduction to the theory of cryptography. We will cover foundational concepts, abstractions, and techniques, with the aim of giving students the basic tools needed to start research in the area. We will also sneak a peek into some advanced topics as time permits.

## Prerequisites

Basic probability theory, basic complexity (P, NP, BPP, NP-completeness). Prior informal-level knowledge of cryptography (such as the undergraduate course

0369.3049) is helpful but not required. Perhaps the most important prerequisite is mathematical maturity: The ability to read, understand, and write mathematical proofs. This is a graduate course. Undergraduate students are encouraged to take 0368.3049. In some special cases, however, undergraduates who receive personal permission of the instructor can take the course.

## Requirements

- Attendance (10%): this part is guaranteed as long as you miss at most 3 lectures (reasonable exceptions can be discussed with Nir).
- Homework assignments (60%): 5 problem sets.
- A final exam (30%).

## Tentative Syllabus

- Introduction
- Perfect secrecy and its limitations.

- Computational Hardness
- Computationally-bounded adversaries
- One-way functions
- Hardness amplification

- Indistinguishability and Pseudorandomness
- Computational indistinguishability
- Cryptographic pseudorandom generators and pseudorandom functions
- Multi-message encryption and authentication
- Hardcore bits and the Goldreich-Levin theorem

- Securing Communication
- Key exchange and public-key Encryption
- Digital signatures

- Zero Knowledge
- The Simulation Paradigm
- ZK proofs for NP
- Non-Interactive ZK

- Securing Computation
- Secure Multi-Party Computation: oblivious-transfer, Yao's garbled circuit
- Advanced topics (as time permits): CCA encryption, fully-homomorphic encryption, functional encryption, obfuscation, and verifying delegated computation

## Text Books

- J. Katz and Y. Lindell,
*Introduction to Modern Cryptography*, Chapman & Hall/CRC Press, 2007. - O. Goldreich,
*Foundations of Cryptography Volumes 1,2*, Cambridge University Press 2001,2004. Drafts available online. - D. Boneh and V. Shoup,
*A Graduate Course in Applied Cryptography*. Draft available online.

## Crypto Courses with Online Material

- Benny Applebaum and Iftach Haitner
- Boaz Barak
- Ran Canetti
- Benny Chor (The Undergraduate Course)
- Yevgeniy Dodis
- Rafael Pass and Abhi Shelat
- Gil Segev
- Salil Vadhan
- Daniel Wichs

## Lecture Notes

Will be posted online.