Session 1:

​

10:30-10:55

Cryptanalysis of HFEv-

Jintai Ding, University of Cincinnati, U.S.

HFEv- schemes is a multivariate scheme. It was  submitted to the NIST post-quantum cryptography competition in the name of GeMMS. It was considered a very secure though not very efficient scheme with nearly 20 years of history and it was a NIST third round PQC candidate.  In this talk,we will present the MinRank attack that breaks completely the HFEv- schemes. This work won honorable mention for the best paper award in crypto 2021.

​

11:00-11:25

A New Algebraic Approach to the Regular Syndrome Decoding Problem and Implications for PCG Constructions

Pierre Briaud, Inria, France

The Regular Syndrome Decoding (RSD) problem, a variant of the Syndrome Decoding problem with a particular error distribution, was introduced almost 20 years ago by Augot et al.. In this problem, the error vector is divided into equally sized blocks, each containing a single noisy coordinate. More recently, the last five years have seen increased interest in this assumption due to its use in MPC and ZK applications. Generally referred to as "LPN with regular noise" in this context, the assumption allows to achieve better efficiency when compared to plain LPN. In all previous works of cryptanalysis, it has not been shown how to exploit the special feature of this problem in an attack.
We present the first algebraic attack on RSD. Based on a careful theoretical analysis of the underlying polynomial system, we propose concrete attacks that are able to take advantage of the regular noise distribution. In particular, we can identify several examples of concrete parameters where our techniques outperform other algorithms.
(joint work with Morten Øygarden)

​

11:30-11:55

Refined F5 Algorithms for Ideals of Minors of Square Matrices

Sriram Gopalakrishnan, LIP6, France

Let k be a field, M an n by n matrix of linear forms over k and r<n an integer. The MinRank problem asks to compute the set of points p in an algebraic closure of k such that the evaluation of M at p has rank at most r. This set is equivalent to vanishing set of the ideal I(M,r) generated by the (r+1)-minors of M. The MinRank problem arises in effective real algebraic geometry and more recently in cryptography in pursuit of quantum safe cryptography schemes. Several post-quantum cryptosystems (e.g. HFE) rely on the difficulty of the MinRank problem.
The ideal I(M,r) cannot be generated by a regular sequence. Thus, reductions to zero appear when running the F5 algorithm to compute a grevlex Groebner basis of I(M,r), regardless of the generators chosen for I(M,r). Using results on the first syzygy module of I(M,r), we introduce a new criterion which predicts reductions to zero when computing a Groebner basis for I(M,r). We remove these reductions to zero, thereby speeding up the Groebner basis computation. Experimental data indicates an improvement on the best-known complexity bound for Groebner basis solutions to the MinRank problem. In the case r=n-2, we exploit a known free resolution of I(M,r) given by Gulliksen and Negard to refine our criterion and avoid all reductions to zero. We show that the complexity of our new algorithm improves on best-known bounds for Groebner basis solutions to the MinRank problem. This is joint work with Vincent Neiger and Mohab Safey El Din.

​

12:00-12:25

To Be Confirmed

Bo-Yin Yang, Academia Sinica, Taiwan

​

Session 2:

​

2:00-2:25

Algebraic Algorithms for Equivalence Problems

Simona Samardjiska, Radboud University, The Netherlands

In the past few years, there has been an increased interest in hard equivalence problems. On a high level, such a problem can be defined as follows: Given two algebraic objects, find, if any, an equivalence that maps one object into the other. Several instantiations have been considered for cryptographic purposes, for example - Isomorphism of polynomials (Pattarin '96), Code equivalence (Biasse et al. '20), Matrix Code equivalence (Chou et al. '22), Alternating trilinear form equivalence (Tang et al.'22), Lattice isomorphism (Ducas & van Woerden '22). All of these problems are believed to be hard even for quantum adversaries. Conveniently, they can generically be used to build a Sigma protocol and further a post-quantum secure signature using the Fiat-Shamir transform. However, their practical hardness is still not well understood, and most of the initially proposed parameters for signature schemes have been broken. In this talk, I will focus on algebraic attacks that target several of these problems. While an equivalence problem can be inherently modeled as a system of equations, the straightforward approach is not very efficient. Turns out, there exists better modeling that allows for a significantly faster algorithm. I will show the implications of this model on the above problems and the differences arising from the particularities of the problem. For example, the presented algorithm can be used to break the proposed parameters of the signature scheme of Tang et al.'22.

​

2:30-2:55

Multivariate Signature Schemes and Cryptanalysis of Early Proposals

Pierre Pébereau, LIP6, France

The difficulty of solving multivariate polynomial systems makes them an interesting candidate for post-quantum cryptography. Several signature schemes have been proposed since the nineties, and although they suffer from relatively large public keys, they yield rather small signature sizes in comparison to lattice-based contributions and competitive runtimes. As is the case for most cryptographic constructions, the polynomial systems encountered in cryptographic applications are not generic: this led to the cryptanalysis of several early proposals, in particular by Kipnis and Shamir on Oil and Vinegar, which is a special case of Unbalanced Oil and Vinegar (UOV). More recently, NIST round 3 candidates GeMSS and Rainbow turned out to be much less secure than expected, with a key recovery in the case of Rainbow. Yet UOV is still standing after two decades, despite the introduction of various attacks, such as the intersection attack of W. Beullens, the Kipnis-Shamir attack and the reconciliation attack. We design a new pre-processing for MinRank before application of Gröbner Bases algorithms, which allows us to obtain an original formulation of the Kipnis-Shamir attack on OV. We study the relevance of this approach to other post-quantum schemes, in particular multivariate and rank-metric.

​

3:00-3:25

Isogeny Graphs With Level Structure (Part 1)

Guido Maria Lido, Università di Roma Tor Vergata, Italy

A familiar object in isogeny based cryptography is the graph whose vertices are supersingular elliptic curves and whose edges are isogenies of fixed degree l. It is immediate to prove that from each vertex there are exactly l+1 outgoing edges, while it is less obvious that such a graph is connected and that it has the Ramanujan property, a property about the spectrum of the adjacency matrix that implies that random walks very soon visit all vertices with the same probability. In our talk we look at a generalization of these graphs, namely graphs whose vertices are pairs (E,T), where E is a supersingular elliptic curve and T is some information on the n-torsion of E (e.g. a basis, a point, a subgroup) for fixed n. It is easy to notice that the secret keys in SIDH are exactly walks in such generalized isogeny graph, and the public keys are vertices. These graphs can be multipartite, implying that the Ramanujan property is not always satisfied. By studying modular curves over mixed characteristic we relate isogeny graphs to geometric and cohomological objects, which allows us to prove the appropriate modification of the Ramanujan property. The properties of these generalized isogeny graphs are useful for a statistical zero knowledge proof of knowledge of an isogeny, which is part of a work with Basso, Connolly, De Feo, Fouotsa, Morrison, Panny, Patranabis and Wesolowski to generate elliptic curves with unknown endomorphisms.

​

3:30-3:55

Isogeny Graphs With Level Structure (Part 2)

Guido Maria Lido, Università di Roma Tor Vergata, Italy

A familiar object in isogeny based cryptography is the graph whose vertices are supersingular elliptic curves and whose edges are isogenies of fixed degree l. It is immediate to prove that from each vertex there are exactly l+1 outgoing edges, while it is less obvious that such a graph is connected and that it has the Ramanujan property, a property about the spectrum of the adjacency matrix that implies that random walks very soon visit all vertices with the same probability. In our talk we look at a generalization of these graphs, namely graphs whose vertices are pairs (E,T), where E is a supersingular elliptic curve and T is some information on the n-torsion of E (e.g. a basis, a point, a subgroup) for fixed n. It is easy to notice that the secret keys in SIDH are exactly walks in such generalized isogeny graph, and the public keys are vertices. These graphs can be multipartite, implying that the Ramanujan property is not always satisfied. By studying modular curves over mixed characteristic we relate isogeny graphs to geometric and cohomological objects, which allows us to prove the appropriate modification of the Ramanujan property. The properties of these generalized isogeny graphs are useful for a statistical zero knowledge proof of knowledge of an isogeny, which is part of a work with Basso, Connolly, De Feo, Fouotsa, Morrison, Panny, Patranabis and Wesolowski to generate elliptic curves with unknown endomorphisms.

​

Session 3:

​

10:30-10:55

Modular Curves Creeping Up in Isogeny Problems

Luca De Feo, IBM Research Europe, Luxembourg

After the spectacular attacks of this summer, the panorama of isogeny based cryptography has changed. One interesting take-away from the SIKE attacks and other recent result is that "torsion knowledge" matters. Although mostly ignored by cryptographers, a well established way to talk about torsion knowledge is the formalism of modular curves. I will explain how modular curves creep up in isogeny-based cryptography, and what they tell us about its security.

​

11:00-11:25

Security and Efficiency of SIDH-based Signatures

Federico Pintore, Università di Bari, Italy

The key exchange SIDH and its corresponding key encapsulation mechanism SIKE had been the flagship isogeny-based cryptosystems before the devastating attacks by Castryck, Decru, Maino, Martindale and Robert against the hard mathematical problem on which their security is based. Nevertheless, the SIDH framework can still be used to construct secure cryptosystems, as for example digital signatures. In this talk, the security and efficiency of such SIDH-based signatures will be discussed.

​

11:30-11:55

Computing Supersingular Endomorphism Rings Using Inseparable Endomorphisms

Annamaria Iezzi, Università di Napoli, Italy

Computing the endomorphism ring of a supersingular elliptic curve defined over a finite field is a relevant problem to cryptography, since the security of several isogeny-based cryptosystems reduces to it. Suppose we have an algorithm which generates random endomorphisms of a supersingular elliptic curve E defined over a finite field with p^2 elements. How many calls to that algorithm do we expect to make before finding enough endomorphisms to guarantee that they generate the endomorphism ring End(E) as a Z-order? In this talk we give a new heuristic argument that, using a particular kind of inseparable endomorphisms, this expectation is bounded by a constant, independent of p or E. Moreover we present an algorithm for computing End(E) which only relies on GRH and computes End(E) in expected O(p^(1/2+e)) time, for every e>0.

​

12:00-12:25

Faster Supersingularity Testing

Valerie Gilchrist, Université Libre de Bruxelle, Belgium

Joint work with Gustavo Banegas (Qualcomm) and Valerie Gilchrist (ULB)

Supersingular elliptic curves are ubiquitous in isogeny-based cryptography. But given some elliptic curve, how can you quickly determine whether it is supersingular or not? In this talk we will compare several approaches, and describe our implementation of a new variant of Doliskani's algorithm, with a view to fast and simple CSIDH key validation.

​

Session 4:

​

2:00-2:25

On the hardness of cryptosystems based on disguised Veronese varieties

Wouter Castryck, KU Leuven, Belgium

Recently, Alzati, Di Tullio, Gyawali and Tortora have proposed two related protocols for post-quantum key exchange. One is based on intersections of conics in A^2, the other is based on intersections of quadrics in P^3. In both protocols, non-standard Veronese varieties are used as a disguising tool. Unfortunately, while these constructions are geometrically beautiful, they are insecure: indeed, the aim of this talk is to explain how they are broken by the "Lie algebra method", which was developed in 2006 by de Graaf, Harrison, Pílníkova and Schicho. This is joint work with Alexander Lemmens.

​

2:30-2:55

Breaking the Supersingular Isogeny Diffie-Hellman Protocol

Thomas Decru, KU Leuven, Belgium

Finding an explicit isogeny between two given isogenous elliptic curves over a finite field is considered a hard problem, even for quantum computers. In 2011 this led Jao and De Feo to propose a key exchange protocol that became known as SIDH, short for Supersingular Isogeny Diffie-Hellman. The security of SIDH does not rely on a pure isogeny problem, due to certain "auxiliary" elliptic curve points that are exchanged during the protocol (for constructive reasons).

In 2017 SIDH was submitted to the NIST standardization effort for post-quantum cryptography, and since then it has attracted a lot of attention. Early July, it advanced to the fourth round. In this talk I will discuss a break of SIDH that was discovered in collaboration with Thomas Decru about three weeks later. The attack uses isogenies between abelian surfaces and exploits the aforementioned auxiliary points, so it does not break the pure isogeny problem. It allows for a full key recovery at the highest security level in a few hours. As time permits, I will also discuss some more recent improvements and follow-up work due to Maino et al. and Robert.

​

3:00-3:25

At the Evening of SIDH Attacks

Tako Boris Fouotsa, EPFL, Switzerland

In summer 2022, SIKE, SIDH and derived schemes were broken in polynomial time by a series of papers (Wouter Castryck and Thomas Decru, Luciano Maino and Chloe Martindale, and Damien Robert). In this talk, we discuss the countermeasure ideas that have appeared till date, and have a brief overview of their security.