Introduction to Modern Cryptography - INFR11131

Lecturer: Aggelos Kiayias

Meeting Time: Wednesday 9-10:50am

Meeting Room: Old Infirmary 2.13 for October 19th, remaining of semester Hunter Building, Lecture Theatre O17, except last two classes (November 23, 30th) again in Old Infirmary 2.13

Class Notes: [Cryptograph_Primitives_and_Protocols.pdf] draft of 23rd November

Bitcoin slides by Giorgos Panagiotakos: [lectureIMC.pdf]

Course Work (Due 23rd November 2016) : [hw.pdf] Revised!

Exam Structure. The exam has 3 problems from which you have to solve 2 of them. Each problem has a number of questions. You are supposed to answer all questions. Answering a question requires expressing  a security model, a protocol or algorithm, or a security proof that a protocol or algorithm is secure based on a model that you either know or it is given in the statement. Sample question (1/2 of a problem)

Useful References.

  1. 1A Computational Introduction to Number Theory and Algebra by V. Shoup

  2. 2Mathematics of Public Key Cryptography by S. Galbraith

  3. 3Handbook of Applied Cryptography, by A. Menezes, P. van Oorschot, and S. A. Vanstone.

Class log.


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.


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).


We studied probabilistic algorithms. We defined the output probability of a probabilistic algorithm and the events that may be defined with respect to this output. We explained the importance of using probabilistic algorithms when arguing about the hardness of problems that are relevant to Cryptography. We sketched a way to realize a commitment scheme which is the primitive that can implement the “box” used in the coin flipping protocol. Refer to Section 2.8.


We defined formally the correctness and security of commitment schemes, in the properties of correctness, binding, hiding, cf. Section 3. We then recalled the construction of commitment schemes based on multiplicative groups (Pedersen commitment). We started the discussion on the security proof focusing on the binding property.


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. We introduced statistical distance as an important measure of similarity between random variables. We introduced the problem of key exchange and described the Diffie Hellman key exchange protocol. The lecture corresponds to Sections 2.6, 2.7, 3.3, 3, 6.1.


Introduction to Bitcoin. Bernoulli trials, Binomial distribution, Chernoff bounds. Bitcoin, currencies, double spending attacks, transactions, blocks, proof of work, difficulty. Modeling Bitcoin, Random oracle. Successful rounds. Synchronous operation.  [lectureIMC.pdf] Refer to Section 2.5 for the tail bounds.


We completed the analysis for Diffie Hellman Key Exchange. Sections 6.4, 6.5 from the notes.


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


Digital Signature schemes and their significance. 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.5.


Exercise discussion, farewell.

For the exam you have to study all the above mentioned sections from the notes. Specifically, sections

1 2.1 without the Chinese Remainder Theorem, 2.5, 2.6, 2.7, 2.8,  3 6.1, Definition 6.2.1, 6.4, 6.5, 6.8,7.1,7.2.,7.5, 9.