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.

Linearized polynomials arise naturally in various areas of finite geometry, coding theory, and cryptography. In particular, most known constructions for good codes in the rank metric arise from studying properties of linearized polynomials. In this talk we will give an overview of the applications of these polynomials, as well as recent results towards characterising their number of roots, and present some open problems.

In this talk, we present quantum algorithms for two fundamental computation problems: solving polynomial systems and optimization over finite fields. The quantum algorithms can solve these problems with any given success probability and have complexities polynomial in the size of the input and the condition number of certain polynomial system related to the problem. So, we achieved exponential speedup for these problems when their condition numbers are small. We apply the quantum algorithm to the cryptanalysis of the stream cipher Trivum, the block cipher AES, the hash function SHA-3/Keccak, the multivariate public key cryptosystems, the lattice based cipher NTRU, and show that they are secure under quantum algebraic attack only if the condition numbers of the corresponding equation systems are large.

The Minrank (MR) problem is a computational problem closely related to attacks on code- and multivariate-based schemes. The MR problem is, given m matrices and a target rank r, to determine whether there exists a linear combination of the matrices with rank at most r. The Kipnis-Shamir (KS) approach to MR is to solve the quadratic system of equations that arises from the observation that the dimension of the right kernel of a rank r matrix of size p times q is q-r by setting the entries of a kernel basis as variables. I will present some recent results on the complexity of the KS approach. I will focus on a particular set of instances that yield a very overdetermined system. I show how to construct non-trivial syzygies through the analysis of the Jacobian of the resulting system, with respect to a group of variables. The resulting complexity estimate for such instances is tighter than other approaches. For example, for the HFE cryptosystem, the speedup is roughly a square root. This talk is based on a paper by the same name with my coauthors Javier Verbel, John Baena, Ray Perlner and Daniel Smith-Tone, that appeared on PQCrypto 2019.

Rank-based cryptosystems such as the second round candidates for NIST's post-quantum standardization process, ROLLO and RQC, have a number of desirable features, such as good performance and key size while defending against all currently known classical and quantum attacks. Nonetheless, these cryptosystems, and the underlying Rank Syndrome Decoding(RSD) problem have been less studied in the literature than competing lattice and code-based cryptosystems and their underlying security assumptions. Parameters for rank-based cryptosystems are currently set using the support trapping attack of Gaborit, Ruatta, and Schrek. However, it is possible that approaches relating the Rank Syndrome decoding problem to polynomial-based approaches to solving the MinRank Problem, such as minors and Kipnis-Shamir modeling may give better cryptanalysis for some parameters. The polynomial systems arising in these cases have a number of interesting features that distinguish them from MinRank problems that arise in multivariate cryptography. In particular 1) The number of matrices is quadratic rather than linear in the dimension of the matrices, which generally results in a solving degree that is significantly higher than the degree of regularity when an algebraic approach is used and 2) There is extra structure in the MinRank instances arising from RSD due to the fact that the solution space exhibits a linear symmetry with respect to the extension field used to define the RSD problem. This allows some variables to be set for free, often reducing the complexity of the MinRank problem. This talk will explore the mathematical techniques that may be employed to give better estimates for the complexity of the RSD and related problems, and better security estimates for Rank-based cryptosystems.