Computer Science 6830
Instructor: Rafael Pass
Time: TR 1:25-2:40
Place: Snee Hall 1150
Course Web page: http://www.cs.cornell.edu/courses/cs6830/2009fa/
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 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
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
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 TA so he can register you. You can check
your grades and submit homework in CMS.
There will be roughly 4 homeworks (and potentially 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 Sep 10.
You will need the following notation and
Lecture notes covering most of the course can be found here (updated on Aug 27).
There is no required textbook for the course. However, most
of the topics we will cover can be found in the following excellent reference.
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.
Hardness and One-wayness:
- 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. Hardness
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
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 definitions.
- 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.
of Encryption schemes.
Chosen challenge-text, Chosen
plain-text, Chosen cipher-text 1 and 2 (CCA1, CCA2).
of Zero-Knowledge proofs.
Please note that scribe notes are only rough notes of the
lectures. Scribers please follow this template.
If you need help with LaTeX, here is a small tutorial file
and its source. Don’t forget to handin
your LaTeX source as well along with your scribe!
- Lecture 1: Introduction (Aug 27, Eleanor Birrell)
- Lecture 2: Information Theoretic Security (Sep 1, Stefano Ermon)
- Lecture 3: One-way Functions (Sep 3, Srivatsan Ravi)
- Lecture 4: More One-way Functions (Sep 8, Matthew Paff)
- Lecture 5: Universal One-way Functions and Computational Number Theory (Sep 10, Edward Lui)
- Lecture 6: Collections of One-Way Functions and Hard-Core Bits (Sep 15, Gabriel Bender)
- Lecture 7: Missing!
- Lecture 8: Computational Indistinguishability and Pseudorandomness (Sep 22, Chin Isradisaikul)
- Lecture 9: Pseudo-Random Generators (Sep 24, Matt Weinberg)
- Lecutre 10: PRG and Secure Encryption (Sep 29, Eleanor Birrell)
- Lecutre 11: Pseudo-Random Functions (Oct 1, Stefano Ermon)
- Lecutre 12: Definitions of Message Security (Oct 6, Gabriel Bender)
- Lecutre 13: CCA2-Secure Encryption and Public-Key Encryption (Oct 8, Edward Lui)
- Lecutre 14: Trapdoor Permutation (Oct 15, Srivatsan Ravi)
- Lecutre 15: Interactive Proofs (Oct 20, Chin Isradisaikul)
- Lecutre 16: Zero Knowledge (Oct 22, Matthew Paff)
- Lecutre 17: Zero Knowledge for NP (Oct 27, Eleanor Birrell)
- Lecutre 18: Zero Knowledge (Oct 29, Matt Weinberg)
- Lecutre 19: Witness-Hiding Protocols and MACs (Nov 3, Gabriel Bender)
- Lecutre 20: Signatures (Nov 10, Edward Lui)
- Lecutre 21: CRH and Signatures (Nov 12, Chin Isradisaikul)
- Lecutre 22: Secure Computation (Nov 17, Stefano Ermon)
- Lecutre 23: Oblivious Transfer (Nov 19, Srivatsan Ravi)
- Lecutre 23: Oblivious Transfer (Nov 19, Eleanor Birrell)
- Lecutre 24: Secure Computation and Yao’s garbled circuit (Nov 24, Matt Weinberg)
- 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
- CS 4830:
Introduction Cryptography. This course is an undergraduate
introductory course to cryptography.
7832: Crypto breakfast. This course is a cryptography reading group
focusing on advanced topics.