Cryptology I

Lecture spring 2018

Instructor Dominique Unruh <<surname> at ut dot ee>
Teaching assistant
Tore Vincent Carstens <<firstname dot thirdname at gmx dot de>
Lecture Period Feb 15 - Wed 30
Lectures Wednesday, 12:15-13:45, room 218 (Paabel) (Unruh; may sometimes be switched with practice)
Practice sessions
Wednesday, 16:15-17:45, room 220 (Paabel) (Unruh/Carstens)
Course Material Lecture notes, blackboard photos (of practice), and exam study guide.
Language English
Mailing list
Contact Dominique Unruh <<surname> at ut dot ee>

Topics covered

2018-02-14 (lecture)Historical ciphers.[video]
2018-02-14b (lecture)Perfect secrecy. One-time pad. Security and limitations of OTP.[video]
2018-02-21 (lecture)Stream ciphers (ctd.). IND-OT-CPA security. Pseudo-random generators (PRG). Security proof for G(k)⊕m encryption scheme.[video]
2018-02-21 (practice)Breaking a substitution cipher. Malleability of one-time-pad (bank transfer).
2018-03-01 (lecture)Block ciphers. AES (construction). Feistel networks. Provable security vs. best effort.[video]
2018-03-01 (practice)Security proof: If G is PRG, then H(x,y):=G(x)||y is PRG. Very short intro to linear feedback shift registers (LFSR).
2018-03-07 (lecture)Security notions of block ciphers: strong PRP. Security of encryption: IND-CPA. Modes of operation: ECB, CBC. Insecurity of ECB. IND-CPA security of CBC (only claim).[video]
2018-03-07 (practice)Security of AES with missing AddRoundKey/SubBytes/MixColumns/ShiftRows
2018-03-14 (lecture)Public key encryption. Textbook RSA. RSA-assumption. Weaknesses of textbook RSA.[video]
2018-03-14 (practice)Recap: linear functions. Malleability of CBC mode. "Crypto competition": Authenticated encryption.
2018-03-21 (lecture)ElGamal. Decisional Diffie-Hellman (DDH) assumption. IND-CPA (public-key). Security of ElGamal.[video]
2018-03-21 (practice)Breaking 3RSA for small messages.
2018-03-28 (lecture)Malleability of ElGamal. Definition IND-CCA. Hybrid Encryption. Message authentication codes (MACs). Hash functions. Collision-resistance. Iterated Hash. Collision-resistance and non-collision-resistance of Iterated Hash.[video]
2018-03-28 (practice)Insecurity of ElGamal mod p. Quadratic residues. Breaking collision resistance for various compression functions.
2018-04-04 (lecture)Merkle-Damgård construction. EF-CMA definition. Insecurity of Merkle-Damgård as a MAC. CBC-MAC, DMAC, and their security. MAC from block cipher/PRF. Extending message space of MACs. [video]
2018-04-04 (practice)Breaking Iterated Hash / Merkle-Damgård with various compression functions. Breaking sponge without padding.
2018-04-11 (lecture)Davies-Meyer. Miyaguchi-Preneel. Birthday attacks for hashes. Signatures. EF-CMA. One-way functions.[video]
2018-04-11 (practice)Two variants of EF-CMA. Constructing bad MACs secure under these variants.
2018-04-18 (lecture)One-time signature construction. EF-OT-CMA. Tree-based signatures (how to get signatures from one-time signatures).[video]
2018-04-18 (practice)Constructing a secure protocol for movie download using PKE and signatures.
2018-04-25 (lecture)Full-domain hash (FDH). Random oracle model/heuristic. EF-CMA in random oracle model. Security proof of FDH.[video]
2018-04-25 (practice)Estimating length of tree based signatures.
2018-05-02 (lecture)Secure function evaluation. Yao's garbled circuits. Oblivious transfer (OT).[video]
2018-05-02 (practice)Unsoundness of random oracle heuristic. Definition and security proof: One-way functions in the random oracle model.
2018-05-09 (lecture)Zero-knowledge proofs.[video]
2018-05-09 (practice)Repetition OT and Yaos protocol. Different more active secure versions of Yaos protocol
2018-05-16 (lecture)Symbolic cryptography. Needham-Schröder-(Lowe) protocols (NSL). Modeling and proving security of NSL symbolically.[video]
2018-05-16 (practice)Schnorr's ZK protocol.
2018-05-34 (practice)Symbolic crypto analysis of "movie download" protocol


Your current amount of points in the homework can be accessed here.
Out Due Homework Solution
2018-02-222018-03-02Homework 1, wordlist.txtSolution 1,,
2018-03-012018-03-09Homework 2,, prg.pySolution 2,
2018-03-082018-03-16Homework 3, ecb-distinguish-2.txt,, ecb-distinguish-1.txtSolution 3,
2018-03-152018-03-23Homework 4, 3rsa-aes.pySolution 4,
2018-03-222018-03-30Homework 5, additive-group.pySolution 5,
2018-03-302018-04-06Homework 6, hybrid.pySolution 6,
2018-04-052018-04-13Homework 7Solution 7
2018-04-122018-04-20Homework 8,, owf.pySolution 8,
2018-04-192018-04-27Homework 9Solution 9
2018-05-032018-05-11Homework 10, yao-gate.pySolution 10,
2018-05-112018-05-18Homework 11, zk-prog.pySolution 11,
2018-05-172018-05-25Homework 12Solution 12


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