# MTAT.07.003 Cryptology II

**Important details**

- Lecture on Fridays 10.15 -- 12.00 L403
- Exercise sessions on Wednesdays 12.15 -- 14.00 L405
- Exam dates 04.06.2008 L207 (10.00-13.00) and 29.06.2008 L207 (10.00-13.00)
- Lectures and exercise sessions are held in English.
- Reports and examination can be both in English and Estonian.

### Requirements

Prerequisites to Cryptology II course are- familiarity higher math and algebra
- rudiments of complexity theory
- basic level understanding in cryptology
- reasonable English skills

If the formal requirements of
the
ÕIS do not permit registration then write me an email or
talk with me. After that we decide whether to enrol you or
not. Secondly, active participation in the course is absolute
necessity. You must participate in most lectures or otherwise
you **are not allowed** to take the exam. Special
arrangements are possible but not advised.

The course grade is determined by three components:

- active participation
- a final research report
- an oral open-book exam

#### Formal grading system

**Participation.**Student gets grade**F**if he or she misses 3 or more lectures. Student gets grade**F**if he or she misses 3 or more exercise sessions.

In reasonable circumstances, it is possible to compensate missed lectures or exercise sessions by extra work. Details are determined by individual agreements with the lecturer.**Active participation.**Students are entitled to get from 0 to 40 points from exercise sessions. Points are given by aggregating points of individual exercise sessions.**Final report.**Each student gets a research topic and must write a 6-10 page report. The report can give up 50 points.**Extra points.**Students can get extra points from additional exercises.**Final grading and exam.**All points specified above are summarised before the exam. The exam might change this sum up to 10 points in both directions. Next, the grade is determined by the standard university scale: 0-50 (**F**), 51-60 (**E**), 61-70 (**D**), 71-80 (**C**), 81-90 (**B**), 91-100 (**A**). A Gentleman's agreement: the exam result cannot decrease grade from**E**to grade**F**.

### Tentative Schedule

#### I Theoretical Background

**Lecture**( PDF)

- Entropy and its basic properties
- Chebyshev, Markov and Jensen inequalities
- Hypothesis Testing. Statistical and computational distance
- Turing Machines. Random Access Machines
- Notion of computational entropy

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

**Exercise session**( PDF, exercises 1--5, baseline 3.75 exercises)

- Passwords and min-entropy
- Hypothesis testing. Trade-offs between false positives and false negatives
- Time-success profile for a toy cipher
- Shannon's secrecy theory.

#### II Computational Indistinguishability

**Lecture**( PDF )

- Definitions
- Semantic security
- Block cipher modes
- Pseudorandom generators

**Additional materials**

- IND=>SEM Proof Explained ( PDF )

**Exercise session**( PDF, 1--6, baseline 4.0 exercises)

- Properties of computational distance and games
- Non-constructive hybrid argument
- Block ciphers
- Generalised IND=>SEM proof and its applications

#### III Cryptosystems

**Lecture**( PDF )

- IND-CPA security and semantic security
- Security of the ElGamal cryptosystem
- IND-CCA1 security and improper usage of decryption key
- IND-CCA2 security and non-malleability

**Exercise session I**( PDF, 1--6, baseline 4 exercises)

- PRF/PRP switching lemma
- Security of the Goldwasser-Micali cryptosystem
- Block ciphers and their working modes
- Pseudorandom generators

**Exercise session II**( PDF, 1--6, baseline 4 exercises)

- Practical variants of the ElGamal cryptosystem
- Hybrid encryption
- Pseudorandom generators and block cipher contructions
- Homological classification

#### IV Message Authentication

**Lecture**( PDF)

- Simmons's lower bounds
- Almost universal hash functions
- Cryptographic hash functions and their properties

**Exercise session**( PDF, 1--6, baseline 3 exercises)

- CBC-MAC
- NMAC, HMAC
- UMAC construction

#### V Commitment schemes

**Lecture**( PDF)

- Hiding and binding property
- Cryptosystems as commitment schemes
- Homomorphic commitments
- Non-malleable commitments

**Exercise session**( PDF, 1--8, baseline 4 exercises)

- Coin-flipping over the phone (exercises 7-8 are voluntary)
- List commitments
- Cryptographic poker game
- Manually authenticated hybrid encryption

**Extra lecture: Crash Course to Coin Flipping**( PDF)

#### VI Entity authentication

**Lecture**( PDF)

- Challenge-Response protocols
- Zero-knowledge proofs of knowledge
- Schnorr identification scheme
- Knowledge extraction

**Exercise session**( PDF, baseline 3.5 exercises)

- Coinflipping and simulators
- Security of Kerberos and MAP-1
- Proofs of posession

**Exercise session**( PDF, baseline 4 exercises)

- Matrix games and details of knowledge extraction
- Proofs of knowledge for various relations
- Soundness vs security

#### VII Digital Signatures

**Lecture**( PDF)

- Fiat-Shamir heuristics
- Random Oracle Model
- Forking Lemma and Random Oracle Model
- Generic Signature Schemes

**Exercise session**(PDF, baseline 3.75 exercises)

- RSA signature
- Schnorr signature
- Various applications of Forking Lemma

#### VIII Zero-knowledge proofs

**Lecture**( draft )

- Honest Verifier Zero Knowledge
- CDS proofs for complex relations
- Non-Interactive Zero Knowledge
- Secure coin-flipping and fully secure Zero Knowledge

**Exercise session**( PDF , baseline 3 exercise)

- Applications of CDS proof technique
- Zero knowledge proofs for NP-complete problems

#### X Oblivious Transfer

**Lecture**( PDF )

- Various definitions of oblivious transfer
- Homomorphic oblivious transfer
- Classical oblivious transfer
- Completeness result

**Exercise session**( PDF , baseline 4 exercises)

- How to make oblivious transfer fully secure
- Classical oblivious transfer protocol

#### IX Secure Computation

**Lecture**( PDF )

- Security models and levels
- Private computations
- Consistent computations
- Fully secure computations

**Exercise session**

- Examples of various security levels
- How to choose appropriate model

#### XII Composability

**Lecture**( PDF )

- Problems with parallel execution
- Universal composability and its characterisation
- Triviality results

**Exercise session**

- How to interpret composability results
- How to interpret triviality results

#### XI Crypto-Computing

**Lecture**

- Homomorphic encryption
- Various crypto-computing schemes
- Conditional Disclosure Secrets

**Exercise session**

- Various examples

#### XIII Design of Complex Protocols

**Lecture**

- Engineering view on universal composability
- Bootstrapping and shared setup

**Exercise session**

- Bellare-Rogaway model