Cryptology deals with mathematical techniques for design and analysis of algorithms and protocols for digital security in the presence of malicious adversaries. In public-key cryptography two parties can establish, for example, private and authentic communication channels without the necessity of having met before. The distinguishing feature of this concept is that they do not require a secure initial exchange of one or more secret keys as is required when using private-key (symmetric) cryptography.
The first instantiation of this concept was proposed in 1978 by Rivest, Shamir, and Adleman, the well-known RSA encryption-system, whose security is based on the intractability of factoring large composite numbers. A variant of the RSA encryption-system is nowadays installed in hundred of millions of web-browsers and is used for secure Internet connections. Other modern encryption-systems also rely on different intractability problems, for example the hardness of computing the discrete logarithm in finite cyclic groups, approximating the shortest vector in lattices, or decoding random linear codes.
We discuss several important public-key primitives including one-way trapdoor functions, encryption and digital signatures and show how to define and rigorously prove their security. These examples will also exhibit interesting connections with algebra, number theory, complexity and probability theory.
A (tentative) list of topics is as follows: basics of complexity theory and number theory, one-way functions, public-key encryption, digital signatures, security against active adversaries, and identity-based encryption. We will also intend to discuss some examples of encryption-systems with enhanced functionality such as searching on encrypted data.
Prerequisites
Basic undergraduate algebra and probability theory. Prior knowledge of cryptology (e.g., the Mastermath Course on Cryptology) is helpful, but certainly not necessary.
Literature
Jonathan Katz, Yehuda Lindell, “Introduction to Modern Cryptography”, Taylor & Francis, 2008 and hand-outs.
Examination
Graded home work exercises / oral exam