# Research

I defended a PhD in Computer Science in November 2016. I work on cryptography, which intersects mathematics, computer science, and electrical engineering. My research topic is at the boundary of the first two disciplines.

Key words: crypatanalysis, public key cryptography, discrete logarithm, finite fields, number field sieve, elliptic curve signatures (ECDSA), side channel attacks, bounded distance decoding problem (BDD), public randomness generation, blockchains...

## Discrete logarithms

Cryptography is the study of techniques
for secure communication in the presence of third parties, also called
adversaries. Such techniques are detailed in cryptosystems, explaining how to
securely encode and decode messages. They are designed around computational
hardness assumptions related to mathematical properties, making such algorithms hard to break in practice
by any adversary. These protocols are based on the computational difficulty of
various problems which often come from number theory, such as integer factorization or discrete logarithms computations.
My research
topic is the study of ** discrete logarithm algorithms in finite
fields**. The uninitiated lector is kindly invited to read an introduction of the
discrete logarithm problem (DLP)
here.

### Medium and High Characteristics

Insiders could find in the
*Special Number Field Sieve* an algorithm to solve the DLP in medium and high characteristic
finite field related to pairing-based cryptography whereas the
*Multiple Number Field Sieve* works in the general medium and high
characteristic cases. A new variant of NFS has been proposed by
collegues in medium characteristic and is based on a
polynomial selection with conjugation method. Combining these
two variants, the
* Multiple Number Field Sieve with
Conjugation Method* is currently the best algorithm for all
medium characteristic finite fields.

### Small characteristic

The
*Simplified Frobenius Representation Algorithm*
permits to solve the DLP in small characteristic finite fields.
It decreases the asymptotic
complexities
of the first polynomial phases, namely the ones that recover the
discrete logarithms of the factor base elements (and of the extended
factor base as well). Even if they are asymptotically negligible with
regards to the quasi-polynomial individual logarithm phase, they are,
in practice, the major brake on discrete logarithms computations. We
illustrate the complexity lowering from
O(q^7) to
O(q^6) in the general case with a discrete logarithm record in
characteristic 3. The target finite field consists in the extension
field of degree 479 over the base field with 3^5 elements. The order
of the target field is so a 3796-bits integer - to be compared with
the previous record on characteristic 3 concerning a 1551-bits field.

### At the boundary between small and medium caracteristics

Finite fields used in pairing-based cryptography asymptotically live
at this boundary case. However the discrete logarithm problem is
very particular here, since it's the boundary of all relevant families
of
algorithms: quasipolynomial algorithms, and its ancestor the function
field sieve (FFS), together with the number field sieve (NFS) and all
its
variants. In
*Asymptotic complexities of discrete logarithm algorithms in
pairing-relevant finite fields*,
we adapt FFS to the particular case of composite extension, showing
how to lower the complexities by working in a translated field. The
whole
study of all these algorithms allows us to evaluate the security of
pairings and to give precise values for the caracteristics that permit
to achieve the highest security for the related
protocols. Surprisingly, some sparse caracteristics (as the one in BN
curves for instance) are as secure as same size caracteristics showing
no special form or structure.

## Linear algebra

Linear algebra is a widely used tool both in
mathematics and computer science, and cryptography
is no exception to this rule. Yet, it introduces
some particularities, such as dealing with
linear systems that are often sparse, or, in
other words, linear systems inside which a lot
of coefficients are equal to zero. We propose to
enlarge this notion to * nearly sparse
matrices*, caracterized by the concatenation
of a sparse matrix and some dense
columns, and to design an algorithm to solve
this kind of problems. Motivated by discrete
logarithms computations on medium and high
caracteristic finite fields, the
*Nearly Sparse Linear Algebra* briges the gap between
classical dense linear algebra problems and
sparse linear algebra ones, for which specific
methods have already been established. Our
algorithm particularly applies on one of the
three phases of the number field sieve which
precisely consists in finding a non trivial
element of the kernel of a nearly sparse matrix.

## Eclideans lattices, a useful tool

### Side-channel attack on ECDSA

ECDSA is a widely deployed signature protocol based on elliptic
curves.
Most of the known attacks using side-channels deal with potential
weaknesses in the implementation of the scalar multiplication.
When this multplication is implemented thanks to the wNAF
reprensation, the attacks are divided into two parts: first the
gathering of data through side-channels (for instance time
measurements on cache access), and then, the processing of this data
thanks to Euclidean lattice based methods. Studying in details one of
these methods called the Extended Hidden Number Problem (EHNP), we
proved how to
*recover the secret key of ECDSA with only 3
signatures*.
It was a theoretical bound already known but never achieved in
practice. Our method is faster and shows a higher probability of
success than most of previous attacks, using the same implementation
weakness.
In particular, our lattice construction allows to recover the secret
key
even with a small amount of misread digits during the side-channel
lecture
of the traces (up to 2% of misread digits).

### Discrete logarithms lattices, BDD and Minkowski's bound

The question of finding the most efficient way to pack spheres
together, for instance oranges, is quite an old problem.
Arranging the spheres so that their centers form an Euclidean lattice
helps to find solutions. In particular, for arbitrary norms and
dimensions,
being able to construct dense lattices helps to give good candidats
to this problem. However the density cannot be greater than a given number
(depending on the norm and dimension only), called Minkowski's
bound.
A similar problem, the Bounded Distance Decoding problem (BDD), is the
following: let's t be a vector space that comes from a vector v of the
lattice alterated by an error e (id est t = v + e), find v. Here,
Minkowski's bound shows we cannot decode (id est find v) beyond a
given
radius, whatever the lattice is. Yet it doesn't mean that we are able
to decode up to that radius, neither in the general case, nor for very
particular lattices.

We propose a
*concrete family of dense lattices* of arbitrary dimension n in which the lattice Bounded Distance Decoding (BDD) problem can be solved in deterministic polynomial time. This construction is directly adapted from the Chor-Rivest cryptosystem (1988). The lattice construction needs discrete logarithm computations that can be made in deterministic polynomial time for well-chosen parameters. Each lattice comes with a deterministic polynomial time decoding algorithm able to decode up to large radius. Namely, we reach decoding radius within O(log n) Minkowskiâ€™s bound, for both l1 and l2 norms.

## Randomness generation and Bitcoin

Trustworthy generation of public random numbers is necessary for
the security of many cryptographic applications. It was suggested to
use the inherent unpredictability of blockchains as a source of public
randomness. Entropy from the Bitcoin blockchain in particular has been used in lotteries and has been suggested for a number of other applications ranging from smart contracts to election auditing.
However, the
*malleability of the blockchain entropy* shows how an
adversary could manipulate these random numbers, even with limited
computational power and financial budget.

This analysis provides by the
way an illustration of generalised Dyck words.