Cryptology I
Lecture spring 2020

Instructor Dominique Unruh <<surname> at ut dot ee>
Teaching assistant
Kristiine Saarmann
Lecture Period February 11 –
Lectures Tuesday, 12:15-13:45, room 1022 (Delta) (Unruh; may sometimes be switched with practice)
Practice sessions
Friday, 10:15-11:45, room 2047 (Delta) (Saarmann)
Office hours
See Dominique's webpage
Course Material Lecture notes, blackboard photos (of practice), and exam study guide.
Language English
Mailing list ut-crypto1@googlegroups.com
Contact Dominique Unruh <<surname> at ut dot ee>


Topics covered

2018-05-15 (practice)Schnorr's ZK protocol.
2020-02-11 (lecture)Historical ciphers. Enigma.[video]
2020-02-14 (practice)Breaking a substitution cipher. The weakness of Enigma. Vigenère cipher with a partially known plaintext.
2020-02-18 (lecture)Perfect secrecy. One-time pad. Limitations of one-time-pad/perfect security.[video]
2020-02-21 (practice)Malleability of the one-time-pad (bank transfer). Calculating the probabilities of a two-time pad.
2020-02-25 (lecture)Streamciphers. IND-OT-CPA security. Pseudo-random generators (PRG). Security proof for G(k)⊕m encryption scheme.[video]
2020-02-28 (practice)Clarifications. Extension of the security proof of the lecture. Proof: If G is a PRG, H(x,y):=G(x)||y is PRG.
2020-03-03 (lecture)Block ciphers. AES. Definition: strong pseudorandom permutation (PRP).[video]
2020-03-06 (practice)Security of AES with missing AddRoundKey, SubBytes, MixColumns, and ShiftRows.
2020-03-10 (lecture)ECB mode (and its weakness). CBC mode. Definition IND-CPA. IND-CPA security of CBC. Public key encryption (intro).[video]
2020-03-13 (practice)Malleability of CBC mode. One-time-pad in CBC mode. Game notation.
2020-03-17 (lecture)[Online lecture] Textbook RSA. RSA assumption. Weaknesses of textbook RSA.[video]
2020-03-20 (practice)Crypto competition: authenticated encryption.
2020-03-24 (lecture)ElGamal encryption. Decisional Diffie-Hellman (DDH) assumption. IND-CPA security (public key case). ElGamal is IND-CPA secure.[video]
2020-03-27 (practice)Insecurity of ElGamal modulo prime.
2020-03-31 (lecture)[Online lecture] Malleability of ElGamal. IND-CCA security. RSA-OAEP. Hybrid encryption. Hash functions. Collision-resistance. Davies-Meyer. Miyaguchi-Preneel. Iterated Hash. https://www.uttv.ee/naita?id=26926 (1:15-end), https://www.uttv.ee/naita?id=26954 (start-0:39), https://www.uttv.ee/naita?id=28446 (start-0:35). Q&A: https://www.uttv.ee/naita?id=29615
2020-04-03 (practice)Insecurity of ElGamal modulo prime (continued).
2020-04-07 (lecture)Collision-resistance and non-collision-resistance of Iterated Hash. Merkle-Damgård construction. Sponge construction. Birthday attack.[video]
2020-04-14 (lecture)Signature. EF-CMA security.[video]
2020-04-14 (practice)Breaking collision resistance for various compression functions.[video]
2020-04-17 (practice)Breaking collision resistance for various compression functions & iterated hash/Merkle-Damgård construction using them.
2020-04-21 (lecture)Naive construction of signatures. Full-domain hash (FDH). Random oracle model/heuristic. EF-CMA in random oracle model. Security proof of FDH.[video]
2020-04-24 (practice)Breaking collision resistance for various compression functions & iterated hash/Merkle-Damgård construction using them (continued). Variants of EF-CMA (EF-NMA, EF-OT-CMA).
2020-04-28 (practice)Pseudorandom generators in the random oracle model[video]
2020-05-05 (lecture)Secure function evaluation. Yao's garbled circuits. Oblivious transfer (OT).[video]
2020-05-08 (practice)Millionairs problem using Yao's garbled circuits
2020-05-12 (lecture)Zero-knowledge proofs.[video]
2020-05-19 (lecture)Graph isomorphism proof is zero-knowledge. Symbolic crypto: Needham-Schröder-(Lowe) protocols (NSL). Modeling security of NSL symbolically.[video]
2020-05-22 (practice)Symbolic crypto analysis of a file transfer protocol
2020-05-27 (lecture)Symbolic crypto analysis of NSL protocol
2020-05-29 (practice)Preparation for the exam

Homework

Your current amount of points in the homework can be accessed here.
Out Due Homework Solution
2020-02-252020-03-06Homework 1, wordlist.txtSolution 1, otp-xor.py, otp-xor-advanced.py
2020-03-032020-03-11Homework 2, ind-ot-cpa.py, prg.pySolution 2, ind-ot-cpa-solution.py
2020-03-112020-03-22Homework 3, ecb-distinguish-1.txt, ecb-distinguish.py, ecb-distinguish-2.txtSolution 3, ecb-distinguish-sol.py
2020-03-182020-03-26Homework 4, 3rsa-aes.pySolution 4, 3rsa-aes-adv.py
2020-03-312020-04-08Homework 5, hybrid.pySolution 5, hybrid-solution.py
2020-04-072020-04-15Homework 6, birthday.pySolution 6
2020-04-232020-05-01Homework 7Solution 7
2020-05-142020-05-22Homework 8, yao-gate.pySolution 8, yao-gate-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).