Provable Security
This course will discuss classical techniques in defining and proving security of cryptographic schemes via reductions. We will focus digital signatures, identity-based encryption, and CCA-secure public-key encryption. This course is a continuation of TMA4160 Cryptography. TMA4160 is required for participation of this seminar.
Lecturer
When and Where
Messages
- 31.05.2022: Hints to Exercise Set 2 is published too.
- 06.05.2022: See Exam section for more details.
- 21.04.2022: Problem set 2 is available. The deadline is 06.05..
- 05.04.2022: Hints to the 1st problem set is here.
- 22.02.2022: The 1st problem set has been published. See the following.
- 27.01.2022: We have capacity for this seminar and we are not accepting any new participant.
- 21.01.2022: Hello World! The first lecture is on 28.01.2022 from 09:15 - 11:00 in R22. This is the only time in R22.
Textbook
I have sent it to you.
Syllabus
We will cover the following topics. Each topic may take 1-3 meeting.
- Introduction (Chapter 1)
- BLS' signature (Chapter 2.1 to 2.3)
- Boneh-Boyen's signature (Chapter 2.4): Chosen-able
- Introduction to identity-based encryption (IBE) and Boneh-Franklin IBE (4.1 - 4.3)
- Boneh-Boyen's IBE (Chapter 4.4):
Chosen-able(Runzhi Zeng) - Waters' IBE (Chapter 4.5)
- CCA-secure PKE from IBE (Chapter 5.1, 5.2):
Chosen-able(Lea Sibylle Nürnberger) - BMW construction (Chapter 5.3):
Chosen-able(Sunniva Engan) - PKE from hash proof systems (Chapter 5.5, 5.6, maybe also 5.7):
Chosen-able. Two persons can work on this topic(Sander Støle Hageli and Espen Sund)
Lecture notes
| Date | Topic | Chapter in the textbook | Classroom notes | Remarks |
|---|---|---|---|---|
| 28.01. | Introduction. PRP-PRF switching lemma | Admin. Introduction. PRP-PRF switching lemma (Chapter 1.2) | Lecture 01 | |
| 04.02. | Code-based Games | 1.3 – 1.4 | Lecture 02 | |
| 11.02. | The BLS signature | 2.1 –2.3 | Lecture 03 | |
| 18.02. | The Boneh-Boyen signature | 2.4 | Lecture 04 | |
| 25.02. | The BB signature (cont.). | 2.4 | See above | |
| 04.03. | The BB signature (cont.) and IBE | 2.4; 4.1 | See above for BB, and this for IBE | |
| 11.03. | IBE. The Boneh-Franklin IBE | 4.1-4.3 | Lecture 06 | |
| 18.03. | The Boneh-Boyen IBE | 4.2 – 4.4 | Lecture 07 | Runzhi Zeng |
| 25.03. | The Waters IBE | 4.5 | Lecture 08 | |
| 01.04. | CCA secure PKE from IBE | 5.1, 5.2 | Lecture 09 | Lea Sibylle Nürnberger |
| 08.04. | IBE from Affine MAC | https://eprint.iacr.org/2014/581 | The-State-of-the-art in IBE | |
| 22.04. | BMW PKE | 5.3 | Lecture 11 | Sunniva Engan |
| 29.04. | No Meeting | No Meeting | ||
| 06.05. | Hash Proof Systems | 5.5-5.7 | Lecture 12 | Sander Støle Hageli and Espen Sund |
Problem Sets
You should finish the problem sets on your own, because questions in the oral exam are similar to them. If you want to collaborate, you can do so, but please write down with whom you have collaborated and what is your own contributions.
You should submit your answers in a PDF. Please send it to me via Email.
- Problem Set 1: Exercises 2.6, 2.7 (p. 32), 2.9 and 2.11 (p. 33) (To get this approved, you need to finish 2.7 and 2.9 correctly, most of 2.11 correctly. Try 2.6 as much as possible. In fact, we have given some hints for 2.6 in the last part of the BLS lecture.) Deadline: 18.03.2022. Hints
- Problem Set 2: Exercises 4.1, 4.3, 4.4 (p. 68, 69). Deadline: 06.05.2022. Hints
Exam
It will be oral and it takes at most 30 minutes where you will be asked questions about schemes and proofs covered by this seminar (cf. Syllabus). We may also ask questions about some variants of the schemes we discuss. The key to prepare is to understand the seminar (like schemes and proofs) instead of remembering by heart.
To get qualified for the oral exam, you need to either get all the problem sets approved or present a topic (which is chosen-able) in syllabus. It will be explained in details in the first meeting.
News to Exam An email with the concrete time slot has been sent to each of you. If you didn't receive it, please let me know. For those on 09.06.2022, your exam room is Central-2 822; and for 10.06.2022, it is Central-2 734.