Cryptography

Computer Science 687
Cornell University
Spring 2008


Instructor: Rafael Pass

Time: TR 2:55-4:10
Place: UP111
Course Web page: http://www.cs.cornell.edu/courses/cs687/2008sp/

 

Office Hours: by appointment.

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

Prerequisites

General ease with algorithms and elementary probability theory, maturity with mathematical proofs (to be able to read and write mathematical proofs)

Grading

There will be roughly 3-4 homeworks and a final project. The grade will be based on homework assignments, scribe and class participation and the final project.

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

You will need the following notation and preliminaries.

Reading  

There is no required text for the course other than lectures. Most of the topics we will cover can be found in the following excellent reference.

 

  • Oded Goldreich. Foundations 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 to change)

  • Introduction: [Lecture Notes]
    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: [Lecture Notes]
    1. One-way Functions and Computationally bounded adversaries.
      Randomized Efficient Algorithms. One-way functions (OWF).
      Collections of OWFs.
    2. Number Theory and Candidate One-way functions/permutations and trapdoor permutations.
    3. Weak and Strong OWFs. Hardness Amplification.

 

  • Indistinguishability, Randomness and Pseudorandomness: [Lecture Notes]
    1. Computational Indistinguishability and Pseudorandom Generators (PRG) and Functions (PRF).
      Definitions of Computational Indistinguishability and Pseudorandomness.

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

    1. Hard-core bits from any one-way function.
      The Goldreich-Levin Theorem.

Hard-core functions. The XOR Lemma.

    1. Imperfect Randomness, and Hardness v.s. Randomness.
      Impossibility of deterministic extraction.
      Universal Hashfunctions and seeded extractors.
      PRG and Derandomization of BPP.
    2. Private-Key Encryption.
      Definitions and Constructions
    3. Public-Key Encryption.
      Definitions and Constructions.

 

  • Zero-Knowledge:
    1. Semantical Security:

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

    1. Zero-Knowledge Proofs:
      Definitions and construction of ZK proofs for Graph-Isomorphism and Graph 3-coloring.
    2. Witness Indistinguishability

Constant-round ZK.

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

1.        Computing on Secret Inputs:

      1. Secret Sharing.
      2. Secure Computation.
        Oblivious Transfer.
        General secure computation.         

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

Scribe notes:

  • Lecture 1 : Intro
  • Lecture 2 : Shannon Security
  • Lecture 3 : Weak and Strong One-way Functions
  • Lecture 4 : Hardness Amplification
  • Lecture 5 : Universal OWF, Primes and Factoring
  • Lecture 6 : Goldreich-Levin Theorem
  • Lecture 7 : Computational Indistinguishability, Hybrid Lemma, PRG
  • Lecture 8 : Next-bit test and construction of a PRG
  • Lecture 9 : Expansion of PRG
  • Lecture 10 : Secret-key Encryption
  • Lecture 11 : Pseudorandom functions
  • Lecture 12 : Multi-message secure Encryption, CPA/CCA security
  • Lecture 13 : Construction of CCA-secure Encryption, Definition of Public-Key Encryption
  • Lecture 14 : Construction of Public-Key Encryption, Negative Results for Learning
  • Lecture 15 : Imperfect Randomness, Extractors

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 487: Introduction Cryptography. This course is an undergraduate introductory course to cryptography.