image001.gif                     Description: Description: CornellNYCTech-logo.jpg


Computer Science 6830
Cornell University
Spring 2017

Instructor: Rafael Pass

Time: W 4.45-7.15
Place: Gates 405 (Ithaca), Touchdown (NYC)
Course Web page:


Office Hours: by appointment.

Course Admin: Vasilis Drimalitis <>




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)


Course Administration


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 Vasilis so he 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.


Homework Policy


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 8.

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.



Topics Outline (subject to change)




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


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

Constant-round ZK.

1.     Computing on Secret Inputs:

2.     Composability:

1.     Composability of Encryption schemes.
Chosen challenge-text, Chosen plain-text, Chosen cipher-text 1 and 2 (CCA1, CCA2).

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



Related Courses