The courses

Multivariate Cryptography and Polynomial Systems

Abstract: In this course, we will give an introduction to multivariate cryptography, which is one of the main candidates for post-quantum cryptography, as well as to linear algebra-based algorithms for solving polynomial systems. In the first part, we will briefly recall the classical mathematical problems underlying public-key cryptography (factoring integers and the discrete logarithm problem) and explain the need for mathematical alternatives believed to be secure against quantum computer attacks. Multivariate cryptography is one such alternative, where security relies on the hardness of solving nonlinear multivariate polynomial systems over finite fields.

This problem is believed to be computationally hard, even for quantum computers. We will explain how basic multivariate systems are constructed, namely HFE and Oil and Vinegar, which serve as the building blocks for more advanced systems.

One of the most efficient strategies for solving multivariate polynomial systems systems is through Gröbner bases. In particular, the introduction of linear algebra-based algorithms for Gröbner basis computation has led to significant advancements. In the second part of the course, we will give a brief introduction to these algorithms and present the key concept of the solving degree, which is used to express their computational complexity. Finally, we will introduce the notions of degree fall and last fall degree, and explain their connection to the solving degree.

Prerequisites: A basic knowledge of commutative algebra (e.g., at the level of Atiyah-MacDonald's Introduction to Commutative Algebra) and computational algebra (e.g., at the level of Kreuzer-Robbiano's Computational Commutative Algebra 1). No previous knowledge of cryptography is required.

Abstract: This course focuses on Gorenstein liaison theory, an important refinement of classical liaison theory with deep connections to the geometry and algebra of projective schemes. After introducing and discussing the basic definitions, the course explores the structure and invariants of Gorenstein liaison classes. We recall the homological framework underlying Gorenstein linkage, including the use of canonical modules, local cohomology, and free resolutions to study linked ideals. A central topic is the analysis of relationships between linked ideals, especially how properties such as Cohen–Macaulayness and Hilbert function behave under G-links. We discuss the Gorenstein liaison class of a complete intersection and the main open question in this theory: when does an ideal belong to the G-liaison class of a complete intersection (glicci)? The course also addresses the interplay between Gorenstein liaison and computational methods, particularly the connection with Gröbner bases. Through explicit examples and computations, students will gain practical tools for exploring G-liaison in concrete settings. The course is complemented by tutorial sessions, during which the participants will use CoCoA to compute examples, verify some results discussed during there lectures and experiment with G-liaison.

Prerequisites: Foundations in commutative algebra, including homogeneous ideals in the polynomial ring, primary decomposition, minimal free resolutions and associated invariants, basic concepts of homological algebra. The dictionary between the language of commutative algebra and that of algebraic geometry, including projective schemes, is discussed in the first lecture. Familiarity with Gröbner bases is assumed.

Abstract: Given a polynomial ring K[x1,…,xn] over a field K, a disjoint union X={x1,…,xn} = Y∪Z, and an ideal I in K[X], the task to compute the elimination ideal I∩K[Y] has been solved classically using resultants or by calculating a Gröbner basis with respect to an elimination term ordering.

A particularly interesting case occurs when the induced map K[Y]/(I∩K[Y]) ⟶ K[X]/I is an isomorphism. In this case we say that the elimination of Z defines a re-embedding of I. In the last years a new method for finding and computing such re-embeddings, called elimination by substitution, was developed by L. Robbiano, L.N. Long, and the speaker.

In this minicourse we discuss the main steps of this new elimination technique: finding suitable candidate tuples of indeterminates Z which could possibly be eliminated, checking whether the given ideal I can be re-embedded by the elimination of Z, and computing the elimination ideal I∩K[Y]. We also present an extension of this method which uses the solution of a Unimodular Matrix Problem in order to define an isomorphism of the poylnomial ring which allows us to eliminate additional indeterminates, as well as a version of the technique for Boolean polynomial ideals which has applications in cryptoanalysis.