Author: Thomas DEBRIS

Title:  NTRU et Module-uSVP de rang 2 

Abstract: The NTRU problem asks to find f and g two polynomials with small coefficients given h = g/f mod q, where all the polynomials are taken modulo some irreducible polynomial P defining a number field. This problem is a particular instance of a Shortest Vector Problem in a Module lattice of rank 2 in which there exists a particularly dense submodule of rank 1. Although NTRU has first been proposed as a security assumption by Hoffstein, Pipher and Silverman in 1998 [HPS98], its relationship to other classical module lattice problems is not yet well understood. It was proven in [PS21] that ideal-SVP reduces to average-case-NTRU, and that average-case-NTRUmod (consisting in recovering the dense rank-1 submodule of the NTRU module) reduces to decision-NTRU. In this follow-up, we consider Module-uSVP, the Module version of the unique-Shortest Vector Problem. This problem asks to find a short vector in a module lattice, provided that it contains a dense submodule of rank 1. We then propose a reduction from module-uSVP to NTRU. 

This is a joint work with Alice Pellet-Mary and Damien Stehlé.

– [HPS98] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: A ringbased public key cryptosystem. In Joe P. Buhler, editor, Algorithmic Number Theory, Lecture Notes in Computer Science, pages 267–288. Springer, 1998. 

– [PS21] Alice Pellet-Mary and Damien Stehlé. On the hardness of the NTRU problem. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2021, pages 3–35, Cham, 2021. Springer International Publishing.

Slides:

Title:  New Construction for MPC from the Variable Density Learning Parity
with Noise (LPN) assumption

Abstract: Multiparty computation (MPC) allows users to compute various
functions of their secret inputs, while ensuring that these inputs remain perfectly
hidden. In the early 2000, correlated secret randomness was shown to be a
useful resource for realizing efficient MPC protocols. Thus, many efforts have
been deployed to improve the generation of correlated randomness. I will present
a series of works that have led to the successive creation of Pseudorandom
Correlation Generators (PCGs), an analogue of pseudorandom generators,
and Pseudorandom Correlation Functions (PCFs), an analogue of pseudorandom
functions.
PCFs are a very powerful tool, but their construction is very complex. It relies on
the creation of a new weak WPRF, and on the use of a Function Secret Sharing (FSS).
The security of this new WPRF is based on a Variable Density variant of the Learning
Parity with Noise assumption called (VDLPN). In this variant, the matrix is no longer
a randomly chosen matrix, but a matrix whose density decreases exponentially. The
presentation will discuss the security proof of the WPRF, which supports the security
of our PCF.

This is a joint work with Geoffroy Couteau.

Slides:

Titre : Calcul de la représentation linéaire d’une variétés de Kummer et application au
comptage de points. 

Résumé : Dans cet exposé, on explique comment on peut calculer la représentation linéaire
de l’anneau des endomorphismes d’une variété de Kummer. La difficulté est que le point
neutre d’une variété de Kummer n’est pas lisse et nous devons passer par l’étude de son
cône tangent en 0. Nous donnons une application à l’algorithme de calcul de nombre de
points rationnels de Mestres.

Slides:

Title: On codes, and Learning with Errors over Function Fields

Abstract: In cryptography, one can often define two versions of a hard problem:
A computational version, or search version, that asks to compute something
(e.g. a discrete logarithm, a prime factor), and a decisional version, that asks to
distinguish between some specific probability distribution and the uniform.
More often, the search problem can be shown computationally hard, but the decision
version might be more difficult to handle. Informally, the hardness of the decision
version means that the distribution is pseudorandom.
In code-based cryptography, one natural search version is the decoding problem,
which has been shown to be equivalent to the decision version in the case of purely
random codes. However, it is a long standing problem to find a search to decision
reduction for structured versions of the decoding problem (e.g. the decoding of
quasi-cyclic codes). In the lattice-based setting though, such reductions have been
carried out using number fields for structured versions of the Learning With Errors
problem: Ring-LWE, Module-LWE and so on.
In this talk I will present a function field version of the LWE problem. This new
framework leads to another point of view on structured codes, strengthening the
connection between lattice-based and code-based cryptography. In particular,
it permits to obtain the first search to decision reduction for structured codes.

The framework can be instantiated with function fields analogue of the cyclotomic
number fields, namely Carlitz extensions, leading to search to decision reductions
on various versions of Ring-LPN, which have applications to secure multi party
computation, and to an authentication protocol.

This is a joint work with Alain Couvreur and Thomas Debris-Alazard.

Slides: part I ; part II

Title: Fast list decoding of algebraic geometry codes

Abstract: In this talk, we present an efficient list decoding algorithm 
for algebraic geometry (AG) codes. They are a natural generalization 
of Reed-Solomon codes and include some of the best codes in terms 
of robustness to errors. The proposed decoder follows the Guruswami-Sudan 
paradigm and is the fastest of its kind, generalizing the decoder for one-point 
Hermitian codes by J. Rosenkilde and P. Beelen to arbitrary AG codes. 
In this fully general setting, our decoder achieves the complexity 
$\widetilde{\mathcal{O}}(s \ell^{\omega}\mu^{\omega – 1}(n+g))$, where $n$ 
is the code length, $g$ is the genus, $\ell$ is the list size, $s$ is the multiplicity
and $\mu$ is the smallest nonzero element of the Weierstrass semigroup at 
some special place.

Joint work with J. Rosenkilde and P. Beelen.

Slides:

Title: Some important tools for verifiable computation: the sumcheck protocols

Abstract: In this talk, I will present a kind of verifiable computation protocol that 
is called the sumcheck protocol. The ultimate goal of the talk is to explain how 
Sarah, Daniel and I designed a multivariate version of this protocol using 
Reed-Solomon codes. To do this, I will also explain what is a verifiable computation, 
how does some previous existing sumchecks works, and where those protocols 
can be useful.

Slides:

Title: Meet-in-the-middle Attacks on Permutations: Simplified Cell-based 
Modeling and Quantum Attacks

Abstract: Meet-in-the-middle (MITM) is a general cryptanalytic technique 
where internal states are computed along two independent paths 
(‘forwards’ and ‘backwards’) and then matched. Over time, MITM attacks 
improved using more refined techniques and exploiting additional freedoms 
and structure, which makes it more involved to find and optimize them. 
This has led to the use of detailed attack models for generic solvers to 
automatically search for improved attacks.
In this paper, we propose a simple MILP modeling for MITM attacks 
on permutations, with applications to preimage attacks on hash functions. 
We benefit from a greatly simplified model and a theoretical analysis 
that, for any solution, proves the existence of a detailed attack and its 
complexity. This model yields new results on several families of constructions.
First, we improve the MITM step in distinguishers on the permutations
 of the Spongent hash functions. Second, on AES-based permutation designs,
 our model recovers the best previous results despite being much simpler. 
The only limitation is that we do not use degrees of freedom from the key 
schedule in AES-based hashing. Third, we extend the model to target more 
permutations, like Feistel networks. Here we give generic guess-and-determine 
distinguishers with complexity 1 which target up to 2/3 of the rounds of Simpira v2, 
preimage attacks on reduced versions of Simpira v2 and practical distinguishers 
on reduced-round Sparkle permutations.
Finally, we extend our model to find quantum MITM attacks, and we give several 
quantum preimage attacks on reduced-round hash functions (e.g. Haraka v2, Simpira v2).

Joint work with Marc Stevens (Cryptology Group, CWI)

Slides:

Title: Computational aspects of algebraic geometry codes.

Abstract: In this talk, we present an overview over multiple computational 
results related to algebraic geometry codes. In particular, we consider 
encoding of one-point codes over a special family of curves called 
$C_{ab}$-curves, which includes the famous Hermitian curve. In this setting, 
we take advantage of the fact that encoding problem can be reduced to the 
problem multi-point evaluation of bivariate polynomials, which we address in 
two fundamentally different ways. In the final part of the talk, we will briefly 
outline an efficient list decoding algorithm for general algebraic geometry codes.

The talk is based on results produced during the PhD studies of the speaker 
under the supervision of J. Rosenkilde and P. Beelen.

Slides:

Title: Two-dimensional implementations of quantum LDPC codes.

Abstract: Quantum LDPC codes are promising to reduce the cost of
quantum error correction but can they really be implemented with
current quantum hardware which typically look like a 2D grid of
qubits equipped with local gates? In this talk we will provide two
answers to this question. First we will discuss obstructions to local
implementation of quantum LDPC codes which suggest that quantum
LDPC are impractical with 2D local quantum hardware. Second, we
propose an implementation of quantum LDPC codes based on long-range
connections. With this design, we obtain a threshold of 0.28% for a family
of quantum LDPC codes using 49 physical qubits per logical qubit. For a
physical error rate of 10^-4, this family reaches a logical error rate of 10^-15
using fourteen times fewer physical qubits than the surface code.

Joint work with Michael Beverland and Maxime Tremblay.

Ref:  arXiv:2109.14599 and arXiv:2109.14609

Slides:

Title: Bilinear Complexity of 3-tensor Linked to Coding Theory

Abstract: A central problem in algebraic complexity theory is
the determination of the complexity, with respect to the
noncommutative model of computation, of problems that can
be modelled by bilinear forms. The bilinear complexity of an
algorithm is defined as the minimum number of non-scalar
multiplications required to execute it. Each bilinear map is
a 3-tensor, and its bilinear complexity is called its tensor rank,
which is the minimum number of rank-one matrices whose span
contains its first slice space. In 1989, H\aastad proved that
computing the tensor rank of a 3-tensor is NP-complete over any
finite field and over the rationals is NP-hard. In this talk, we present
upper bounds on the tensor rank of certain classes of 3-tensors and
give explicit constructions of spaces spanned by rank-one matrices
containing their first slice spaces. We then show how these results
can be applied in coding theory to derive upper bounds on the
complexity of a generator tensor of some rank-metric codes. In particular,
we compute the tensor rank of a family of $\mathbb{F}_q^m$-linear
codes and show that its members are extremal with respect to Kruskal’s
tensor rank bound.

Slides: