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:

Title: Decoding Reed-Solomon codes by solving a bilinear system with a 
Gröbner basis approach

Abstract: Decoding a Reed-Solomon code can be modeled by a bilinear 
system which can be solved by Gröbner basis techniques. We will show 
that in this particular case, these techniques are much more efficient than 
for generic bilinear systems with the same number of unknowns and 
equations (where these techniques have exponential complexity). 
Here we show that they are able to solve the problem in polynomial time 
up to the Sudan radius. Moreover, beyond this radius these techniques 
recover automatically polynomial identities that are at the heart of improvements 
of the power decoding approach for reaching the Johnson decoding radius. 
They also allow to derive new polynomial identities that can be used to derive 
new algebraic decoding algorithms for Reed-Solomon codes. We provide
numerical evidence that this sometimes allows to correct efficiently slightly 
more errors than the Johnson radius. 

Slides:

Title: Implementing the Thull-Yap fast integer GCD algorithm

Abstract: Euclid’s algorithm is one of the oldest algorithms ever.
Its role in number theory is fundamental and its analysis has a
long and rich history too. Algorihms computing the gcd of two
intergers are quadratic in the length of the operands and are not
favoured by current processors. This led to the development of
quadratic and subquadratic binary versions that are currently
the fastest in practice.
In some cases, we need the sequence of euclidean remainders
produced by Euclid’s original approach. Fast methods exist for this
task, but they are difficult to prove and implement. The latest of
these is due to Thull and Yap and was never really implemented
efficiently. We explain how to improve this algorithm, fixing some
missing points. We detail our implementation in GMP and give
benchmarks.
We exemplify the use of the algorithm with the particular case of
Cornacchia’s algorithm that is an important piece of the Complex
Multiplication Method in primality proving with elliptic curves, which
motivated our work.

Slides:

Title: Quantum Resource Estimation

Abstract: In the last few years, quantum algorithms have been a constant
focus of study by cryptographers.
One of the main reasons is that it can break RSA and ECC. Furthermore,
Grover’s algorithm “lower” the security of the current symmetric cryptography,
namely AES. However, even if one can build a quantum computer, there are
some questions without answers, e.g., how many “quantum” resources we need
to break symmetric and asymmetric cryptography? In the talk, we will see
the basic concepts of Shor’s and Grover’s algorithm. The number of gates and qubits
necessary to break RSA, ECC, and AES.

Slides:

Title: Double-Authentication-Preventing Signatures: when you can cheat,
but better not to!

Abstract: In this talk we will introduce a cryptographic primitive known
as Double Authentication Preventing Signature (DAPS).
In a traditional signature scheme, the signer can sign whatever they
want (as far as the message is in the right message space), this can
be dramatically dangerous for some applications.
In this talk we will review these sort of applications and show how DAPS
can be useful there. The main idea of DAPS is that if the signer does not
follow the rules of the protocol, its signing key would be revealed.
The protocol is designed in a way to make the signing key precious,
such that the signer will not risk losing it.

Slides:

Title: Implicit Proofs of Membership

Abstract: Smooth Hash Proof Systems have been introduced by Cramer and Shoup to
build compact efficient CCA2 encryption in the standard model. Since
then, they found applications in a broad range of protocols from
oblivious transfer to authenticated key exchange, passing by witness
examples.
In this talk, we will start by a panorama of languages that can be
managed by such a primitive and then show how this is enough to
instantiate efficiently various primitives.
We will provide examples of such constructions first with vanilla
cryptography (elliptic curve, paillier) but also show that post-quantum
constructions can be achieved with a non-prohibitive efficiency in both
lattice and code based cryptography, widening the range of primitive
available under those hypotheses.

Slides:

Title: Quantum period finding against symmetric primitives

Abstract: Quantum period finding has a huge impact in cryptography, with Shor’s
algorithm that breaks the RSA and Diffie-Hellman protocol. 
Moreover, there are other quantum period finding algorithms that are less famous,
such as Simon’s algorithm.
I will present cryptanalysis using Simon’s algorithm, from the theory to complete
implementations in Q#, against a diverse set of symmetric constructions: the lightweight
MAC and ISO standard Chaskey, the low-latency block cipher Prince, used to encrypt
the memory in some microcontrollers, and the authenticated encryption scheme Elephant,
which is a candidate in the NIST lightweight authenticated encryption competition.

This presentation will cover content from the following articles:

 – https://eprint.iacr.org/2019/614
 – https://eprint.iacr.org/2020/919
 – https://eprint.iacr.org/2020/1418

Slides:

Title: A “FRI-like” protocol to test proximity to an algebraic geometric code

Abstract: Following Sarah’s talks, I will detail the main ideas behind the FRI
protocol (Fast reed-Solomon IOP of Proximity) to see how they can be generalized
to build a similar protocol for algebraic geometric codes.

Slides:

Title: Efficient proofs of computational integrity from code-based interactive oracle proofs.

Abstract: Proofs of computational integrity are probabilistic proofs that enable a verifier
to check the correctness of an execution of a program, without having to run the
computation again. For practical concerns, such proofs should be short, easy to
generate and fast to verify. They may also have a zero-knowledge property, meaning
that a verifier can be convinced of a correctness of a result without getting any
information on a private input of the computation.
In recent years, proof systems (e.g. probabilistically checkable proofs, interactive
proofs, zero-knowledge proofs) have seen tremendous progress, which eventually
lead to real-world widespread deployment (e.g. Zcash, StarkEx).  However, the most
commonly used general-purpose succinct non-interactive zero-knowledge proofs,
also called zk-SNARKs, requires a per-computation trusted setup to generate large
public parameters. In particular, the soundness of the scheme is compromised if
the secret hidden in the public parameters is leaked. To overcome this limitation,
several directions have been pursued with the aim to construct practical zk-SNARKs
without trusted setup. In particular, one of them relies heavily on properties
of Reed-Solomon codes, uses only lightweight cryptographic primitives and is
plausibly post-quantum secure.
In this talk, we will first review a fundamental construction of PCP-based succinct
non-interactive arguments for NP, dating back from the seminal works of Kilian and
Micali. Next, we will give an overview of how a long computation can be verified in
exponentially less time than redoing it. This practical scheme is known as STARK
and relies essentially on properties of low-degree polynomials. We will finally discuss
the problem of proximity to an error-correcting code, and how it is effectively solved
for Reed-Solomon codes.

Slides:

Title: Simultaneous Rational Function Reconstruction and applications to Algebraic Coding Theory.

Abstract: The simultaneous rational function reconstruction (SRFR) is the
problem of reconstructing a vector of rational functions with the same denominator
given its evaluations (or more generally given its remainders modulo different
polynomials).
The peculiarity of this problem consists in the fact that the common denominator
constraint reduces the number of evaluation points needed to guarantee the existence
of a solution, possibly losing the uniqueness. One of the main contributions presented
in this talk consists in the proof that uniqueness is guaranteed for almost all instances
of this problem.
This result was obtained by elaborating some other contributions and techniques
derived by the applications of SRFR, from the polynomial linear system solving to the
decoding of Interleaved Reed-Solomon codes. In this talk it is also presented another
application of the SRFR problem, concerning the problem of constructing fault-tolerant
algorithms: algorithms resilients to computational errors.
These algorithms are constructed by introducing redundancy and using error correcting
codes tools to detect and possibly correct errors which occur during computations.
In this application context, we improve an existing fault-tolerant technique for
polynomial linear system solving by interpolation-evaluation, by focusing on the related
SRFR.

Contains joint works with Eleonora Guerrini and Romain Lebreton. 

Slides: