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
- 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.
II Computational Indistinguishability
Lecture ( PDF )- Definitions
- Semantic security
- Block cipher modes
- Pseudorandom generators
- IND=>SEM Proof Explained ( PDF )
- 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
- 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
IV Message Authentication
Lecture ( PDF)- Simmons's lower bounds
- Almost universal hash functions
- Cryptographic hash functions and their properties
- CBC-MAC
- NMAC, HMAC
- UMAC construction
V Commitment schemes
Lecture ( PDF)- Hiding and binding property
- Cryptosystems as commitment schemes
- Homomorphic commitments
- Non-malleable commitments
- Coin-flipping over the phone (exercises 7-8 are voluntary)
- List commitments
- Cryptographic poker game
- Manually authenticated hybrid encryption
VI Entity authentication
Lecture ( PDF)- Challenge-Response protocols
- Zero-knowledge proofs of knowledge
- Schnorr identification scheme
- Knowledge extraction
- Coinflipping and simulators
- Security of Kerberos and MAP-1
- Proofs of posession
- 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
- 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
- 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
- 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
- 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
- How to interpret composability results
- How to interpret triviality results
XI Crypto-Computing
Lecture- Homomorphic encryption
- Various crypto-computing schemes
- Conditional Disclosure Secrets
- Various examples
XIII Design of Complex Protocols
Lecture- Engineering view on universal composability
- Bootstrapping and shared setup
- Bellare-Rogaway model