Cryptology I
Lecture spring 2019

Instructor Dominique Unruh <unruh@ut.ee>
Teaching assistant
Tore Vincent Carstens <tore.carstens@gmx.de>
Lecture Period February 13 –
Lectures Wednesday, 10:15-11:45, room 220 (Paabel) (Unruh; may sometimes be switched with practice)
Practice sessions
Wednesday, 14:15-15:45, room 220 (Paabel) (Unruh/Carstens)
Course Material Lecture notes, blackboard photos (of practice), and exam study guide.
Language English
Mailing list ut-crypto1@googlegroups.com
Contact Dominique Unruh <unruh@ut.ee>


Topics covered

2019-02-13 (lecture)Historical ciphers. Perfect secrecy. One-time pad.[video]
2019-02-20 (practice)Breaking a substitution cipher. Malleability of one-time-pad (bank transfer).
2019-02-27 (lecture)Limitations of one-time-pad/perfect security. Streamciphers. IND-OT-CPA security.[video]
2019-02-27 (practice)Brief introduction to PRGs. Security proof: If G is PRG, then H(x,y):=G(x)||y is PRG. Very short intro to linear feedback shift registers (LFSR).
2019-03-06 (lecture)Pseudo-random generators (PRG). Security proof for G(k)⊕m encryption scheme. Blockciphers. AES (started).[video]
2019-03-06 (practice)Game-based security of one-time pad.
2019-03-13 (lecture)AES (continued). Feistel networks. Definition: strong pseudorandom permutation (PRP).[video]
2019-03-13 (practice)Security of AES with missing AddRoundKey/SubBytes/MixColumns/ShiftRows. Insecurity of 1-round, 2-round and 3-round-Feistel.
2019-03-20 (lecture)Definition IND-CPA. ECB mode (and its weakness). CBC mode. IND-CPA security of CBC.[video]
2019-03-20 (practice)Malleability of CBC mode. Recap: Strong PRP. 3-round-Feistel is not strong PRP.
2019-03-27 (lecture)Public key encryption. Textbook RSA. RSA assumption. Weaknesses of textbook RSA.[video]
2019-03-27 (practice)Crypto competition: authenticated encryption
2019-04-03 (lecture)ElGamal encryption. Decisional Diffie-Hellman (DDH) assumption. IND-CPA security (public key case). ElGamal is IND-CPA secure.[video]
2019-04-03 (practice)(In)security of small variants of RSA
2019-04-10 (lecture)Malleability of ElGamal. IND-CCA security. RSA-OAEP. Hybrid encryption.
2019-04-10 (practice)Insecurity of ElGamal modulo prime.
2019-04-17 (lecture)Hash functions. Collision-resistance. Davies-Meyer. Miyaguchi-Preneel. Iterated Hash. Collision-resistance and non-collision-resistance of Iterated Hash. Merkle-Damgård construction. Message authentication codes (MACs). Insecurity of Merkle-Damgård as a MAC.[video]
2019-04-17 (practice)Breaking collision resistance for various compression functions. Breaking sponge without padding.
2019-04-24 (lecture)Constructions of MACs (secure/insecure): HMAC, CBC-MAC, DMAC, blockcipher as MAC, message length extension using hash functions. EF-CMA security. Birthday attack on hash functions.[video]
2019-04-24 (practice)Variants of EF-CMA (EF-NMA, EF-OT-CMA). Building information-theoretically secure EF-OT-CMA MACs
2019-05-08 (lecture)Signatures. EF-CMA security (for signatures). Naive construction of signatures. One-way functions. Lamport's one-time signatures[video]
2019-05-08 (practice)Design of a movie download protocol
2019-05-15 (lecture)Tree-based signatures (how to get signatures from one-time signatures).[video]
2019-05-15 (practice)Insecurity of Lamport's one-time signature in twice-sign-scenario. Estimating length of tree based signatures.
2019-05-22 (lecture)Unsoundness of random oracle heuristic. Definition and security proof: One-way functions in the random oracle model.

Homework

Your current amount of points in the homework can be accessed here.
Out Due Homework Solution
2019-03-022019-03-16Homework 1, wordlist.txtSolution 1, otp-xor-advanced.py, otp-xor.py
2019-03-232019-04-06Homework 2, ind-ot-cpa.py, ecb-distinguish-2.txt, prg.py, ecb-distinguish.py, ecb-distinguish-1.txtSolution 2, ind-ot-cpa-solution.py, ecb-distinguish-sol.py
2019-04-112019-04-25Homework 3, hybrid.py, 3rsa-aes.pySolution 3, 3rsa-aes-adv.py, hybrid-solution.py
2019-04-152019-05-10Homework 4, additive-group.py, birthday.pySolution 4, additive-group-solution.py
2019-05-152019-05-29Homework 5, owf.pySolution 5, owf-solution.py

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