Cryptography for Computer Scientists I
Lecturer and TA: Stefan Dziembowski
Lecture: Wednesdays 14:15 - 15:45 (room 4420)
Exercises: Wednesdays 16:15 - 17:45 (room 5870)
Assessment methods and assessment criteria: there will be a final written exam consisting of two parts: the "theory" part, and the "exercises".
- 07.10.15 Introduction to Cryptography [pptx,pdf]
- 14.10.15 Symmetric Encryption I [pptx,pdf]
- 21.10.15 Symmetric Encryption II [pptx,pdf]
- 28.10.15 Symmetric Encryption III [pptx,pdf]
- 04.11.15 Message Authentication and Introduction to Hash Functions [pptx,pdf]
- 18.11.15 Hash Functions - continued [pptx,pdf], Key Management and Public-Key Cryptography [pptx,pdf]
- 25.11.15 A Brush-up on Number. Theory and Algebra [pptx,pdf] (part of this material was covered on the exercises, and part on the next lecture)
- 02.12.15 Public-Key Encryption I [pptx,pdf]
- 09.12.15 Public-Key Encryption II [pptx,pdf]
- 16.12.15 Signature Schemes and Commitment Schemes [pptx,pdf] (slides 86-99 were covered on the exercises)
- 13.01.16 Commitment Schemes and Zero-Knowledge Protocols [pptx,pdf]
- 20.01.16 Two-party and Multi-party Computation Protocols [pptx,pdf]
- 27.01.16 Introduction to Bitcoin -- we used slides from my longer tutorial, available here [pptx,pdf], we stopped at slide 101
- 14.10.15: we solved the exercises 1,3, and 4 from the course of Jonathan Katz (the solutions are available here).
- 21.10.15: we showed how to increase the expansion factor of a PRG (see , Section 3.3.3), and how to construct a PRF from a PRG (without a proof). This construction is due to Goldreich, Goldwasser, and Micali (and sometimes called "GGM"), and it can be found, e.g., in Section 3.6.2 of . We also solved Exercise 2 ("Extending the range of a PRF") from the course of Stanisław Jarecki. We also discussed the difference between negligible and noticeable functions (see Sections 1.1 and 1.2 of this notes).
- 28.10.15: we finished some exercises from last week. We also did Exercises 1 and 3 from here, and Exercise 7 from  (Chapter 1).
- 04.11.15 We analyzed the birthday attacks on hash functions (see , Section 4.6.3, and Appendix A.4). We showed briefly how the information-theoretically secure MACs (aka authentication codes) work (see Section 4.5 of )
- 18.11.15 Key agreement from public key encryption, key agreement from padlocks, Merkle Puzzles.
- 25.11.15 We did the Baby-Step Giant Step algorithm, and did some of the material from the slides from Lecture 8 [pptx,pdf].
- 02.12.15 we discussed the alleged NSA backdoor in the Dual_EC_DRBG algorithm, see this presentation. We solved Ex. 7.5 and 7.6 from , showed why using RSA with exponent e=3 is bad (see [here] page 288, point (ii)), and a fault attack on RSA.
- 09.12.15 Private Information Retrieval (see these slides: [pptx,pdf]).
- 16.12.15 We discussed constructions from slides 86-99 of [pptx,pdf]. We showed a construction of a hash function from the discrete log assumption (see, e.g., Exercise 3b from [here]). We discussed the blind signatures based based on the RSA, and the idea to enhance banknote security by using fibers infused in the paper, and the digital signatures.
- 13.01.16 We provided an overview of Sigma protocols. We used , skipping Section 7.1, and focusing on Section 10. We also discussed the Schnorr signatures.
- 20.01.16 We continued the lecture, and discussed a construction of information-theoretically passively secure MPC protocols, see Section 15 of .
- 27.01.16 We continued the lecture.
- Oded Goldreich Foundations of Cryptography (Fragments of a Book)
- Jonathan Katz, Yehuda Lindell Introduction to Modern Cryptography: Principles and Protocols, First Edition.
- Douglas R. Stinson Cryptography: Theory and Practice, Third Edition
- Ivan Damgard On Σ-protocols
- Ronald Cramer Introduction to Secure Computation
The exam will take place from 10 AM to 1 PM on 3.02.16 in room 3180. It will consist of two parts:
- the "theory" part (when it will not be allowed to use any materials like books or notes), and
- the "exercises"(when the use of books and notes is will be allowed).
Here are some examples of exercises:
Resit exam will take place in room 3130 on February 24 at 17:00-20:00.
Final results: [pdf]