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>


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)


Your current amount of points in the homework can be accessed here.
Out / due
Feb 20 / Mar 6 Homework 1 Solution 1
Feb 14 / Mar 26 Homework 2, Solution 2,
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


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.


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


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