Introduction to Modern Cryptography

Welcome to the web-site of Introduction to Modern Cryptography course.

On November 29th: Scotland's Democratic Future: Exploring Electronic Voting.

Catalogue link

Instructor: Aggelos Kiayias
Teaching Assistant: Giorgos Panagiotakos
Time and Location: Wednesday, 9:00-10:50. Geography (Old Infirmary) 2.13.

The class notes are available in the 2016/2017 web-site.

Homework is available here. Due date: November 15, 2017. (In class, hard-copy, optionally: submit to ITO).

Class Log
20.09.2017 We met Alice and Bob and considered how they can flip a coin over the telephone. We discussed Manuel Blum's coin flipping protocol using an underlying notion of an opaque box. We identified the properties that the box should satisfy in order to be useful in the protocol, hiding and binding. In the 2nd half of the hour we discussed the process that we use in modern cryptography to design and analyze algorithms and protocols. We also discussed the relation to P and NP. Section 1 from the notes.

27.09.2017 We discussed group operations and introduced modular arithmetic (Section 2.1 without the Chinese Remainder Theorem). We then discussed the exponentiation problem and we discussed how we can get an algorithmic solution that is efficient. This is not in the notes but you can read about it in e.g., Wikipedia, see this link. We introduced the inverse problem in the form of computing the logarithm of an element in the group for a given generator. This problem will be eventually identified as the discrete logarithm problem, see Definition 6.2.1 in Section 6.2).

04.10.2017 We did a review of probability theory concepts related to cryptography. First, we discussed about a type of concentration bound: the Chernoff bound. Then, we talked about the notions of statistical distance, negligibility and statistical indistinguishability. After that, we introduced the concept of a statistical test and explored its' relation to statistical distance. Finally, we talked about probabilistic algorithms. All topics discussed are from Section 2 of the notes.

11.10.2017 We introduced the problem of key exchange and described the Diffie Hellman key exchange protocol. Sections 6.1, 6.2, 6.3, 6.4 from the notes.

18.10.2017 We completed the analysis for Diffie Hellman Key Exchange. Section 6.4 and 6.5 from the notes. The concept of zero-knowledge proofs. Section 8, 8.1 and 8.2

25.10.2017 Proving the knowledge of discrete logarithms. The Schnorr protocol. The Splitting Lemma. Section 8.3

01.11.2017 The Schnorr protocol is Honest verifier Zero-Knowledge. Section 8.3. We introduced the commitment primitive, binding and hiding properties, Section 3.1, 3.2 from the notes. We covered the properties for commitment schemes, hiding and binding in more detail and completed the proof for perfect hiding with malicious parameter generation and computational binding under the discrete logarithm problem.

08.11.2017 Digital Signature schemes and their significance; man in the middle attacks. Trapdoor one-way functions. Applications of digital signatures. See Sections 6.8, 7.1, 7.2. The proof of security of digital signatures "full domain hash" assuming a one-way trapdoor function in the random oracle model. Section 7.3 and 7.4.

15.11.2017 Public-key encryption. The ElGamal scheme. Proof of security of ElGamal under the DDH Assumption. Refer to Section 9 from the notes.

22.11.2017 Class wrap up and directions.

29.11.2017 [No class] - participate in the workshop Scotland's Democratic Future: Exploring Electronic Voting.


Home : Teaching : Courses 

Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK
Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail: school-office@inf.ed.ac.uk
Please contact our webadmin with any comments or corrections. Logging and Cookies
Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh