Program

Registration 14:00 - 14:30

Ngoc Khanh Nguyen

Practical Anonymous Credentials From a New Family of Lattice-Based Assumptions (Slides) 

We present a framework for building practical anonymous credential schemes based on the hardness of lattice problems. The security of our scheme is based on a new family of lattice assumptions which roughly states that given short pre-images of random elements in some set S, it is hard to create a pre-image for a fresh element in such a set. We show that if the set admits efficient zero-knowledge proofs of knowledge of a commitment to a set element and its pre-image, then this yields practically-efficient privacy-preserving primitives such as blind signatures, anonymous credentials, and group signatures. We propose a candidate instantiation of a function from this family which allows for such proofs and thus yields practical lattice-based primitives.

Maxime Plançon

New techniques in masking, and applications towards efficient side-channel protection of post-quantum algorithms (Slides)

Is there such a thing as "post-quantum masking" ? Not all cryptographic algorithms are equal when it comes to side-channel countermeasures. The cost of securing a grey-box implementation (in which the adversary has access to leakage from the internal state) is not a simple overhead factor on the black-box implementation, but depends on the circuit itself and on the techniques available to mask it. This is also true for post-quantum algorithms on the verge of large scale deployment.

In this talk, I will present a recent work (eprint 2022/1540 appearing a weak later at Asiacrypt 2023), aiming at taking advantage of the extra available structure from the ring/field on which the circuit is defined. The talk is supposed to be self-contained and require no prior knowledge on side-channel attacks or masking.

I will then give an overview of the practical impact of this new masking framework for post-quantum cryptography. This impact mostly depends on the suitability of the underlying algebraic structure of the post-quantum algorithm. I will focus on the cyclotomic rings over which Kyber and Dilithium are defined, and present the challenges that remain open toward obtaining side-channel-secure and efficient concrete implementations of the latter algorithms.

Coffee Break 16:30 - 17:00

Irene Villa 

On some cryptographic properties of Boolean functions (Slides)

Modern cryptography is deeply founded on mathematical theory and vectorial Boolean functions play an important role in it. In this context, some cryptographic properties of Boolean functions are defined, that evaluate the quality of the cryptographic algorithm in which the functions are implemented. In this talk, we will focus on the differential uniformity and the boomerang uniformity, properties connected to the differential attack and the boomerang attack, well-known attacks on block ciphers. We will describe these properties and present some related results.

Paolo Santini [canceled]

Recent advances in signatures from the code equivalence problem

The problem of determining whether two linear codes are equivalent is called Code Equivalence Problem. When codes are endowed with the Hamming metric (which is the most studied case), the problem normally goes by the name of Linear Equivalence Problem (LEP); LEP has been used to design the NIST candidate LESS. In the panorama of code-based cryptography, the code equivalence problem exhibits some unusual properties (e.g., a description as a non-commutative, transitive group action) which allow for new possibilities, such as signatures from a Sigma protocol or competitive signatures with advanced functionalities. This talk is aimed at recalling the main properties of the code equivalence problem and its usage in cryptography, with a special focus on recent advances and open questions.

Silvia Sconza  

Knot-based Key Exchange protocol

In this talk, we propose a new key exchange protocol based on the Generalised Diffie-Hellman Key Exchange. In the latter, instead of using a group-action, we consider a semigroup action on a finite set. In our proposal, the semigroup is the set of oriented knots with the operation of connected sum. As a semigroup action, we choose the action of the semigroup on itself through the connected sum. For the protocol to work, we need to use knot invariants, which allow us to create the shared secret key starting from the same knot represented in two different ways.  The security of the protocol is guaranteed by the hardness of decomposing knots in the semigroup. This is a joint work with Arno Wildi.

Coffee Break 10:50 - 11:20

Federico Pintore

Old and new approaches for the cryptographic supersingular random-sampling problem (Slides)

The currently best-known method to sample supersingular elliptic curves over a given finite field (SRS problem) combines the reduction of a suitable complex-multiplication elliptic curve and a random walk over some supersingular isogeny graph. Unfortunately, this method is not suitable for several cryptographic applications, as they require the endomorphism ring of the generated curve to be hard to compute. This has led to the formulation of a variant of the SRS problem, named cryptographic supersingular random-sampling problem (cSRS). This problem has recently puzzled researchers in isogeny-based cryptography, and it has not witnessed substantial improvements. In this talk, known approaches will be surveyed and new possible directions will be discussed.

Lunch Break 12:10 - 14:00

Giulia Gaggero

MinRank Problem - SupportMinors Modeling (Slides)

The MinRank Problem is the computational problem of finding a low rank linear combination of a set of matrices. There are several cryptographic attacks that can be reduced to MinRank. During this talk I will introduce a recent approach to the problem: the SupportMinors Modeling. We will discuss the modeling itself and the euristics that the authors made in order to estimate the complexity.

Sriram Gopalakrishnan 

Complexity aspects of Gröbner basis attacks on multivariate post-quantum cryptosystems (Slides)

In this talk, we investigate the complexity of computing Gröbner bases of the polynomial systems encountered in several state-of-the-art multivariate cryptosystems. We focus in particular on those cryptosystems for which key recovery can be reduced to an instance of the MinRank problem. Using the minors modeling, solutions to the MinRank problem correspond to solutions of a determinantal polynomial system. Exploiting existing theory about these determinantal systems we introduce new F5-type criteria which can be used to avoid performing useless computations when computing Gröbner bases for these determinantal systems. All arithmetic operations performed by these algorithms occur when echelonizing matrices over finite fields. Therefore, by analyzing the structure of the specific matrices encountered when solving determinantal systems, we provide sharp complexity upper bounds for these refined algorithms. Additionally, by carefully analyzing the structure of the output Gröbner bases of these determinantal systems, we are able to obtain theoretical lower bounds on the complexity of computing Gröbner bases of determinantal systems in specific situations and under suitable genericity assumptions. In comparing our upper bounds to our theoretical lower bounds, we find that our refined algorithms run in subquadratic arithmetic complexity. We conclude by discussing the consequences of these new algorithms and analyses for the security of the corresponding cryptosystems.