Brief description of the course:

 

“It is possible to build a cabin with no foundations, but not a lasting building.”

 

           Eng. Isidor Goldreich (1906-1995)

 

 

Cryptography is concerned with the conceptualization, definition, and construction of computing systems that address security concerns. The design of cryptographic systems must be based on firm foundations. This course presents a rigorous and systematic treatment of foundational issues: defining cryptographic tasks and solving new cryptographic problems using existing tools.

 

The first part of the course focuses on the basic mathematical tools: computational difficulty (one-way functions), pseudo randomness, and zero-knowledge proofs. The emphasis is on the clarification of the fundamental concepts and on demonstrating the feasibility of solving cryptographic problems. This part is almost entirely based on the book titled "Foundations of Cryptography: Basic Tools" by Oded Goldreich.

 

In the second part of the course we will look at the basic applications (of the basic tools that we have developed so far) like encryption schemes, signature schemes and general cryptographic protocols. This part of the course will be based on the second volume, titled "Foundations of Cryptography: Basic Applications", of the same series on foundations of cryptography by Oded Goldreich.

 

There are no pre-requisites for the course and we will keep it as self contained as possible. However, basic familiarity with the design and analysis of the algorithms; some knowledge of complexity theory and probability is useful, although not required.

 

Details:

·        What: CS6285, Topics in Computer Science V1; title “Foundations of Cryptography”.

·        When: Every Tuesday, 2-4pm. First class on 13th January, 2009.

·        Where: COM1-212.

·        Books:

1.     “Foundations of Cryptography: Basic Tools”. (This is the Volume 1)

Author: Oded Goldreich. Publication: Cambridge University Press.Year 2001.

2.     "Foundations of Cryptography: Basic Applications". (This is the Volume 2)

Author: Oded Goldreich. Publication: Cambridge University Press.Year 2004.

·        Useful weblinks:

1.     http://www.wisdom.weizmann.ac.il/~oded/foc.html

 

2.     http://www.wisdom.weizmann.ac.il/~oded/foc-book.html

 

·        Office Hours: Every Thursday 2-3pm.

 

Course Outline:

Following is an outline, as suggested by Oded Goldreich, for a one-semester course on Foundations of Cryptography. We will try to follow this schedule. Each lecture below is meant to be of one hour and we will try to club 2 lectures in each two hour class. Lectures 1-15 are covered by Volume 1. Lectures 16-28 are covered by Volume 2.

 

Main: Definition (Sec. 2.2), Hard-Core Predicates (Sec. 2.5)
Optional: Weak implies Strong (Sec. 2.3), and Sec. 2.4.2-2.4.4

Main: Definitional issues and a construction (Sec. 3.2-3.4)
Optional: Pseudorandom Functions (Sec. 3.6)

Main: Some definitions and a construction (Sec. 4.2.1, 4.3.1, 4.4.1-4.4.3)
Optional: Sec. 4.2.2, 4.3.2, 4.3.3-4.3.4, 4.4.4

Definitions and a construction.

Definitions and a construction.

The definitional approach and a general construction (sketches).

 

Lecture notes:

 

Lecture 1

 

Lecture 2 

 

Lecture 3

 

Lecture 4

 

 

Assignments:

 

  1.

 Chapter 1 : 1,2,3,4,5

2.      

 Chapter 2: 1,2,6,7

3.      

 Chapter 2:  8,9,10,12,18

4.      

 Chapter 2: 21,25,27,28(1,2),30,31

  5.

 Chapter 3: 2,3,4,6,7,10,11

  6.

 Chapter 3: 13,14,17,19,20

  7.

 Chapter 4: 1, 5, 6, 8, 9, 10