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 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 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 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 Reduction Types
Lecture (PDF)- Turing Machines. Random Access Machines
- Many to one reductions. Compilation from one language to another
- Black-box reductions. Code wrappers, library calls and rewinding
- White-box reductions. Static code analysis
- Random self-reducibility and its consequences
- Relation between vertex and set cover problem
- Self-reducibility of discrete logarithm problem
- Self-reducibility of Diffie-Hellman 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. Time-bounded random access machines.
- C. E. Shannon, Communication Theory of Secrecy Systems
- 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.
-
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
- Non-constructive hybrid argument
- Generalised IND=>SEM proof and its applications
-
IV 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
- PRF/PRP switching lemma
- Security of the Goldwasser-Micali 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
- CBC-MAC
- NMAC, HMAC
- UMAC construction
-
VI Commitment schemes
Lecture (PDF)- Hiding and binding property
- Cryptosystems as commitment schemes
- Homomorphic commitments
- Non-malleable commitments
- List commitments
- Cryptographic poker game
- Manually authenticated hybrid encryption
-
VII Entity authentication
Lecture (PDF)- Challenge-Response protocols
- Zero-knowledge proofs of knowledge
- Schnorr identification scheme
- Knowledge extraction
- Security of Kerberos and MAP-1
- Proofs of posession
-
VIII Digital Signatures
Lecture (PDF)- Fiat-Shamir 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 zero-knowledge 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 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
- Applications of CDS proof technique
- Zero knowledge proofs for NP-complete problems
-
XI Security of Protocols
Lecture (PDF)- Beaver's maximal resilience principle
- Highest achievable security
- Ideal vs real world model
- Coin-flipping over the phone
- Other simple example protocols
- Lottery protocols
- Coin-flipping over the phone and secure poker
- Simulator constructions for coin-flipping
- Analysis of zero-knowledge 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