## 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
- Security of Protocols
- Oblivious Transfer

## 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
- Ehsan Ebrahimi
- Filip Ivanov
- Ilya Kuzovkin
- Ivo Kubjas
- Kristiina Rahkema
- Karl Tarbe
- Margus Niitsoo
- Pille Pullonen
- Prastudi Fauzy
- Sanja Scepanovic
- Sander Siim

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
- On the random self-reducibility of the most significant bit of discrete logarithm
- Independence of biased coin throws

#### 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
- Convex closure of distinguishers
- Existence of hard-core bits

### 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. Example solutions

- IND-SEM proof in details (PDF)
- Coin-fixing argument and semantic security
- Semantic security of randomised functions

#### 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

- Security of hash ElGamal cryptosystem
- Security of Goldwasser-Micaly cryptosystem
- Trivial inclusions between non-malleability and indistinguishability
- IND-FPA implies IND-CPA
- Conversion from IND-FPA to IND-CPA

### 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

- Merkle trees are binding commitments
- 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
- Non-malleability implies a restricted form of semantic binding

### 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

- Liveness proof based on a one-way function
- Liveness proof based on a one-way permutation
- Simplified security analysis of MAP-I protocol

### 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

- Analysis of Guillou-Quisquater identification scheme
- Sigma protocol for the ElGamal encryption
- Sigma protocol for the Pedersen commitment scheme
- Weak knowledge-extractor for the Schnorr protocol
- Witness-indistinguishability of disjunctive composition of Schnorr protocols

### 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

#### Example solutions

- Simulator for the Fiat-Shamir identification protocol
- Soundness of QNR-ZK protocol with disjunctive proof of knowledge
- Simulator for the QNR-ZK protocol with disjunctive proof of knowledge
- Knowledge-extraction and simulation distance in QNR-ZK-delay protocol

### Security of Protocols

#### Lecture (PDF)

- Primitives vs protocols
- Beaver's resilience principle
- Ideal vs real world comparison
- Sequential vs universal composability
- Trusted setup and simulation
- Re-usage of public parameters

### Oblivious Transfer

#### Lecture (PDF)

- Various ways to extend 1-out-of-2 oblivious transfer
- Solution to millionaire problem
- Interactive secure circuit evaluation
- Aiello-Ishai-Reingold protocol for oblivious transfer
- Bellare-Micali protocol for oblivious transfer