## 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:
• 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

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