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

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

·
When: Every Tuesday, 2-4pm. First class on 13^{th}
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.

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.

- Lecture 1: Introduction, Background, etc.

- Lecture 2-5: Computational Difficulty (One-Way Functions)

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

- Lecture 6-10: Pseudorandom Generators

Main: Definitional issues and a construction (Sec. 3.2-3.4)

Optional: Pseudorandom Functions (Sec. 3.6)

- Lecture 11-15: Zero-Knowledge Proofs

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

- Lecture 16-20: Encryption Schemes

Definitions and a construction.

- Lecture 21-24: Signature Schemes

Definitions and a construction.

- Lecture 25-28: General Cryptographic Protocols

The definitional approach and a general construction (sketches).

Lecture notes:

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 |