Cornell University

Spring 2016

Instructor: Rafael Pass

Time: W
4.45-7.15

Place: Gates 405 (Ithaca), Touchdown (NYC)

Course Web page: http://www.cs.cornell.edu/courses/cs6830/2016sp/

Office
Hours: by appointment.

Course
Admin: Devaneke Crumpler
<dec89@cornell.edu>

The
modern study of cryptography investigates techniques for facilitating interactions
between distrustful entities. In our connected society, such techniques have
become indispensable---enabling, for instance, automated teller machines,
secure wireless networks, internet banking, satellite
radio/television and more.

In this
course we introduce some of the fundamental concepts of this study. Emphasis
will be placed on the foundations of cryptography and in particular on precise
definitions and proof techniques.

Topics
include: one-way functions, encryption, signatures, pseudo-random number
generation, zero-knowledge and basic protocols.

Note:
This will be a theory course. You will be expected to read and write formal
definitions and mathematical proofs. This is not a course in security: you will
not learn how to secure your system. Cryptography is only one (important) part
of security. We will not study cryptographic acronyms or all cryptographic
protocols in use today. Rather we focus on some of the fundamental design
paradigms and on notions that will allow you to critically evaluate
cryptographic protocols.

General ease with algorithms and elementary probability theory, maturity with mathematical proofs (to be able to read and write mathematical proofs)

We
are using the course management system, **CMS**.
Please login to http://cms.csuglab.cornell.edu/
and check whether you are registered. There will be a list of courses you are
registered for, and CS 6830 should be one of them. If not, please send
your full name and Cornell netid to the Devaneke so she can register you. You can check your
grades and submit homework in CMS.

There
will be roughly 4-5 homeworks. The grade will be based
on homework assignments and class participation.

You are free to collaborate with other students on the homework, but you must turn in your own individually written solution and you must specify the names of your collaborators. Additionally, you may make use of published material, provided that you acknowledge all sources used. Note that it is a violation of this policy to submit a problem solution that you are unable to explain orally to me. Typed problem sets are strongly preferred.

Homework 1 is due on Feb 3.

G-writer ciphertext are found here: zip

You will need the following notation and preliminaries.

Lecture
notes covering a large fraction of the course can be found here.

(Background
material on discrete math from CS 2800 can be found here.)

There
is no required textbook for the course. However, most of the topics we will
cover can be found in the following excellent reference.

- Oded Goldreich. Foundations of Cryptography. This is a very comprehensive treatment of the theoretical foundations of cryptography. Volume I contains most of the material we will cover in class. Other topics such as encryption, signatures and secure computation are in Volume II.

**Introduction:**- Introduction
and Overview.
- Information
Theoretic Security.

*Shannon’s Definition of security. One-time Pads. Limitations of the Information Theoretic Approach.*

** **

**Computational Hardness and One-wayness:**- One-way
Functions and Computationally bounded adversaries.

*Randomized Efficient Algorithms. One-way functions (OWF).*

Collections of OWFs. *Number Theory and Candidate One-way functions/permutations and trapdoor permutations.**Weak and Strong OWFs. Hardness Amplification.*

** **

**Indistinguishability****, Randomness and Pseudorandomness:**- Computational
Indistinguishability and Pseudorandom Generators
(PRG) and Functions (PRF).

*Definitions of Computational Indistinguishability and Pseudorandomness.*

*Hard-core
bits. Constructions of a PRGs and PRFs.*

- Hard-core
bits from any one-way function.

*The Goldreich-Levin Theorem.* - Imperfect
Randomness, and Hardness v.s. Randomness.

*Impossibility of deterministic extraction.*

Universal Hashfunctions and seeded extractors.

PRG and Derandomization of BPP. - Private-Key
Encryption.

*Definitions and Constructions* - Public-Key
Encryption.

*Definitions and Constructions.*

**Zero-Knowledge:**- Semantical Security:

*Zero
knowledge-based definitions of encryption. Equivalence with indistinguishability-based definitions.*

- Zero-Knowledge
Proofs:

*Definitions and construction of ZK proofs for Graph-Isomorphism and Graph 3-coloring.* - Witness
Indistinguishability

*Constant-round ZK.
*

**Applications:****Authentication:**- Digital
Signatures.

*Definitions and Constructions* - Hash functions.
- Message Authentication Codes.
- Zero
Knowledge-based Authentication
**.**

1.
**Computing on Secret Inputs:**

- Secret Sharing.
- Secure
Computation.

*Oblivious Transfer.*

General secure computation. - Fully Homomorphic Encryption.

2.
**Composability****:**

*1. *Composability of Encryption schemes.

*Chosen challenge-text, Chosen plain-text, Chosen cipher-text 1 and 2 (CCA1, CCA2).
Malleability. *

2. Composability of Zero-Knowledge proofs.

3.
**Program Obfuscation**

1. Impossibility of Virtual Black-box Obfuscation

2. Indistinguishability Obfuscation and Applications

4.
**Bitcoin****
and Proof-of-Work Based Ledgers**

1. Proofs of Work

2. The Blockchain protocol

- CS 513: System Security. This course discusses security and survivability for computers and communications networks. The course will include discussions of policy issues (e.g. the national debates on cryptography policy) as well as the discussions of the technical alternatives for implementing the properties that comprise "trustworthiness" in a computing system. Mechanisms for authorization and authentication as well as cryptographic protocols will be covered.
- CS 6810: Theory of Computation This course gives an advanced treatment of theory of computation, computational-complexity theory, and other topics in computing theory.
- CS 4830: Introduction Cryptography. This course is an undergraduate introductory course to cryptography.
- CS 7832: Crypto breakfast. This course is a cryptography reading group focusing on advanced topics.