Cryptography for Computer Scientists I
2015/16
Lecturer and TAStefan Dziembowski


Lecture: Wednesdays 14:15 - 15:45 (room 4420)
ExercisesWednesdays 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". 

Lectures:
  • 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
Exercises:
  • 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 [1], 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 [1]. 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 [1] (Chapter 1). 

  • 04.11.15 We analyzed the birthday attacks on hash functions (see [2], 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 [3])

  • 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 [2], 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 [4], 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 [5].

  • 27.01.16 We continued the lecture.
Bibliography
  1. Oded Goldreich Foundations of Cryptography (Fragments of a Book)
  2. Jonathan Katz, Yehuda Lindell Introduction to Modern Cryptography: Principles and Protocols, First Edition.
  3. Douglas R. Stinson Cryptography: Theory and Practice, Third Edition
  4. Ivan Damgard On Σ-protocols
Exam

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: 
  • pdf - "theory" - 3,4,6, and 7, "exercises":1,2, and 3, 
  • pdf - "theory": 4,5,7, and 8, "exercises": 1,2,3, and 6
  • pdf (theory), pdf (exercises)
Results: [pdf]

Resit exam will take place in room 3130 on February 24 at 17:00-20:00.

Final results: [pdf]

Past courses: 2014/152012/13, 2011/12