Cryptology I

Lecture spring 2016

Instructor Dominique Unruh <<surname> at ut dot ee>
Teaching assistant
Prastudy Fauzi <<givenname> at ut dot ee>
Lecture Period February 10, 2015 - May 27, 2015
Lectures Wednesdays, 12:15-13:45, room 512 (Unruh; may sometimes be switched with tutorial)
Practice sessions
Fridays, 10:15-11:45, room 512 (Unruh)
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

2016-02-10 (lecture)Classical ciphers.[video]
2016-02-12 (practice)Breaking a substitution cipher. How to define security of encryption (sketches).
2016-02-17 (lecture)Perfect secrecy. One-time pad. Security and limitations of OTP. Streamciphers (basic construction). LFSR.[video]
2016-02-19 (practice)Breaking LFSRs with linear algebra. Malleability of one-time-pad (bank transfer). Attacking the linear congruence randomness generator
2016-02-26 (lecture)Stream ciphers (ctd.). IND-OT-CPA security. Pseudo-random generators (PRG). Security proof for stream ciphers.[video]
2016-03-02 (lecture)Block ciphers. DES (construction). Feistel networks. 2DES, 3DES. Meet-in-the-middle attack[video]
2016-03-04 (practice)Security proof: If G is PRG, then H(x,y):=G(x)||y is PRG
2016-03-09 (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.[video]
2016-03-11 (practice)Details of stream cipher security proof. Malleability of CBC mode
2016-03-16 (lecture)Public key encryption. Textbook RSA. RSA-assumption. Weaknesses of textbook RSA. ElGamal.[video]
2016-03-18 (practice)"Crypto competition": Authenticated encryption
2016-03-23 (practice)Breaking 3RSA for small messages. RSA with N=pqr
2016-03-30 (lecture)ElGamal. Decisional Diffie-Hellman (DDH) assumption. IND-CPA (public-key). Security of ElGamal. Malleability of ElGamal. Hybrid Encryption[video]
2016-04-01 (lecture)Message authentication codes (MAC). Hash functions. Collision resistance. Iterated hash. Merkle-Damgård construction.
2016-04-06 (lecture)Merkle-Damgård. Davies-Meyer. Miyaguchi-Preneel. Insecurity of Merkle-Damgård as a MAC. HMAC. EF-CMA definition. MAC from block cipher/PRF. Extending message space of MACs.[video]
2016-04-08 (practice)Two variants of EF-CMA. Constructing bad MACs secure under these variants.
2016-04-13 (lecture)Signatures. EF-CMA. One-way functions. One-time signature construction.[video]
2016-04-15 (practice)Constructing a secure protocol for movie download using PKE and signatures.
2016-04-20 (lecture)Tree-based signatures (how to get signatures from one-time signatures).[video]
2016-04-22 (practice)Security proof of one-time signatures scheme (partial)
2016-04-27 (lecture)Full Domain Hash (FDH) signatures. Random oracle model/heuristic. Unsoundness of random oracle heuristic.[video]
2016-04-29 (practice)Constructiong and security proof: One-way functions in the random oracle model
2016-05-04 (lecture)Symbolic cryptography. Needham-Schröder-(Lowe) protocols.[video]
2016-05-06 (practice)Symbolic crypto analysis of "movie download" protocol
2016-05-11 (practice)Developing a (simple) protocol for secure channels (à la TLS).
2016-05-13 (lecture)Secure function evaluation. Yao's garbled circuits. Oblivious transfer (OT).[video]
2016-05-18 (lecture)Overview of quantum cryptography (post-quantum crypto, quantum protocols).[video]
2016-05-20 (practice)(Trying to) make a passive OT protocol actively secure.
2016-05-25 (lecture)Zero-knowledge proofs.[video]

Homework

Your current amount of points in the homework can be accessed here.
Out Due Homework Solution
2016-02-172016-03-04Homework 1Solution 1, otp-xor.py
2016-03-092016-03-25Homework 2, ind-ot-cpa.py, prg.pySolution 2, ind-ot-cpa-solution.py, ind-cpa-solution.py
2016-03-212016-04-01Homework 3, ecb-distinguish.py, ecb-distinguish-2.txt, ecb-distinguish-1.txt, 3rsa-aes.pySolution 3, 3rsa-aes-adv.py, ecb-distinguish-sol.py
2016-04-052016-04-15Homework 4Solution 4
2016-04-202016-04-29Homework 5, owf.pySolution 5, owf-solution.py
2016-05-022016-05-13Homework 6Solution 6
2016-05-162016-05-27Homework 7, sym-crypto-parts.pySolution 7, sym-crypto.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).