(Amalia Pizarro-Madariaga)
This course starts with an introduction to the classical Diffie-Helman key exchange based on the discrete logarithm on finite groups. Elliptic curves provide the most important finite groups used for this kind of cryptographic application. After having introduced the definition of elliptic curves as well as their elementary properties, we will study the homomorphisms (also called isogenies) between elliptic curves, and describe the endomorphism rings for ordinary and supersingular elliptic curves. We will then study how isogenies are computed in practice.
(Gustavo Banegas)
The problem of finding (computing) the explicit isogeny between two isogenic elliptic curves defined on a finite field is known to be difficult (even in the presence of quantum computers) and continues to attract increasing attention from cryptographers. In this course we will present different families of cryptographic applications based on isogenies. We will first present the basic concept about the graph of isogenies, as well as isogenies walk through this graph. The main variants of cryptographic applications of isogenies (CSIDH and SQI-sign) will be presented, followed by a description of the impacts of the attack of Castryck and Decru on some of the protocols based on isogenies and how this approach even lead to faster protocols under different settings.
(Fernando Virdia)
Over the last few years, lattice-based cryptosystems have become one of the main contenders to replace systems based on discrete logarithms in a world with quantum computers. In this course we will first study how groups could be used in cryptography to agree on a common secret key (Diffie-Hellman) or to transmit a secret key (key encapsulation), and how these two approaches are related. We will then see how key encapsulation was developed in the discrete logarithm setting through the ElGammal cryptosystem. Finally, we will see how Shor's algorithm for quantum computers changed the security of cryptosystems based on the discrete logarithm problem, and how ElGammal can be adapted to work in the setting of the LWE (Learning-With-Errors) problem, leading to current lattice-based cryptosystems.
(Vanesa Daza)
In this course we will go deeper into algebraic lattices and their use in post-quantum cryptosystems. We will first study the hardness of the LWE problem and its relation to other hard problems in lattices, especially to the shortest vector problem in ideal lattices (SIVP) and lattice reductions. We will then discuss how the LWE problem in lattices can be used to obtain fully-homomorphic encryption (where computations can be performed on encrypted data), FHE in short, and the use of bootstrapping to make such a system practical. We will finish with a study of some advance topics in FHE.
(Claudio Qureshi)
In this course, we will begin with an introduction to the basic elements of coding theory: finite fields, linear codes, fundamental parameters (length, dimension and minimal distance), generating matrices, the parity control matrix and its relation to the minimal distance of a code. We will present some basic codes (parity control and Hamming codes, etc.) and introduce decoding through syndromes. We will then introduce how coding theory comes into play in post-quantum cryptography: how hard problems in coding theory can be used to replace the discrete logarithm problem and integer factorization, and a brief introduction to the McEliece scheme. For the final session, we will present some important codes used in cryptographic applications: Reed-Solomon codes (definition, construction and some of its properties and applications) and Goppa codes (definition, history, some important properties and its principal parameters), completing with a discussion of security aspects of Goppa codes for the McEliece cryptosystem.
(Valérie Gauthier)
In this course we will study in more details the interactions between coding theory and cryptography. We will start with a detailed study of the McEliece cryptosystem (how to generate keys, encrypt and decrypt), how Goppa codes play a pivotal role in this framework and how key sizes and efficiency compare to other approaches to obtain post-quantum cryptosystems. We will then look at how a study of algebraic codes can lead to variations of the McEliece cryptosystem and what attacks should be taken into accounts in this setting. Finally, we will finish the course looking at how codes can be used to obtain digital signatures and some proposed signature schemes based on this framework.
(Daniel Cabarcas)
This course starts with an introduction to public-key cryptography based on multivariate polynomials over a finite field (MPKC). We will study some historically important cryptosystems that served as a framework for later ones. This leads to a discussion on pros and cons of computing with polynomials. All MPKC is supported on the hardness of solving multivariate quadratic polynomial systems over a finite field, so, next we dive into this topic. We will study the Groebner basis algorithms for solving polynomial equations, and how it can be reduced to a linear algebra problem. We will discuss how the complexity of such algorithms has been bounded. And we will end by mentioning some other recently proposed algorithms. Next, we will introduce the digital signature scheme MQDSS. This is a Fiat-Shamir scheme, i.e. its signatures are a proof of knowledge of a solution to a mathematical problem. The main security assumption in MQDSS is the difficulty of solving random systems of multivariate quadratic equations with equal number of equations and variables. During the presentation, key concepts related to identification systems, zero-knowledge proofs and the Fiat-Shamir transformation will be addressed, with the purpose of establishing a comprehensible context for understanding the MQDSS scheme. Finally, we will examine in detail how the relevant algorithms are intertwined to generate signatures in MQDSS.
(Sofía Celi)
This course explores advanced concepts in multivariate cryptography, with a focus on constructing digital signature schemes. It is structured around three key lectures, each paired with practical exercises to solidify the material. We begin with an in-depth examination of the most well-known multivariate digital signature scheme: Oil-and-Vinegar (OV). Building on this foundation, we will explore what it means to design a signature scheme that is both safe and practical. This includes a discussion of attacks on OV, particularly the Kipnis-Shamir attack, and potential mitigations. Next, we will investigate the most prominent mitigation: the Unbalanced Oil-and-Vinegar (UOV) scheme. We will analyze why UOV is considered secure and debate whether it is practical enough for real-world applications. Finally, we will conclude with an analysis of the MAYO signature scheme, evaluating it from both security and practical perspectives.
(Daniel Escudero)
"Multiparty Computation", abreviated as MPC, is a set of tools that allow multiple participants to compute (in common) a function in a private way without revealing their inputs, but still obtaining the result. MPC has many applications in various domains, but an interesting application is something surprising that allows to construct digital signatures through a technique known as "MPC-in-the-Head" (MPCitH). In general, the necessary ingredients required to obtain digital signatures are (1) an MPC protocol, and (2) a function y=F(x) that is hard to invert. Under these conditions, the digital signatures obtained with MPCitH are proovably secure, without any additional hypothesis. In particular, if the function F is hard to invert with quantum computers, the resulting signatures will be post-quantic as well. Because of this, MPCitH has become a relevant paradigm for the design of digital signatures, giving rise to a rich set of recent works improving parameters such as the computational complexity or the size of digital signatures. As to the function F, a common and natural choice is to use a set of random multivariate quadratic polynomials. The "MQ" hypothesis establishes that those systems are difficult to invert, and the signatures obtained from these functions using MPCitH are the only signatures that are probably secure coming from MQ without any additional hypothesis. There exist other choices for the function F, giving rise to different signatures with distinct properties. The objective of this course is to present MPC in the context of MPC-in-the-Head, with a particular focus on the construction of highly efficient digital signatures from the MQ hypothesis. We will study several optimizations and concrete instances that convert MPCitH signatures in very attractive candidates for the construction of post-quantic digital signatures.