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 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 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 6-10 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: 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 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
- Formalisation of cryptographic primitives
- Formalisation of attack senarios and security definitions
- Self-reducibility and 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
- 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. Time-bounded 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
- IND-SEM theorem and some conclusions
- Statistical tests
- Trade-offs 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 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 swithching lemma
- IND-SEM proof in details (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
- 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)- 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
- 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
-
VI Message Authentication
Lecture (PDF)- Simmons's lower bounds
- Almost universal hash functions
- Security of polynomial hashing
- Cryptographic hash functions and their properties
- CBC-MAC
- NMAC, HMAC
- UMAC construction
- Authenticated symmetric key encryption
-
VII 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
-
VIII 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
-
Under Construction
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