Cryptology I

Lecture spring 2013

Instructor Dominique Unruh <<surname> at ut dot ee>
Teaching assistant
Prastudy Fauzi <<givenname> at ut dot ee>
Lecture Period February 12, 2013 - May 28, 2013 (weeks 24-39)
Lectures Tuesdays 12:15-13:45 (Unruh; may sometimes be switched with tutorial)
Practice sessions
Tuesdays 14:15-15:45 (Unruh)
Course Material Lecture notes, blackboard photos (of practice), and exam study guide.
Language English
Exam May 29,  9:30-12:30, room 224
Contact Dominique Unruh <<surname> at ut dot ee>

News

Topics covered

2013-02-12 (lecture) General introduction to cryptography. Classical ciphers.
2013-02-19 (lecture) Perfect secrecy. One time pad. Limitations of these.
2013-02-19 (practice) Breaking a subsitution cipher. "Two time pad" security. Exploiting malleability.
2013-02-26 (lecture) Stream ciphers. IND-OT-CPA. How security proofs work.
2013-02-26 (practice) Defining "random looking ciphertexts". Proof "random looking ciphertexts" implies IND-OT-CPA.
2013-03-12 (lecture) Block ciphers. Feistel networks. DES. 2DES. Meet in the middle. 3DES.
2013-03-12 (practice) Breaking 1-round and 2-round Feistel nets. Meet-in-the-middle attack on 4DES.
2013-03-19 (lecture) Security of block ciphers. Provable security vs. best-effort design. Strong PRP. IND-CPA. Modes of operation: ECB, CBC.
2013-03-19 (practice) Modes of operation for authenticated encryption ("crypto competition").
2013-03-26 (lecture) Public key encryption. Textbook RSA. RSA assumption. ElGamal.
2013-03-26 (practice) Breaking insecure mod-p ElGamal.
2013-04-02 (lecture) Security of ElGamal. DDH-assumption. IND-CPA (public key variant). Malleability of ElGamal (auction example & chosen ciphertext attack). IND-CCA. RSA-OAEP. Hybrid encryption.
2013-04-02 (practice) Constructing non-malleable encryption schemes for longer messages ("crypto competition")
2013-04-09 (lecture) MACs. Hash functions. Iterated hash + attack. Merkle-Damgard. Insecurity of MD as MAC. HMAC
2013-04-09 (practice) MD5 with length in the beginning -> attack. Constructing compression function with weakness for Iterated Hash. Crypto competition: MACs from block ciphers.
2013-04-16 (lecture) EF-CMA security. CBC-MAC + insecurity of it. DMAC. PRF is MAC. Message space extension of MACs using hash functions. Davies-Meyer. Miyaguchi-Preneel. Birthday attack on hash functions.
2013-04-16 (practice) EF-CMA definition: necessity of the MAC- and Verify-queries. Key-dependent message security.
2013-04-23 (lecture) Signatures. EF-CMA (for signatures). Naive approach: encryption as signature. One-way functions. One-time signatures from OWFs (Lamport's scheme).
2013-04-23 (practice) Building a protocol (putting all stuff together).
2013-04-30 (lecture) Signatures from one-time signatures: stateful chain construction and stateless tree construction.
2013-04-30 (practice) Proof of the tree construction for signatures.
2013-05-07 (lecture) Full domain hash (FDH) signatures. Random oracle model / heuristic. Security of RSA-FDH. Unsoundness of the random oracle.
2013-05-07 (practice) One-wayness of the random oracle.
2013-05-14 (lecture) Needham-Schroeder protocol (attack & fix). Symbolic cryptography
2013-05-14 (practice) Symbolic analysis of toy protocols. Modeling XOR in symbolic analysis.
2013-05-21 (lecture) Zero-knowledge proofs. Yao's garbled circuits.
2013-05-21 (practice) Examples of protocols that are/are not ZK proofs. Parallel composition of ZK proofs.
2013-05-28 (lecture)
2013-05-28 (practice)

Homework

Your current amount of points in the homework can be accessed here.
Out / due
Homework
Solution
Feb 20 / Mar 6 Homework 1 Solution 1
Feb 14 / Mar 26 Homework 2, prg.zip Solution 2, Solution.java
Apr 3 / Apr 16
Homework 3
Solution 3
Apr 17 / Apr 30
Homework 4
Solution 4
May 3 / May 15
Homework 5
Solution 5 
May 15 / May 24
Homework 6
Solution 6

Description

The course "Cryptology I" introduces the basics of cryptography. After discussing historic ciphers and their weaknesses, we introduce modern cryptographic primitives such as encryption and signature schemes, hash functions, one-way functions etc. We explain how the security of cryptographic schemes is defined and proven. We study advanced cryptographic schemes such as zero-knowledge proofs and secure function evaluation.

Requirements

"Elements of Discrete Mathematics" or some comparable mathematical foundations.

Reading

The following reading supplements this lecture (optional!)

Lindell and Katz, Introduction to Modern Cryptography, Chapman & Hall, 2007.
Materials from the course "Topics of Mathematics in Cryptology" (especially the chapter on probability and the one on modular arithmetic).