Conference Agenda

Polynomial equations are central in algebraic geometry, being algebraic varieties geometric manifestations of solutions of systems of polynomial equations. Actually, modern algebraic geometry is based on the use of techniques for studying and solving geometrical problems about these sets of zeros. At the same time, polynomial equations have found interesting applications in coding theory and cryptography. The interplay between algebraic geometry and coding theory is old and goes back to the first examples of algebraic codes defined with polynomials and codes coming from algebraic curves. More recently, polynomial equations have found important applications in cryptography as well. For example, in multivariate cryptography, one of the prominent candidates for post-quantum cryptosystems, the trapdoor one-way function takes the form of a multivariate quadratic polynomial map over a finite field. Furthermore, the efficiency of the index calculus attack to break an elliptic curve cryptosystem relies on the effectiveness of solving a system of multivariate polynomial equations. This session will feature recent progress in these and other applications of polynomial equations to coding theory and cryptography.

The Rainbow Signature Scheme is one of the most studied multivariate signature scheme and was accepted as a second round candidate for the NIST standardization process for post-quantum cryptosystems. However, the key generation process of the first round version was not very efficient. In this talk, we present a modified version of the Rainbow key generation process, which generates a Rainbow key pair using only matrix products, and therefore is very efficient. Furthermore, our new algorithm also allows a very efficient key generation for Rainbow variants such as cyclicRainbow.

In the past few years, code-based cryptography in the rank-metric has become increasingly popular mainly because of the efficiency advantages over similar constructions in the Hamming metric and the ongoing NIST post-quantum standardization process. Several new ideas have emerged - for example, the cryptosystems based on LRPC codes follow an NTRU-like design and provide an alternative to the classical rank-based cryptosystems based on Gabidulin codes. Furthermore, the security in the rank metric is now much better understood - recently it was shown that the rank syndrome decoding problem is hard. On the other hand, the known cryptosystems do not have a reduction from the hard problem. Therefore, it is interesting not only to study the practical security of the rank syndrome decoding, but also attacks that take advantage of the particular construction of the cryptosystems. In this talk I will focus on algebraic techniques in the context of rank-based cryptography. It is known that decoding problems in rank-based cryptography can be modeled as systems of (non-linear) equations, however not much attention has been devoted to this modelling. It turns out that algebraic techniques are more powerful than previously thought. I will discuss how they can be refined and used in an unexpected way and how particular structure of the cryptosytems influences their efficiency.

We explore some of the variety of MinRank problem instances arising in post-quantum cryptography. We briefly review some prototypical applications in some of the post-quantum families of schemes, recall some of the computation techniques and summarize some of the complexity results for such instances. This talk should illustrate the landscape more closely investigated in the talks of Daniel Cabarcas and Ray Perlner.

Multivariate cryptography is the study of public-key cryptosystems based on multivariate polynomials over a finite field. Since solving a system of multivariate nonlinear polynomials over a finite field of order 2 is proven to be NP-hard, it is considered to be secure against quantum computers. Currently, most of the multivariate schemes are based on system of quadratic polynomials, mainly because of two reasons. First, they are smaller compared to higher degree constructions and hence more efficient. Second, if f is cubic, its (symmetric) differential Df(x) = f(x+a) - f(x) - f(a) is a quadratic map that preserves some of the properties of f. In quadratic constructions, one of the most successful family of attacks is the min-rank attack. It exploits the existence of low-rank linear combination of the matrices representing the quadratic forms of the public polynomials. One natural way to avoid this attack is to use cubic polynomials. This leads to several natural questions: Is there a notion of rank for cubic forms? Can we extend the min-rank attack to cubic constructions? Is the differential attack always a vulnerability for such constructions? What are the implications of low-rank cubic constructions?

In this talk, we address all these questions by taking a general perspective of cubic multivariate schemes. This is a joint work with John Baena, Daniel Cabarcas, Daniel Escudero and Javier Verbel.