MTAT.07.003 Cryptology II
Important details Lecture on Wednesdays 10.15  12.00 L404
 Exercise sessions on Mondays 12.15  14.00 L405
 Exam dates: 17th July and 25th July
 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 individual exercise sessions and home assignments. Home assignments give 30 points and exercise sessions 10 points.
 Final report. Each student gets a research topic and must write a 610 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: 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 Reduction Types
Lecture (PDF) Turing Machines. Random Access Machines
 Many to one reductions. Compilation from one language to another
 Blackbox reductions. Code wrappers, library calls and rewinding
 Whitebox reductions. Static code analysis
 Random selfreducibility and its consequences
 Relation between vertex and set cover problem
 Selfreducibility of discrete logarithm problem
 Selfreducibility of DiffieHellman problem
 Analysis of TENEX password authentication routine

II Theoretical Background
Lecture (PDF) Entropy and its basic properties
 Chebyshev, Markov and Jensen inequalities
 Hypothesis Testing. Statistical and computational distance
 Notion of computational entropy
 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
 Passwords and minentropy
 Hypothesis testing. Tradeoffs between false positives and false negatives
 Timesuccess profile for a toy cipher
 Shannon's secrecy theory.

III Computational Indistinguishability
Lecture (PDF) Definitions
 Semantic security
 Block cipher modes
 Pseudorandom generators
 IND=>SEM Proof in details (PDF)
 Properties of computational distance and games
 Nonconstructive hybrid argument
 Generalised IND=>SEM proof and its applications

IV Cryptosystems
Lecture (PDF) INDCPA security and semantic security
 Security of the ElGamal cryptosystem
 INDCCA1 security and improper usage of decryption key
 INDCCA2 security and nonmalleability
 PRF/PRP switching lemma
 Security of the GoldwasserMicali cryptosystem
 Block ciphers and their working modes
 Pseudorandom generators
 Practical variants of the ElGamal cryptosystem
 Hybrid encryption
 Pseudorandom generators and block cipher contructions
 Homological classification

V Message Authentication
Lecture (PDF) Simmons's lower bounds
 Almost universal hash functions
 Cryptographic hash functions and their properties
 CBCMAC
 NMAC, HMAC
 UMAC construction

VI 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

VII 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

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