Introduction to Cryptography

Computer Science 4830
Cornell University
Fall 2008


Instructor: Rafael Pass

Time: TR 1:25-2:40
Place: 306 Hollister Hall
Course Web page: http://www.cs.cornell.edu/courses/cs4830/2008fa/

 

TA: Muthu Venkitasubramaniam

Office Hours: Mon 1:00-2:00p
Place: 328 Upson Hall (Bay C)

Overview

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 undergraduate course we introduce some of the fundamental concepts of this study. Emphasis will be placed on rigorous proofs of security based on precise definitions and assumptions.

 

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.

Prerequisites

CS280 (or equivalent), CS381 (or mathematical maturity), or permission of instructor.

The main skills that will be assumed from these courses are: 1) the ability to understand and write formal mathematical definitions and proofs and 2) comfort with reasoning about algorithms, such as proving their correctness and analyzing their running times. It is also important that you are familiar with basic probability.

Course Administration

We 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 Com S 487 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. 

Grading

There will be 6 homeworks, an in-class mid-term and a take-home final exam.

�

HW 1 is due on Sep 9. Break this : cipher.txt

 

Dates for other HW (subject to change): HW2 on Sep 23, HW3 on Oct 7, HW4 on Oct 28, HW5 on Nov 11, HW6 on Nov 25.

 

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 midterm is in class on Oct 16.


Weights: homeworks 60%, mid-term 15% and final 25%.

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

Reading

Lecture notes will be made available on the web-site, but should not serve as a substitute for attending the lectures. In particular, lecture notes might sometimes be posted several days after the class.

 

Current draft of the lecture notes is here (updated on Nov 25)

 

There is no 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.

 

  • Jonathan Katz and Yehuda Lindell. An Introduction to Modern Cryptography. This is an introductory textbook on cryptography. The level of the material and the mathematical treatment is similar to the one we will use in class. However, this book does not cover all of the material that we go through.

 

  • Oded Goldreich. Foundations of Cryptography. This is a very comprehensive treatment of the theoretical foundations of cryptography. Volume I and II include most of the material that we cover in class, but at a far greater depth and at a more advanced level. This book is a great reference for students interested in more advanced studies in theoretical cryptography.

 

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)

  • Introduction:
    1. Introduction and Overview.
    2. Information Theoretic Security.
      Shannon’s Definition of security. One-time Pads. Limitations of the Information Theoretic Approach.

 

  • Computational Hardness and One-wayness:
    1. One-way Functions and Computationally bounded adversaries.
      Randomized Efficient Algorithms. One-way functions (OWF). Weak and Strong OWFs.
      Collections of OWFs.
    2. Computational Number Theory.
      Euclid’s Algorithm, Modular Exponentiation, Basic group theory, Euler’s and Fermat’s Theorems.
      Primes. Candidate OWFs based on the Factoring assumption and the Discrete log assumption.
      One way permutations and Trapdoor permutations.

 

  • Indistinguishability and Pseudorandomness:
    1. Computational Indistinguishability and Pseudorandom Generators (PRG) and Functions (PRF).
      Definitions of Computational Indistinguishability and Pseudorandomness.
      Provable constructions of a PRGs and PRFs.
      Practical constructions of PRG and PRFs: stream and block-ciphers.
    2. Private-Key Encryption.
      Definitions and Constructions
    3. Public-Key Encryption.
      Trap-door function model and problems with it.
      Definitions and Constructions.

 

  • Zero-Knowledge:
    1. Semantical Security:
      Zero knowledge-based definitions of encryption. Equivalence with indistinguishability-based definitions.
    2. Zero-Knowledge Proofs:
      Definitions and construction of ZK proofs for Graph-Isomorphism and Graph 3-coloring.

 

  • Authentication:
    1. Digital Signatures.
      Definitions and Constructions
    2. Hash functions.
    3. Message Authentication Codes.
    4. Zero Knowledge-based Authentication.

 

  • Composability:
    1. Composability of Encryption schemes.
      Chosen challenge-text, Chosen plain-text, Chosen cipher-text 1 and 2 (CCA1, CCA2).
      Malleability.
    2. Composability of Zero-Knowledge proofs.
  • Computing on Secret Inputs:
    1. Secret Sharing.
    2. Secure Computation.
      Oblivious Transfer.
      Yao’s Garbled Circuit.

Related Courses

  • 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 682: Theory of Computation. This course gives an advanced treatment of theory of computation, computational-complexity theory, and other topics in computing theory.
  • CS 687: Cryptography. This course is a more advanced graduate introductory course to cryptography.
  • CS 7832: Crypto breakfast. This course is a cryptography reading group focusing on advanced topics.