This course is a graduate introduction to cryptography. Topics include encryption, digital signatures, pseudo-random number generation, zero-knowledge and basic protocols. The emphasis will be on fundamental concepts and proof techniques.
Tu Th 2:55p-4:10p, 341 Statler Hall
Rafael : by appointment. Please email.
Muthu : by appointment. Please email Muthu.
- Homework 1 posted on webpage.
- Clarification in Question 4 (Homework 1) - Given a random message, ciphertext pair, the adversary can find ith bit for any i with probability 1/2+epsilon.
- Homework 1 has been corrected. Please download the new version if the version you have was obtained before Aug 25.
- There is a typo in the handout regarding the Chebyshev's inequality. Variance of X has been given as sigma, where it actually has to be sigma^2. This error has been corrected in the new handout.
- Lecture 1 notes have been posted online. See Preliminary Syllabus section.
- Homework 2 posten on CMS. (Due: Sep 21)
- Correction in Homework 2, problem 4 (a). The implications have to go the other way. Essentially, you have to show that a strong OWF is also a weak OWF and a weak OWF is also a worst-case OWF.
- Homework 2 is due on Tuesday 3rd October. There will be a problem solving session on Friday to help with Homework 2.
- There will be 6 homeworks in all.
CMS
We are using the course management system, CMS. Please login to
http://cms.csuglab.cornell.edu/ and check whether
you exist. There will be a list of courses you are registered for, and Com
S 687 should be one of them. If not, please send your full name and Cornell netid to
Muthu so he can register you.
You can check your grades and submit homework in CMS. There is a help page
with instructions.
There is no book that serves as the main text for this course. Scribe notes will be available online from the course webpage. Scribe notes can not be considered as substitute for class lectures. Supplementary reading can be made from the following sources.
Sources
- Oded Goldreich, Foundations of Cryptography: Basic Tools}, Cambridge University Press,New York, June 2001.
- Mihir Bellare and Shafi Goldwasser, Lecture Notes on Cryptography, August 2001.(An electronic copy of these lecture notes is available here )
The grade will be based on homework assignments, scribe and class
participation. You should expect roughly 8 problem sets during the
term.
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 a member of the course staff.
Assignments and solutions will be posted in CMS. Submit hardcopy in class or to Muthu by the due date, or a .pdf, .ps, .doc, or .txt file in CMS. Problem sets must be typed. Use of LaTeX is not required but LaTeX templates will be provided.
You will be required to scribe one or two lectures of the course.
General ease with algorithms and elementary probability theory, maturity with mathematical proofs (to be able to read and write mathematical proofs)
Please note that the scribe notes are only rough drafts of the lectures.
- Lecture 1: Introduction.
(Aug 24: Muthu)
- Lecture 2: Information Theoretic Security.
(Aug 29: Michael Clarkson)
Shannon Definition of security.
One-time Pads. Limitations of the Information Theoretic Approach.
- Lecture 3: One-way Functions and Computationally bounded adversaries.
(Aug 31: Lucja Kot)
Randomized Algorithms. Uniform/non-uniform algorithms.
One-way functions (OWF). Weak and Strong OWFs.
- Lecture 4: Hardness Amplification: From Weak to Strong OWFs.
(Sep 5: Jed Liu)
Collections of OWFs. A Universal OWF.
- Lecture 5: Computational Number Theory I.
(Sep 7: Michael George)
Primes, Factoring. Candidate OWF based on factoring. Collections of OWF.
- Lecture 6: Computational Number Theory II.
(Sep 12: Thanh Nguyen)
Properties of Zp*. Discrete log based one-way permutations. Quadratic residues in Zp*.
- Lecture 7: Computational Number Theory III.
(Sep 14: Hui jia Lin)
Properties of Zn*. Chinese Remainder Theorem. Quadratic residues in Zn*. RSA and Rabin OWF.
- Lecture 8: Computational Indistinguishability and Pseudorandom Generators (PRG).
(Sep 19: Wei-lung Tseng)
Computational Indistinguishability: Transitivity, product distributions.
Definition of Pseudorandomness in terms of Indistinguishability.
- Lecture 9: Unpredictability: An alternative definition of a pseudorandomness.
(Sep 21: Parvathinathan Venkitasubramaniam)
Equivalence of the two notions.
- Lecture 10: Hard-core predicates.
(Sep 26: Ariel Rabkin)
Construction of a PRG based on one-way permutations.
Improving the stretch of a PRG. Derandomization of BPP.
- Lecture 11: Every OWF has a hard-core bit.
(Sep 28: Krishnaprasad Vikram)
The Goldreich-Levin Theorem.
- Lecture 12: Pseudorandom Functions (PRF).
(Oct 3: Stephen Chong)
Definition and Construction. Applications to Learning Theory.
- Lecture 13: Private-Key Encryption.
(Oct 5: Ashwin Machanavajjhala)
Definitions. Semantic Security v.s. Indistinguishability.
Construction from PRF.
- Lecture 14: Many-message security.
(Oct 15: Tudor Marian)
Definitions. Semantic Security v.s. Indistinguishability.
Construction from PRF.
- Lecture 15: Stronger Attacks.
(Oct 17: Hui jia Lin)
Chosen challenge-text, Chosen plain-text, Chosen cipher-text 1 and 2 (CCA1, CCA2).
Malleability. CCA2 secure private-key encryption from a PRF.
- Lecture 16: Non-Malleability and Public-Key Encryption.
(Oct 19: Michael George)
Trap-door function model and Problems with it.
Indistinguishability and Semantic Security.
Impossibility of deterministic encryption.
- Lecture 17: Constructions of Public-Key Encryption.
(Oct 24: Muthu)
Goldwasser-Micali, Blum-Goldwasser.
- Lecture 18: Signatures and Authentication.
(Oct 26: Ashwin Machanavajjhala)
Construction of one-time signatures.
- Lecture 19: Digital Signatures.
(Oct 31: Tom Roeder)
- Lecture 20: Digital Signatures II.
(Nov 2: Tom Roeder)
Identity proving.
- Lecture 21: Zero Knowledge Proofs.
(Nov 7: Ariel Rabkin)
- Lecture 22: More ZK Protocols.
(Nov 9: Wei-lung Tseng)
- Lecture 23: More on ZK.
(Nov 21: Krishnaprasad Vikram)
- Lecture 24: Commitments and ZKPOK
(Nov 28: Tudor Marian)
- Lecture 25: Secure Computation.
(Nov 30: Michael Clarkson)