Computer Science 6830
Instructor: Rafael Pass
Place: Thurston 220
Course Web page: http://www.cs.cornell.edu/courses/cs6830/2011fa/
Hours: by appointment.
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.
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.
include: one-way functions, encryption, signatures, pseudo-random number
generation, zero-knowledge and basic protocols.
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
ease with algorithms and elementary probability theory, maturity with
mathematical proofs (to be able to read and write mathematical proofs)
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 TA so he can register you. You
can check your grades and submit homework in CMS.
will be roughly 5 homeworks (and potentially a final project). The grade will
be based on homework assignments, scribe and class participation (and the final
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 6.
will need the following notation and preliminaries.
notes covering a large fraction of the course can be found here.
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
Definition of security. One-time Pads. Limitations of the Information
- Computational Hardness and
Functions and Computationally bounded adversaries.
Efficient Algorithms. One-way functions (OWF).
Collections of OWFs.
Theory and Candidate One-way functions/permutations and trapdoor
- Weak and
Strong OWFs. Hardness Amplification.
- Indistinguishability, Randomness and
Indistinguishability and Pseudorandom Generators (PRG) and Functions
of Computational Indistinguishability and Pseudorandomness.
Hard-core bits. Constructions of
a PRGs and PRFs.
bits from any one-way function.
Hard-core functions. The XOR
Randomness, and Hardness v.s. Randomness.
of deterministic extraction.
Universal Hashfunctions and seeded extractors.
PRG and Derandomization of BPP.
Zero knowledge-based definitions
of encryption. Equivalence with indistinguishability-based definitions.
and construction of ZK proofs for Graph-Isomorphism and Graph 3-coloring.
Computing on Secret Inputs:
General secure computation.
of Encryption schemes.
challenge-text, Chosen plain-text, Chosen cipher-text 1 and 2 (CCA1, CCA2).
of Zero-Knowledge proofs.
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 hand in your LaTeX
source as well along with your scribe!
- Lecture 1: Introduction (Aug 25)
- Lecture 2: Perfect Secrecy (Aug 30, Sidharth Telang)
- Lecture 3: One-Way Functions (Sep 1, Costandino Dufort Moriates)
- Lecture 4: Hardness Amplification Theorem (Sep 6, Sujay Jayakar)
- Lecture 5: Levin's OWF and Multiplication (Sep 8, Shyam Lenna)
- Lecture 6: OWFs and Hard-Core Bits (Sep 13, David Goff)
- Lecture 7: Hard-Core Bits from any OWF (Sep 15, Remus Radu)
- Lecture 8: Computational Indistinguishability (Sep 22, Nick Alessi)
- Lecture 9: Indistinguishability and Pseudorandomness (Sep 27, Anthony Chang)
- Lecture 10: Pseudorandom Generators (Sep 29, Karn Seth)
- Lecture 11: Probabilistic Random Functions (Oct 4, Shentong Wang)
- Lecture 12: Missing (Oct 6, ???)
- Lecture 13: Multi-Message Security (Oct 18, Shyam Lenna)
- Lecture 14: Public Key Encryption (Oct 20, Nick Alessi)
- Lecture 15: PKE and Zero Knowledge (Oct 27, Sujay Jayakar)
- Lecture 16: Zero Knowledge Proofs - Part 1 (Nov 1, Lior Seeman)
- Lecture 17: Zero Knowledge Proofs - Part 2 (Nov 3, Remus Radu)
- Lecture 18: Zero Knowledge Proofs - Part 3 (Nov 8, Karn Seth)
- Lecture 19: Zero Knowledge Proofs - Part 4 (Nov 10, Shentong Wang)
- Lecture 20: Authentication (Nov 15, Sidharth Telang)
- Lecture 21: Authentication - Part 2 (Nov 17, Shentong Wang)
- Lecture 22: Secure Computation (Nov 22, Sujay Jayakar)
- 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
- 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.