Announcements
28/10/16 : Homework correction, no lecture on Nov. 8th
Hi all,
Two brief announcements:
1. Due to a local conference, there will be no lecture on Tuesday, November 8th.
2. There’s a couple of typos in Homework 4:
- in problem 3, p should be 29, not 27;
- in problem 4, “perfectly indistinguishable plaintexts” should read “perfectly indistinguishable encryptions.”
Thanks for catching the errors!
Best,
Gorjan
24/10/16 : Homework 4, final topics, reading
Hi everyone,
Below is Homework 4 (public-key cryptography.) It is shorter than the usual homework, but it is also due in one week : on November 1st.
I also strongly encourage you to e-mail me your topic ideas for the final homework as soon as possible.
The reading for this week is:
- Section 10.3 (Diffie-Hellman), and in particular the security proof under the DDH assumption;
- Sections 11.1 and 11.2 (public-key encryption)
- Section 11.4.1 (El-Gamal).
If you want to read ahead, you can also look at 11.3 and 11.4.4 (CCA for public-key), or start reading Chapter 12 (digital signatures.)
Best,
Gorjan
14/10/16 : Homework, reading
Hi everyone,
There’s a couple of announcements.
- There will be two more homework sets. The first will be on public-key cryptography, and will be handed out after the break. The second (and final) homework will be different: you will be asked to read about a topic in cryptography, and then write a clear, technical exposition of the topic. A detailed description of this assignment is attached below. Please read it now, and start thinking about your topic. When you have one in mind, write me a brief summary before you start working.
- The reading for this week and next week is as follows:
- 7.6 (Feistel networks)
- 8.1 (Basic group theory)
- Chapter 10 (public-key intro, Diffie-Hellman)
- 11.4 (DDH-based public-key crypto)
- You should also at least skim Appendix B, which describes several efficient algorithms for working in groups.
As usual, feel free to e-mail me with any questions.
Best,
Gorjan
05/10/16 : Homework 3, reading
Hi Everyone,
Please find Homework 3 attached below. It is due Tuesday, October 25th, i.e., after the break. It is of typical length, so it shouldn’t require any of your well-earned holiday time. In fact, I encourage you to set a pre-break deadline for yourself.
The reading for this week is Katz and Lindell, Sections 7.1-7.6. You should make sure you understand:
- definitions of one-way function, one-way permutation, hard-core predicates;
- (recall) definitions of PRG, PRF, and PRP;
- how to use a one-way permutation to construct a PRG of any polynomial expansion;
- how to use a PRG to construct a PRF;
- how to use a PRF to construct a PRP.
I want to emphasize that the constructions in the last three bullets are relatively simple to describe, even though the proofs that they actually work might be quite challenging.
Best,
Gorjan
30/09/16 : PhD students and ECTS
If you are a PhD student taking the course, please e-mail me as soon as possible. (Don’t worry, it’s just about some administrative stuff and ECTS points.)
Best,
Gorjan
29/09/16 : Reminder
Hi everyone,
I would like to remind you that:
- In order to pass the course, you must pass each and every homework set. A passing grade is 60% or higher.
- Only the first homework set can be resubmitted for a new grade.
- The second homework set is due on Tuesday.
Unless you are completely sure that you will pass the second homework, I strongly encourage you to attend today’s lectures and exercises, ask lots of questions, and seek out help (from me, or others in class.)
Best,
Gorjan
28/09/16 : Reading for week 4
Hi everyone,
The reading for this week is Sections 4.1, 4.2, 4.3, 4.4.1, and 4.5.
You should make sure you fully understand:
- purpose of authentication, and how it differs from encryption;
- the login problem and how to solve it with a PRF;
- message authentication codes (MACs): unforgeability, EUF-CMA security
- secure MAC constructions: PRF-MAC and CBC-MAC;
- chosen ciphertext security: IND-CCA and how to satisfy it with authenticated encryption.
If you would like to read ahead for next week, you can start reading Chapter 7.
Best,
Gorjan
04/10/16 : Reading for week 3, Homework 2
Hi everyone,
Attached below is Homework 2, which is due October 4th at 8:30am.
This week’s reading is Sections 3.4, 3.5, 3.6, and 4.1 in Katz and Lindell. You should make sure you fully understand the following concepts:
- definitions of security: IND, indistinguishability of ciphertexts, semantic security;
- multiple-message security and IND-CPA security;
- pseudorandom functions and how to use them to construct IND-CPA-secure symmetric-key encryption schemes;
- block ciphers, ECB and CBC modes;
- authentication (conceptually): what it is for in practice, how it differs from encryption;
As usual, write me if there are any problems/issues.
Best,
Gorjan
14/09/16 : Reading for week 2
This week’s reading is Sections 3.1 to 3.4 in Katz and Lindell (yes, you should read 3.1 again!) There are fewer sections this week, but they’re more dense and there are more technical things that you will need to understand. You should be sure you have a handle on:
- limitations of the one-time pad and information-theoretic security in general;
- the idea behind computational security;
- what an algorithm is, probabilistic algorithms, efficient vs inefficient algorithms;
- polynomially growing functions and negligible functions;
- definitions for computationally secure encryption: the IND game, computational indistinguishability of ciphertext distributions, and semantic security;
- pseudorandom generators (PRGs)
- how to use a PRG to build computationally secure fixed-length encryption schemes;
- single-message security vs multiple-message security.
Feel free to e-mail me with questions/issues. See you tomorrow!
Gorjan
08/09/16 : Homework 1
Here’s the first homework assignment. It’s due Tuesday, 20th of September, at 8:30am. You can submit it however you like (by e-mail, in person, etc.) Please look it over and bring your questions to tomorrow’s lectures.
Gorjan
06/09/16 : Updated Times, Logistics
Hi everyone,
Here’s a few updates after this morning’s meeting. Note the Tuesday start time, and that all times are sharp. Please let me know if there are any problems with this schedule.
- the new meeting times are (all sharp): Tuesdays 8:30 – 10:00 in A112; Thursdays 10:00-12:00 in Aud9 and 13:00-15:00 in 1-0-37 (DIKU);
- as some of you pointed out, I had the wrong lecture weeks in the last announcement: it should be weeks 36-41 and 43-45;
- I will post “weekly readings” for keeping up with the course, starting below with this week. I will mainly refer to Katz and Lindell; you are of course welcome to substitute (or supplement) with other sources.
This week’s reading is Chapters 1 and 2 and Section 3.1 in Katz and Lindell. You should be sure you understand:
- the Caesar (shift) cipher, the substitution cipher, and the Vigenere cipher;
- exhaustive key search and frequency analysis, and how to use them to break all three of the above;
- Kirchkoff’s principle;
- formal definitions: encryption schemes, perfect security, indistinguishability of encryptions, the one-time pad;
- proofs: equivalence of perfect security and indistinguishability, perfect security for one-time pad, Shannon’s theorem.
- some informal understanding (Section 3.1): information theoretic vs computational security, algorithms, probabilistic algorithms, efficient vs inefficient algorithms;
Feel free to e-mail me with questions/issues.
Gorjan