Computer Science 687
Instructor: Rafael Pass
Time: TR 2:55-4:10
Course Web page: http://www.cs.cornell.edu/courses/cs687/2008sp/
Office Hours: by appointment.
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
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)
There will be roughly 3-4 homeworks
and a final project. The grade will be based on homework assignments, scribe
and class participation and the final project.
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 5.
You will need the following notation and
There is no required text for the course other than lectures.
Most of the topics we will cover can be found in the following excellent
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.
Topics Outline (subject to change)
- Introduction and Overview.
- Information Theoretic Security.
Shannon’s Definition of security.
One-time Pads. Limitations of the Information Theoretic Approach.
- One-way Functions and Computationally
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.
- Indistinguishability, Randomness and Pseudorandomness: [Lecture Notes]
- Computational Indistinguishability
and Pseudorandom Generators (PRG) and Functions (PRF).
Definitions of Computational Indistinguishability and Pseudorandomness.
Hard-core bits. Constructions of a PRGs and PRFs.
bits from any one-way function.
The Goldreich-Levin Theorem.
Hard-core functions. The XOR Lemma.
Randomness, and Hardness v.s. Randomness.
Impossibility of deterministic
Universal Hashfunctions and seeded extractors.
PRG and Derandomization of BPP.
- Private-Key Encryption.
Definitions and Constructions
- Public-Key Encryption.
Definitions and Constructions.
- Semantical Security:
Zero knowledge-based definitions of
encryption. Equivalence with indistinguishability-based
- Zero-Knowledge Proofs:
Definitions and construction of ZK
proofs for Graph-Isomorphism and Graph 3-coloring.
- Digital Signatures.
- Hash functions.
- Message Authentication Codes.
- Zero Knowledge-based Authentication.
Computing on Secret Inputs:
- Secret Sharing.
- Secure Computation.
General secure computation.
Chosen challenge-text, Chosen
plain-text, Chosen cipher-text 1 and 2 (CCA1, CCA2).
1 : Intro
- Lecture 2 : Shannon
- Lecture 3 : Weak and Strong One-way Functions
- Lecture 4 : Hardness Amplification
5 : Universal OWF, Primes and Factoring
6 : Goldreich-Levin Theorem
7 : Computational Indistinguishability, Hybrid
- Lecture 8 : Next-bit test and
construction of a PRG
9 : Expansion of PRG
10 : Secret-key Encryption
- Lecture 11 : Pseudorandom functions
12 : Multi-message secure Encryption, CPA/CCA security
13 : Construction of CCA-secure Encryption, Definition of Public-Key
14 : Construction of Public-Key Encryption, Negative Results for Learning
15 : Imperfect Randomness, Extractors
- 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 682: Theory of
Computation This course gives an advanced treatment of theory of
computation, computational-complexity theory, and other topics in
- CS 487: Introduction
Cryptography. This course is an undergraduate introductory course to