Description: CornellNYCTech-logo.jpg


Computer Science 5830
Cornell University
Fall 2013

Instructor: Rafael Pass

Time: T 10:10-12.55
Place: Big Red, Cornell Tech
Course Web page:


TA: Sidharth Telang

Office Hours: W 13:00 - 15:00

Homework 1 pdf

Gwriter files rar zip


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 precise definitions of security, precise assumptions and proofs of security.


Topics include: one-way functions, encryption, signatures, pseudo-random number generation, zero-knowledge and basic protocols.


Note: Although students will be expected to provide implementations of basic cryptographic primitives, this is largely 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.


Equivalent of CS2800 (Discrete Mathematics) and comfort with reasoning about algorithms, such as proving their correctness and analyzing their running times, or permission of instructor.

The main skill that will be assumed is the ability to understand and write formal mathematical definitions and proofs. It is also important that you are familiar with basic probability (although we will recall some basic concepts); please refresh yourself by reading Chapter 5 in the following lecture notes: [Pass-Tseng]

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 Com S 4830 should be one of them.  If not, please send your full name and Cornell netid to the TA so they can register you.  You can check your grades and submit homework in CMS. 


There will be 4 homeworks.

Dates for HW (subject to change): HW1 is due on Sep 17, HW2 on Oct 8, HW3 on Nov 5, HW4 on Nov 26.

Homeworks need to be handed in before the beginning of class. Additionally, you have a total of 4 “late-days” that you can use throughout the semester.

The following notation might be useful.


Homework Policy

You are free to collaborate with other students on the homework (in fact, I highly encourage you to work in pairs), 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 will be posted in CMS. Submit hardcopy in class or to the TA by the due date, or as a .pdf, .ps, .doc, or .txt file in CMS. Typed problem sets are strongly preferred.


We will largely follow the following lecture notes: [Pass-Shelat] (although some of the advanced proofs in these lecture notes will not be required for this course).


For additional background on probability theory, number theory and logic, please consult the following lecture notes on discrete mathematics: [Pass-Tseng]


There is no other required text for the course other than lecture notes. You may find the following two books to be useful references. Note, however, that we will not always be following the same notational conventions as these books.




For a more applied treatment of cryptography, I suggest the following book which is available on-line.



For background reading on probability, algorithms, and complexity theory, I recommend:


Topics Outline (subject to change)