CSE690 Fall 2007. Theory of Cryptography

Lecturer:	Rob Johnson
Location:	Old Chem 144
Time:	TuTh 11:20am-12:40pm
Office Hours:	Tu 1-2pm, 2313D Computer Science Building
Home page:	http://www.cs.sunysb.edu/~rob/teaching/cse690-fa07

News

The following links may be useful in developing a hash function for the class project:
- John Kelsey's Invited Talk, "How to Evaluate a Hash Proposal".
- Sponge Functions, Guido Bertoni, Joan Daemen, Michael Peeters and Gilles Van Assche. This talk proposes a new security model for hash functions.
- A critical look at cryptographic hash function literature, Scott Contini, Ron Steinfeld, Josef Pieprzyk and Krystian Matusiewicz. This great paper gives an overview of the security requirements of a hash function.
- VSH, an Efficient and Provable Collision Resistant Hash Function, Scott Contini and Arjen K. Lenstra and Ron Steinfeld. This is one way of constructing a "provably" secure hash function from number-theoretic assumptions.
- Efficient Collision Search Attacks on SHA-0, Xiaoyun Wang, Hongbo Yu, and Yiqun Lisa Yin. You can learn more details about attacks on traditional hash function designs in this paper.
- Some project ideas:
  - Make a more secure version of VSH.
  - Make an efficient hash function from a block cipher or some other primitive.
  - Make a hash function from a tweakable block cipher. See Tweakable Block Ciphers, Moses Liskov, Ronald L. Rivest, David Wagner.
HW3: Goldwasser & Bellare "Lecture Notes on Cryptography". Page 275, Problems E.4.1-E.4.4. Also, prove that if B is a hardcore bit for a OWF F, then G(x)=(F(x),B(x)) is a PRG.
HW2 is now available and due Oct. 29.
I have changed the grading policy to suit the class size. There will be no tests, more homeworks, and you can revise your homeworks as many times as you like.
The class will begin meeting in CS1211 on Sep. 27.
HW1 is now available and due Sept. 25.

Overview

This class will explore the theory and foundations of modern cryptography. The primary focus will be on provably secure constructions, although we may also study the art of designing cryptographic primitives if there is sufficient interest.

Topics

Basics of provable security: definitions of security, security reductions, one-way functions, trap-door one-way functions, pseudo-random functions, pseudo-random permutations
Constructions: encryption schemes, signature schemes, modes of operation, hash functions, MACs, zero-knowledge proofs, pseudo-random number generators, bit-commitment schemes
Public key primitives: modular arithmetic, RSA, El Gamal, discrete logs, elliptic curves, bilinear maps
Symmetric cryptographic primitives: Feistel networks, substitution-permutation networks, block ciphers, stream ciphers, AES, SHA-256
Cryptanalytic tools: linear, differential, and integral cryptanalysis, slide attacks, birthday problems
Cutting edge topics: identity-based crypto-systems, homomorphic encryption and signatures

Requirements and Grading

Subject to tweaks throughout the semester.

Homeworks (60%). I will assign 6-8 homeworks throughout the semester. You may revise your solutions as many times as you like based on my feedback. Thus it should be possible to have a perfect score on all the homeworks at the end of the semester.
Class Notes (20%). You should write notes for the class at least twice. Your notes can cover a class lecture or solutions for a homework or exam. You may collaborate with another student on a set of notes, although credit will be divided among the authors. You may also write extra class notes for extra credit with my approval.
Class project (20%). There are two project options for the class. We will develop candidate hash function designs for the NIST hash function standards competition. Class members will then attack each-others designs. Any proposals still left standing at the end of the semester will be considered for submission to the actual contest. More details to come. Alternatively, you may pursue any other project with my prior approval.

References

The course will largely follow Bellare and Rogaway's online course notes, Introduction to Modern Cryptography. You may also refer to Goldwasser and Bellare's Lecture Notes on Cryptography.

Lecture Schedule

Note: the schedule may change throughout the semester.
Warning: The notes below may contain errors. Use with caution.

Date	Topic/Recommended Reading
9/4	Crypto basics: history, goals, threat models, one-time pad and other foundations Notes, Kimberly Albrecht
9/6	Information-theoretic secrecy Notes, Kimberly Albrecht
9/11	Stream ciphers, computational indistinguishability, PRGs Notes, Kimberly Albrecht
9/18	Expanding PRGs, the GGM construction, PRFs Notes, Kimberly Albrecht
9/20	Stream ciphers, PRFs, PRF+PRG=PRF Notes, Kimberly Albrecht
9/25	Block ciphers, examples, PRF-PRP switching lemma Notes, Kimberly Albrecht
9/27	PRF-PRP switching lemma, DES, PRF->PRP (Luby-Rackoff) Notes, Kimberly Albrecht
10/2	Differential and Linear Cryptanalysis Notes, Kimberly Albrecht
10/4	Matsui's piling-up lemma, Real-or-random security, Modes of operation, ECB Mode, CTR mode Notes, Kimberly Albrecht
10/9	CTR mode, CBC mode Notes, Kimberly Albrecht
10/11	CBC mode, Left-or-Right Security, Semantic Security, IND-CPA Notes, Kimberly Albrecht
10/16	Semantic security, message integrity, MACs, PRFs are MACs
10/18	2-universal hashing, PRF+2-universal = PRF
10/23	GNMAC security (attempt 1), SHA-0 and attacks
10/25	SHA-0 and attacks (cont.), GNMAC security (attempt 2)
10/30	GNMAC security (cont.), HMAC, IND-CCA2

Note: If you have a physical, psychological, medical or learning disability that may impact on your ability to carry out assigned course work, please contact the staff in the Disabled Student Services office (DSS), Room 133, Humanities, 632-6748v/TDD. DSS will review your concerns and determine with you what accommodations are necessary and appropriate. All information and documentation of disability are confidential.

Note: Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Any suspected instance of academic dishonesty will be reported to the Academic Judiciary. For more comprehensive information on academic integrity, including categories of academic dishonesty, please refer to the academic judiciary website at http://www.stonybrook.edu/uaa/academicjudiciary/