Program

Registration 14:00 - 14:30

Violetta Weger 

What is going on in the on ramp call? 

The need to transition to post-quantum cryptography is one of the most pressing challenges cryptography is facing since decades. While NIST and other national agencies across Europe seem to have settled for KEMs, the quest for signature schemes is still ongoing. In fact, the standardization in 2016 has only lead to three passable solutions, none of which is code-based. The two main approaches on constructing code-based signature schemes either lead to huge key sizes or huge signatures, with no solution in sight for decades. In the on ramp standardization call of 2023, however, 11 out of the 40 submissions are based on coding theory. This perfectly mirrors how much the field has changed since the first call. In fact, only one of the submissions is based on the classical decoding problem. In this talk, I will present the two construction approaches and the novel technique which shifted the panorma of signatures drastically: MPCitH, which by now is considered as third approach. We then dive into the vast pool of new code-based problems which are used in the proposals. Our main focus will be on the scheme CROSS, as it is a perfect example of how versatile coding theory is in providing new problems to give efficient cryptographic solutions.

Abhinaba Mazumder

On Code Equivalence (Slides)

While not NP-Hard, the equivalence of linear codes is a hard-ish problem that has been utilised by cryptosystems such as LESS, amongst others. Fundamentally, it asks whether we can find a specific kind of map between two codes we know to be equivalent. There are two types of equivalence problems, namely the Linear Equivalence Problem (LEP) and the Permutation Equivalence Problem (PEP). For random codes, PEP can be reduced to the well-known and widely studied graph isomorphism problem, which can be solved in quasi-polynomial time by Babai's algorithm. We can also reduce LEP to PEP in fields with q<5. For all other instances, however, the problem has resisted attempts to weaken it. In this talk, I will give a more detailed overview of the problem and all its intricacies, along with a discussion on the ongoing attempts, by me and my colleagues, to tackle the non-trivial instances of the code equivalence problem.

Coffee Break 16:15 - 16:45

Giuseppe D'Alconzo 

On the Sample Complexity of Code Equivalence Problems (Slides)

An equivalence problem asks, given two "equivalent objects", to find the map leading to the equivalence. Recently, hard equivalence problems have gained a lot of interest since, among other applications, they are used in three proposals for NIST's call for post-quantum digital signatures, namely LESS, MEDS, and ALTEQ. In this talk, we analyze the t-sample complexity of an equivalence problem: given t pairs of objects linked by the same map, what is the complexity of retrieving the equivalence? We study the sample complexity of some problems from linear codes and tensors. Moreover, we show that some known constructions from this class of problems are insecure, as they rely on more advanced cryptographic assumptions involving a polynomial t-sample complexity.

Alex Pellegrini 

Streamlining higher-genus McEliece (Slides)

This talk investigates an approach that aims at increasing the security of the McEliece cryptosystem by introducing more errors into the ciphertexts. In fact, the best attacks known against the McEliece cryptosystem have cost growing exponentially with the number of errors corrected by the error-correcting code used in the cryptosystem. One can modify the cryptosystem to asymptotically increase this number of errors, for the same key size and the same ciphertext size, by generalizing classical binary Goppa codes to subfield subcodes of algebraic-geometry codes, and then moving from genus 0 to higher genus. This talk describes streamlined algorithms for code generation and decoding for a broad class of these codes, including the codes that appear most relevant to cryptography. A notable feature of this work's algorithms is the use of arithmetic on the Jacobian variety of the underlying curve to simplify decoding.

Social Dinner: Ristorante I Tre Merli Porto Antico

Morten Øygarden 

Gröbner Basis Attacks Against New Problems in Cryptography (Slides)

Gröbner basis computation is one of the most efficient tools for solving a system of multivariate polynomial equations. Indeed, attacks based on theses techniques have a long and successful history in multivariate cryptography. Recent years have furthermore seen a surge in new encryption and hash functions designed to be efficient in the settings of Multiparty Computation (MPC), Fully Homomorphic Encryption (FHE) and Zero-Knowledge (ZK) proofs. One particular example is encryption functions that form vital components for post-quantum signature schemes based on the MPC-in-the-head paradigm. Common to all these encryption and hash functions is a distinct algebraic composition, which makes them potentially vulnerable to Gröbner basis attacks. In this talk I will give a brief overview of these MPC-/FHE-/ZK-friendly primitives, and give examples of how Gröbner basis attacks have proved to be remarkably efficient in this setting. Finally, I will discuss some of the numerous open problems regarding cryptanalysis in this area.

Coffee Break 10:50 - 11:20

Rocco Mora

The Regular Multivariate Quadratic Problem (Slides)

In this talk, we introduce a new NP-complete variant of the multivariate quadratic problem. The computational challenge involves finding a solution to an algebraic system that meets the "regular" constraint, meaning that each block of the solution vector contains only one nonzero entry. Following this, we adapt and compare various techniques of cryptanalysis to study the asymptotic complexity of the average instance.

Lunch Break 12:10 - 14:00

Ryann Cartor

MinRank Attacks in Multivariate Cryptography (Slides)

As quantum computing advances, multivariate and rank-metric code-based schemes have gained attention as viable security options. But, these schemes are vulnerable to MinRank attacks, which have exposed critical security flaws. The MinRank problem, central to these attacks, has been effectively used to break several prominent cryptosystems. This presentation will offer an introduction to these cryptosystems, and examine two distinct MinRank-based attacks on the multivariate encryption scheme HFERP, offering new insights into cryptanalytic techniques and their implications for the future of post-quantum cryptography. The discussion highlights the necessity of continuous cryptanalysis and innovation in developing quantum-resistant cryptosystems.

Simona Samardjiska 

The tensor isomorphism problem in cryptography

In the past few years, there has been an increased interest in hard equivalence problems, especially with NIST's announcement of a fourth round for new designs of digital signatures. 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 (Patarin '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. In this talk I will unite these problems under the hood of the Tensor Isomorphism problem. I will consider its theoretical and practical hardness, the state-of-the-art algorithms for solving them, as well as some pen questions that could help better understand the complexity of this problem.