Computational Commutative Algebra and Applications to Codes & Cryptography

Speaker : Lorenzo ROBBIANO (University of Genoa,Italy,Italy)

Lecture 1: Gröbner Bases After introducing basic notions such as term orderings and leading terms, we define Gröbner bases and provide several characterizations of this concept. In particular, Buchberger's criterion allows us to formulate Buchberger's algorithm for computing Gröbner bases. Reduced Gröbner bases and the extended Buchberger algorithm form the underpinnings of many of the later applications. Lecture 2: Applications of Gröbner Bases Two types of applications of Gröbner bases are presented. The first one is based on the computation of syzygy modules via lifting of syzygies. It enables linear algebra operations with polynomial ideals and modules such as kernels and images of linear maps, as well as ideal operations such as intersections and colon ideals. The second type of applications is founded on computing elimination ideals. Among others, we discuss the computation of kernels and images of algebra homomorphisms, as well as saturation and homogenization of polynomial ideals. Lecture 3: Hilbert Functions After introducing graded rings, homogeneous ideals, and Nakayama's lemma, we present the basics of the theory of Hilbert functions and Hilbert series. Besides algorithms for computing them, we discuss their structure and basic properties. Lecture 4: Applications of Hilbert Functions The first applications of Hilbert functions we consider are the computation of important invariants such as dimension, multiplicity, and h-vectors. Then we discuss further topics where Hilbert functions play a prominent role such as Gorenstein rings and the Cayley-Bacharach property. Generalizations to affine algebras and multigraded rings round this lecture off. Lecture 5: Zero-Dimensional Ideals Based on the family of multiplication matrices, the structure of zero-dimensional algebras is analyzed in a novel way. They are decomposed into joint generalized eigenspaces and this decomposition is used to solve zero-dimensional polynomial systems. References [KR00] M. Kreuzer and L. Robbiano, Computational Commutative Algebra 1, Springer-Verlag, Berlin Heidelberg 2000. [KR05] M. Kreuzer and L. Robbiano, Computational Commutative Algebra 2, Springer-Verlag, Berlin Heidelberg 2005. [KR16] M. Kreuzer and L. Robbiano, Computational Linear and Commutative Algebra, Springer International, Cham 2016.

Speaker : Elena GUARDO (University of Catania,Italy)

Finite sets of points in projective space are fundamental objects in algebraic geometry and commutative algebra. From an algebraic perspective, they correspond to zero-dimensional radical ideals. Despite their apparent simplicity, finite sets of points encode rich combinatorial and geometric information. Their vanishing ideals I(X) capture all polynomials that vanish at the points, while the Hilbert function of I(X) describes the dimension of each graded piece of the coordinate ring, reflecting the distribution and configuration of the points. In the minimal free resolution of I(X) we can see the structure of the syzygies among the generators. The study of symbolic powers I(X)(m) versus ordinary powers I(X)m highlights the interaction between algebraic and geometric multiplicities. These algebraic invariants allow us to understand classical combinatorial configurations such as grids, star configurations of points, Fermat arrangements, and arithmetically Cohen-Macaulay (ACM for short) sets of points in (multi)projective spaces, just to cite some of them. Furthermore, they provide tools for applications in interpolation, coding theory, and algebraic statistics. The course emphasizes algorithmic and computational approaches, showing how modern techniques in commutative algebra can be applied to compute these invariants effectively. The course consists of 5 lectures. Lecture 1: Points and Vanishing Ideals Interpolation, construction of I(X), basic examples. Lecture 2: Gröbner Bases and Separators Computation of Gröbner bases for zero-dimensional ideals, standard monomials, Lagrange interpolation, separators. Lecture 3: Hilbert Functions and Fat Points Hilbert functions, minimal free resolutions, multiplicities. Lecture 4: Symbolic Powers and Asymptotic Invariants Symbolic vs. ordinary powers of I(X), containment problems, Waldschmidt constants, resurgence. Lecture 5: Applications and Open Problems Application to algebraic statistics, star and Fermat configurations, algebraic coding theory, open research directions. References [GT15] E. Guardo, E. and A. Van Tuyl, Arithmetically Cohen-Macaulay Sets of Points in P^1 × P^1. Springer Briefs in Math., Springer-Verlag, Berlin 2015 [CLS15] D. Cox, J. Little, and D. O’Shea, Ideals, Varieties, and Algorithms (4th ed.), Springer-Verlag, Berlin 2015.

Speaker : Lorenzo ROBBIANO (University of Genoa,Italy,Italy)

A poster section will be organized on Friday of the first week. The participants may share their research with others. This activity will strengthen the connection among the participants and with the instructors who are invited to provide their feedback to the posters. (At the SEAMS 2023 school, we organized in one evening a poster session, and we had a very interesting and inspiring time. We had a light dinner together and shared ideas and thoughts. It was a space where participants could freely exchange their thoughts with others, especially the experts. We printed out the posters for the participants and we even sent them the poster template a month before the school started, so they had enough time to prepare their presentations. We would like to follow the same process with this CIMPA school.)

Speaker : Lorenzo ROBBIANO (University of Genoa,Italy,Italy)

On the first Saturday, from 2:00 PM to 4:00 PM, we will hold a public talk titled "Algebra, Geometry, and Photography" given by Professor Lorenzo Robbiano, which is open to high school students, teachers, participants, and lecturers.

Speaker : Joachim ROSENTHAL (University of Zürich,Switzerland)

This course focuses on the applications of Computational Commutative Algebra to error-correcting codes. Coding theory studies algebraic, geometric, and combinatorial methods for constructing error-correcting codes that enable reliable communication and storage over noisy channels. The course starts with the basics of coding theory, providing an historical overview on block codes, convolutional codes, LDPC codes, and subspace codes. In the second part of the course, we explore the algebraic foundations of rank-metric codes, beginning with their interpretation as spaces of matrices (possibly over more infinite fields). We then introduce a natural and powerful framework for studying these codes: the ring of skew polynomials, introduced in [Ore33], non-commutative polynomials defined via a field automorphism, over a cyclic Galois field extension. In this course, we will give the basics of coding theory, providing an historical overview on block codes, convolutional codes, LDPC codes, subspace codes. In the second part of the course, we explore the algebraic foundations of rank-metric codes, beginning with their interpretation as spaces of matrices (possibly over more infinite fields). We then introduce a natural and powerful framework for studying these codes: the ring of skew polynomials, introduced in [Ore33], non-commutative polynomials defined via a field automorphism, over a cyclic Galois field extension. Lecture 1: Block Codes and Convolutional Codes In its most general setting, Coding Theory studies subsets of a vector space V over a (typically finite) field F, equipped with a distance function. The most classical case is the Hamming metric: vectors of length n over F, with distance given by the number of differing coordinates. A (linear) Hamming-metric code is then a k-dimensional subspace of F^n. Such codes are known as block codes. Beyond block codes, convolutional codes extend coding to sequences of arbitrary length via polynomial generator matrices, and are efficiently decoded by algorithms such as the Viterbi decoder, making them a cornerstone of streaming communication. Lecture 2: Low-Density Parity-Check Codes More recent advances exploit graph-theoretic structures. Low-density parity-check (LDPC) codes are defined by sparse parity-check matrices and admit efficient decoding via iterative message-passing algorithms on Tanner graphs, achieving near-capacity performance over a wide range of channels. Lecture 3: Subspace Codes In contrast to symbol-based error models, subspace codes are designed for network coding environments where information is transmitted as subspaces of a vector space. Their distance is measured in terms of the dimension of intersections, enabling robustness against packet erasures and random linear mixing (see[KK08]). Lecture 4: Rank-Metric Codes In 2008, the rank metric gained attention due to applications to network coding and the relation with subspace codes. In 1978, Delsarte introduced rank-metric codes as linear spaces of matrices over finite fields, equipped with the rank distance that measures the minimal rank of their difference (see [Del78]). Lecture 5: Gabidulin Codes Independently, in 1985, Gabidulin developed rank-metric codes from a polynomial perspective, defining them as evaluation codes of linearized polynomials over finite fields F_{q^m}, and constructing what are now known as Gabidulin codes, optimal codes with respect to the rank metric (see [Gab85]). References [Gab85] E.M. Gabidulin, Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21 (1985), 3-16. [KK08] R. Kötter and F.R. Kschischang, Coding for errors and erasures in random network coding, IEEE Transactions on Information Theory 54 (2008), 3579-3591. [Ore33] O. Ore, Theory of non-commutative polynomials, Annals of Mathematics 34 (1933), 480–508. [RS60] I.S. Reed and G. Solomon, Polynomial codes over certain finite fields, Journal of the society for industrial and applied mathematics 8 (1960), 300-304.

Speaker : Jens ZUMBRÄGEL (University of Passau,Germany)

Cryptography, literally meaning the art of secret writing, nowadays encompasses additional functionalities such as key exchange, digital signature, message integrity and many more. Our today’s digital world requires more than ever the ability to communicate securely and safely over the internet. Public-key cryptography has proven an indispensable technique for modern key management infrastructures and relies fundamentally on abstract algebra and computational number theory. In more recent years the advancements in quantum algorithms and computing facilities have led to the developments and standardisation efforts of post-quantum cryptography. Indeed, Shor’s algorithm renders widely used cryptographic primitives, such as RSA encryption and Diffie-Hellman key agreement, completely broken once a large-scale quantum computer can be built. Therefore, people have been investigating novel paradigms for designing quantum-resistant cryptosystems, of which several interesting ideas stem from problems in commutative algebra. In these lecture series we first give an overview of the principles of cryptography, and we present the major cryptographic primitives along with the state-of-the-art algorithms how to attack the underlying computational problems. We then deal with the development of post-quantum cryptosystems, which is currently a very active research area. We will focus in particular on schemes based on multivariate quadratic polynomials, and outline proposals for encryption and signature schemes along with the most important attacks. In the last part of the course we touch upon special applications of commutative algebra methods in cryptography, namely in discrete logarithm computations in small characteristic and in the computation of elliptic curves isogenies. The five-lecture course on the applications to cryptography is based on the following outline. Lecture 1. Introduction to Cryptography Short history from the ancient Egypt to world war II, general concepts such as Kerckhoffs' principle, block ciphers with the Digital Encryption Standard and the Advanced Encryption Standard, the idea of public-key cryptography, RSA encryption and signature, DH key agreement. Lecture 2. Number-Theoretic Reference Problems Short recap of computational complexity basics, RSA and the factoring problem, factoring algorithms and the quadratic sieve, DH and the discrete logarithm problem, computing discrete logarithms, the index calculus method, the number field sieve and current records. Lecture 3. Post-Quantum Cryptography and Multivariate Systems Introduction to Shor's quantum algorithm, the post-quantum standardisation process, overview of current proposals of quantum-resistant cryptosystems, multivariate quadratic polynomials, a general framework for MQ systems. Lecture 4. Algorithms for Multivariate Cryptosystems General methods for solving multivariate quadratic systems, the oil-and-vinegar method, signatures based on MQ systems, proposals in the post-quantum standardisation, some recent attacks. Lecture 5. Selected Contemporary Topics The discrete log problem in finite fields of small characteristic, why the index calculus method works so fast in this case, challenges of the descent step, algorithms involving Gröbner basis techniques, elliptic curves and isogenies, isogeny-based post-quantum cryptography, computing isogenies via modular polynomials.