**Cryptography for Computer Scientists I**

2015/16

**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".

__:__

**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*)**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__- 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

**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:

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

Final results: [pdf]