MTAT.07.003 Cryptology II
Important details Lecture on Wednesdays 14.15  16.00 L404
 Exercise sessions on Mondays 14.15  16.00 L405
 Exam dates: To be announced
 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 openbook 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 home assignments given out in each exercise session. Usually, the home assignement is a single exercise from the exercise sheet not solved in the exercise session.
 Final report. Each student gets a research topic and must write a 610 page report. The report can give up 50 points. This year the reports are mostly supplementary materials for the lectures.
 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: 050 (F), 5160 (E), 6170 (D), 7180 (C), 8190 (B), 91100 (A). A Gentleman's agreement: the exam result cannot decrease grade from E to grade F.
Tentative Schedule

I 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 selfreducibility and its consequences
 Formalisation of cryptographic primitives
 Formalisation of attack senarios and security definitions
 Selfreducibility and DiffieHellman 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 runningtime
 Total probability formula and analysis by exhaustive decomposition
 Entropy and its basic properties
 Subtleties and paradoxes of computational models
 Applications of total probability formula
 Applications of Chebyshev, Markov and Jensen inequalities
 Stintson, Cryptography: Theory and Practice, Chapter 2 (entropy).
 Cook, S. A., Reckhow, R. A. Timebounded random access machines.
 C. E. Shannon, Communication Theory of Secrecy Systems
III Computational Indistinguishability
Lecture (PDF) Statistical and computational distance
 Pseudorandom generators, functions and permutations
 Guessing games and semantic security
 INDSEM theorem and some conclusions
 Statistical tests
 Tradeoffs between false positives and false negatives
 Naive estimates on computational distance
 Properties of computational distance
 Application of guessing games

IV Semantic Security and Cryptosystems
Lecture (PDF) The proof of INDSEM theorem
 Symmetric key cryptosystems
 INDFPA security and semantic security
 Insufficiency of INDFPA security in practical settings
 INDCPA security and constructive INDSEM theorem
 PRF/PRP swithching lemma
 INDSEM proof in details (PDF)
 Random functions and permutations
 Analysis of PRF/PRP switching lemma
 Gamebased proof for the PRF/PRP lemma
 Anaysis of ECB, CBC, CTR encryption modes
 Leftorright and realorrandom games
 BAD reduction schema and its applications
 Horizon splitting technique and its applications
 Insecurity of three round Feistel constuction against chosen ciphertext attacks
 Celebrated Feistel construction
 Constructions for pseudorandom generators
 Circular constructions: PRP => RPF => PRP, PRF => PRG => PRF

V Public Key Cryptosystems
Lecture (PDF) INDCPA security and semantic security
 Security of the ElGamal cryptosystem
 Hybrid encryption and its security
 INDCCA1 security and improper usage of decryption key
 INDCCA2 security and nonmalleability
 Analysis of hybrid encryption scheme
 Nonmalleability and INDCCA2 security
 Security of the GoldwasserMicali cryptosystem
 Practical variants of the ElGamal cryptosystem
 Homomorphic cryptosystems and nonmalleability

VI Message Authentication
Lecture (PDF) Simmons's lower bounds
 Almost universal hash functions
 Security of polynomial hashing
 Cryptographic hash functions and their properties
 CBCMAC
 NMAC, HMAC
 UMAC construction
 Authenticated symmetric key encryption

VII Commitment schemes
Lecture (PDF) Hiding and binding property
 Cryptosystems as commitment schemes
 Homomorphic commitments
 Nonmalleable commitments
 List commitments
 Cryptographic poker game
 Manually authenticated hybrid encryption

VIII Entity authentication
Lecture (PDF) ChallengeResponse protocols
 Zeroknowledge proofs of knowledge
 Schnorr identification scheme
 Knowledge extraction
 Security of Kerberos and MAP1
 Proofs of posession

VIII Digital Signatures
Lecture (PDF) FiatShamir heuristics
 Random Oracle Model
 Forking Lemma and Random Oracle Model
 Generic Signature Schemes
 RSA signature
 Schnorr signature
 Signatures with additional properties

IX Sigma Protocols
Lecture (PDF) Knowledge extraction
 Disjunctive and conjunctive compositions
 Honest verifier zeroknowledge proofs of knowledge
 Certified computations for semihonest verifier
 Examples of sigma protocols
 Proofs of knowledge for various relations
 Matrix games and details of knowledge extraction
 Various applications of Forking Lemma

X Zeroknowledge Proofs
Lecture (PDF) Honest Verifier Zero Knowledge
 CDS proofs for complex relations
 NonInteractive Zero Knowledge
 Secure coinflipping and fully secure Zero Knowledge
 Applications of CDS proof technique
 Zero knowledge proofs for NPcomplete problems

Under Construction
XI Security of Protocols
Lecture (PDF) Beaver's maximal resilience principle
 Highest achievable security
 Ideal vs real world model
 Coinflipping over the phone
 Other simple example protocols
 Lottery protocols
 Coinflipping over the phone and secure poker
 Simulator constructions for coinflipping
 Analysis of zeroknowledge proofs

XII Oblivious Transfer
Lecture (PDF) Various definitions of oblivious transfer
 Homomorphic oblivious transfer
 Classical oblivious transfer
 Completeness result
 How to make oblivious transfer fully secure
 Classical oblivious transfer protocols

XIV Composability
Lecture (PDF) Problems with parallel execution
 Universal composability and its characterisation
 Triviality results

XIV Design of Complex Protocols
Lecture (PDF) Security models and levels
 Private computations
 Consistent computations
 Fully secure computations
 Engineering view on universal composability
 Bootstrapping and shared setup