Syllabus
- How to Model Cryptographic Primitives and Protocols
- Analysis of Randomised Algorithms
- Computational Indistinguishability
- Semantic Security and Cryptosystems
- Security Notions for Public Key Cryptosystems
- Message Authentication Codes
- Commitment schemes
- Entity Authentication
- Sigma protocols
- Digital signatures
- Zero-knowledge proofs
Authorship of example solutions
The example solutions to most of the exercises are generated in close collaboration with students. For many exercises, I have taken the solution type set by a student and modified it. By doing it I have tried to keep the original solution scheme but iron out some technical wrinkles or add emphasis on the details I believe are worth stressing. The PDF files do not contain explicit references of authorship, I will thank all of my contributors separately
- Alisa Pankova
- Filip Ivanov
- Ilya Kuzovkin
- Ivo Kubjas
- Margus Niitsoo
- Pille Pullonen
- Prastudi Fauzy
- Sanja Scepanovic
The table showing who are the authors of which exercises can be downloaded form here Δ
How to Model Cryptographic Primitives and Protocols
Lecture (PDF)
- Cryptographic absraction techniques
- Functional requirements. Attacks and security requirements
- Discrete logarithm and abstract DL, CDH and DDH groups
- Factorisation problem and abstract distribution of RSA moduli
- Basic reductions between DL, CDH and DDH problems
- Random self-reducibility and its consequences
Exercise session (PDF)
- Formalisation of cryptographic primitives
- Formalisation of attack senarios and security definitions
- Self-reducibility and Diffie-Hellman problem
Example solutions
- Electronic lottery
- Hash functions
- Password hashing
- Random self-reducibility of discrete logarithm
- Random self-reducibility of Computational Diffie-Hellman Problem
- Weak random self-reducibility of Decisional Diffie-Hellman Problem
- Random self-reducibility of Decisional Diffie-Hellman Problem
- Alternative explanation to random self-reducibility of Decisional Diffie-Hellman Problem
Analysis of Randomised Algorithms
Lecture (PDF)
- Turing Machines. Random Access Machines. Circuits
- Chebyshev, Markov and Jensen inequalities
- Standard amplification techniques and their connection to inequalities
- Relation between expected and strict running-time
- Total probability formula and analysis by exhaustive decomposition
- Entropy and its basic properties
Exercise session (PDF)
- Subtleties and paradoxes of computational models
- Applications of total probability formula
- Applications of Chebyshev, Markov and Jensen inequalities
Example solutions
- From expected running time to strict running time
- Amplification by majority voting
- Standard analysis of combiner constructions
- On the necessity of universality in the timing model
Literature:
- Stintson, Cryptography: Theory and Practice, Chapter 2 (entropy).
- Cook, S. A., Reckhow, R. A. Time-bounded random access machines.
- C. E. Shannon, Communication Theory of Secrecy Systems
Computational Indistinguishability
Lecture (PDF)
- Statistical and computational distance
- Pseudorandom generators, functions and permutations
- Guessing games and semantic security
- IND-SEM theorem and some conclusions
Exercise session (PDF)
- Statistical tests
- Trade-offs between false positives and false negatives
- Naive estimates on computational distance
- Properties of computational distance
- Application of guessing games
Example solutions
- Tradeoffs between false positives and false negatives
- Explicit estimation of computational distances
- Lottery game with indistinguishable distributions
- Classical hybrid argument
Semantic Security and Cryptosystems
Lecture (PDF)
- The proof of IND-SEM theorem
- Symmetric key cryptosystems
- IND-FPA security and semantic security
- Insufficiency of IND-FPA security in practical settings
- IND-CPA security and constructive IND-SEM theorem
- PRF/PRP switching lemma
Supporting materials
- IND-SEM proof in details (PDF)
Exercise session (PDF Δ)
- Random functions and permutations
- Analysis of PRF/PRP switching lemma
- Game-based proof for the PRF/PRP lemma
- Anaysis of ECB, CBC, CTR encryption modes
- Left-or-right and real-or-random games
Example solutions
- Insecurity of ECB mode of operation
- Static non-malleability implies IND-CPA security
- BAD reduction schema and its applications
- Horizon splitting technique and its applications
- Insecurity of three round Feistel constuction against chosen ciphertext attacks
Additional exercises (PDF)
- Celebrated Feistel construction
- Constructions for pseudorandom generators
- Circular constructions: PRP => RPF => PRP, PRF => PRG => PRF
Security Notions for Public Key Cryptosystems
Lecture (PDF)
- IND-CPA security and semantic security
- Security of the ElGamal cryptosystem
- Hybrid encryption and its security
- IND-CCA1 security and improper usage of decryption key
- IND-CCA2 security and non-malleability
Exercise session (PDF)
- Analysis of hybrid encryption scheme
- Non-malleability and IND-CCA2 security
- Security of the Goldwasser-Micali cryptosystem
- Practical variants of the ElGamal cryptosystem
- Homomorphic cryptosystems and non-malleability
Example solutions
Message Authentication Codes
Lecture (PDF)
- Simmons's lower bounds
- Almost universal hash functions
- Security of polynomial hashing
- Cryptographic hash functions and their properties
Exercise session (PDF)
- CBC-MAC
- NMAC, HMAC
- UMAC construction
- Authenticated symmetric key encryption
Example solutions
- Security analysis of a message authentication protocol
- Security of authenticated encryption
- Security of authenticated encryption
- Security of Poly-AES construction with randomised nonce
- Hashing as a way to extend the domain of message authentication codes
Commitment schemes
Lecture (PDF)
- Hiding and binding property
- Cryptosystems as commitment schemes
- Homomorphic commitments
- Non-malleable commitments
Exercise session (PDF)
- List commitments
- Cryptographic poker game
- Manually authenticated hybrid encryption
Example solutions
- Second preimage resistance implies one-wayness
- User-aided-key-agreement based on IND-CCA2 secure encryption
- User-aided-key-agreement based on non-malleable encryption
- Partial double-opening of list commitment schemes
- Basic properties of dual mode commitments
Entity authentication
Lecture (PDF)
- Challenge-Response protocols
- Zero-knowledge proofs of knowledge
- Schnorr identification scheme
- Knowledge extraction
Exercise session (PDF)
- Security of Kerberos and MAP-1
- Proofs of possession
Example solutions
Sigma Protocols
Lecture (PDF)
- Knowledge extraction
- Disjunctive and conjunctive compositions
- Honest verifier zero-knowledge proofs of knowledge
- Certified computations for semihonest verifier
Exercise session (PDF)
- Examples of sigma protocols
- Proofs of knowledge for various relations
- Matrix games and details of knowledge extraction
- Various applications of Forking Lemma
Example solutions
Digital Signatures
Lecture (PDF Δ)
- One-time signatures
- Full domain hash
- Fiat-Shamir heuristics
- Random Oracle Model
- Forking Lemma and Random Oracle Model
- Generic Signature Schemes
Exercise session (PDF Δ)
- RSA signature
- Schnorr signature
- Signatures with additional properties
Example solutions
Zero-knowledge Proofs
Lecture (PDF Δ)
- Honest Verifier Zero Knowledge
- CDS proofs for complex relations
- Non-Interactive Zero Knowledge
- Secure coin-flipping and fully secure Zero Knowledge
Exercise session (PDF Δ)
- Applications of CDS proof technique
- Zero knowledge proofs for NP-complete problems