October 18, 2022. Nicolas Resch

Title: Zero-Rate Thresholds and New Capacity Bounds
for List-Decoding

Abstract: It is typically desired that an error-correcting
code has the property that, so long as a codeword is not
too corrupted, it is possible to recover the codeword.
However, this unique-decoding requirement places
fairly strict limits on the tolerable noise, especially
when one is concerned with worst-case errors.
Motivated by this (as well as their numerous applications
in theoretical computer science), list-decodable codes
have been defined and studied, which informally allow
for the recovery of a short list of possible codewords
that could have led to a given corrupted codeword.
Formally, a code is called (p, L)-list-decodable if
every radius pn Hamming ball contains less than
L codewords. 

For a given alphabet size q and a list-size L, our main
contribution consists of computing the maximum value
of p for which there exist positive rate (p,L)-list-decodable
q-ary codes, a value called the zero-rate threshold.
Denoting this value by p*, we in fact show that q-ary codes
correcting p*+epsilon fraction of errors must have constant
size (i.e., independent of the codeword length); such a result
is often called a Plotkin bound. From such a result we can
then follow a classic proof template to derive other tradeoffs
between the rate and decoding-radius for list-decodable codes.

In the talk, we will see a high level overview of how one proves
a Plotkin bound, as well as an elucidation of how certain
convexity properties play an important role.

Slides:

October 04, 2022. Mathias Joly

Titre:  Les protocoles de PIR (Private Information Retrieval)
et leurs applications à la détection d’URLs malveillantes.

Résumé: Les protocoles de PIR permettent à un client de
récupérer un élément x
i d’une base de données en connaissant
l’indice i de cet élément dans la base de données, sans que les
serveurs ne puisse déterminer i. L’état de l’art des protocoles
de PIR à deux serveurs montre que le protocole de BGI16 a
les meilleurs coûts de communication et les meilleurs coûts
de calcul côté client. 

Ce protocole utilise une DPF (Distributed Point Function).
Si une Point Function est une fonction qui est nulle partout
sauf en un point a où elle vaut b, une Distributed Point Function
est un couple de fonctions pseudo-aléatoires, qui sont identiques
partout sauf en a, où faire le XOR de leurs valeurs donne b
(connaître l’une de ces fonctions ne donne aucune information
sur a ou b).

Lorsqu’un client veut se rendre sur un site web, le navigateur
doit vérifier que l’URL de ce site ne figure pas dans la liste des
URLs malveillantes connues. Pour l’instant, cette vérification
se fait par des serveurs à distance de manière non confidentielle.
Il y a-t-il un schéma qui conserve la confidentialité de l’URL et
garde un temps d’exécution acceptable ?

Je présenterai donc l’état de l’art des PIR à deux serveurs,
puis j’expliquerai comment construire une DPF ainsi qu’un protocole
de PIR avec DPF, enfin je montrerai comment appliquer ce protocole
à la détection d’URLs malveillantes.

September 27, 2022. Anaëlle Le Dévéhat

Title:  On the Higher bit Version of Approximate
Inhomogeneous Short Integer Solution Problem

Resume: We explore a bitwise modification in
Ajtai’s one-way function. Our main contribution
is to define the higher-bit approximate
inhomogeneous short integer solution (ISIS)
problem and prove its reduction to the ISIS
problem. In this new instance, our main idea
is to discard low-weighted bits to gain compactness.
As an application, we construct a bitwise version
of a hash-and-sign signature in the random oracle
model whose security relies on the (Ring)-LWE and
(Ring)-ISIS assumptions. Our scheme is built from
the hash-and-sign digital signature scheme based
on the relaxed notion of approximate trapdoors
introduced by Chen, Genise and Mukherjee (2019).
Their work can be interpreted as a bitwise optimization
of the work of Micciancio and Peikert (2012).
We extend this idea and apply our technique to
the scheme by discarding low-weighted bits in
the public key. Our modification brings improvement
in the public key size but also in the signature size when
used in the right setting. However, constructions based
on the higher-bit approximate ISIS save memory space
at the expense of loosening security. Parameters must
be set in regards with this trade-off. Finally, we combine
the higher bit approximate setting with the use of a
non-spherical Gaussian sampler as suggested by Jia,
Hu and Tang (2021) to construct a hash-and-sign signature
in the random oracle model whose security relies on the
(Ring)-LWE and (Ring)-ISIS assumptions. This helps us
understand better the higher-bit approximate setting.

Slides:

September 20, 2022. Hugo Delavenne

Title:  Vérification simultanée de preuves avec des codes de Reed-Solomon entrelacés

Resume: Les protocoles interactifs STARKs permettent à un vérifieur faible de vérifier qu’un prouveur infiniment puissant a effectué honnêtement un calcul. Cette vérification d’exécution honnête est ramenée à une vérification d’appartenance d’un certain mot à un code de Reed-Solomon. Le protocole interactif FRI permet ensuite de tester cette appartenance en temps logarithmique en la dimension du code pour le prouveur.

Les codes de Reed-Solomon entrelacés possèdent certaines propriétés semblant indiquer qu’ils pourraient donner une meilleure soundness que les codes de Reed-Solomon classiques, c’est-à-dire qu’un prouveur malhonnête aurait une plus petite probabilité de pouvoir tricher sans être detecté. Une autre motivation pour l’utilisation de ces codes est qu’en pratique de nombreux mots doivent être testés successivement, et que l’entrelacement est une technique classique dans ces cas.

Durant mon stage sous la direction de Daniel Augot j’ai tenté d’adapter les preuves existantes de soundness avec les codes de Reed-Solomon pour les utiliser avec des codes entrelacés et améliorer la soundness du protocole. J’ai pu adapter les preuves pour utiliser des codes entrelacés mais les propriétés nécessaires pour améliorer la soundness ne s’avèrent pas être exactement celles des codes de Reed-Solomon entrelacés.

Slides:

June 21, 2022. Valérie Gilchrist

Title:  An Isogeny-Based Adaptor Signature Using SQISign

Abstract: Transactions on blockchains can prove very costly,
so as a solution to avoid these large costs, schemes involving
payment channel networks have been developed. One approach
to implementing these off-chain forms of payment securely
involves adaptor signatures.

Previous work has established a generic construction of adaptor
signatures using signature schemes that satisfy a couple of key properties.

Unfortunately, not all post-quantum signature schemes satisfy these
properties, meaning more work needs to be done to develop
quantum-safe solutions. We introduce a new post-quantum adaptor
signature that uses SQISign as its underlying signature. SQISign has been
shown to be significantly faster and to require less storage than any other
isogeny-based signature, giving our construction potential for significant
improvements in the way of efficiency. We give the details of the new
scheme and detail how it can be implemented in a blockchain setting.

Slides:

May 31, 2022. Antoine Leudière

Title:  An explicit CRS-like action with Drinfeld modules

Abstract: L’une des pierres angulaires de la cryptographie
des isogénies est l’action
(dite CRS), simplement transitive,
du groupe des classes d’un ordre d’un corps
quadratique
imaginaires, sur un certain ensemble de classes d’isomorphismes
de
courbes elliptiques ordinaires.
L’échange de clé non-interactif basé sur cette action est relativement
lent (de
Feo, Kieffer, Smith, 2019) ; la structure du groupe sous-jacent
(Beullens,
Kleinjung, Vercauteren, 2019) est particulièrement
difficile à calculer. Cela
nous incite à adapter cette construction
à d’autres objets mathématiques. Dans
ce contexte, nous décrivons
une action, simplement transitive, de la jacobienne
d’une courbe
hyperelliptique imaginaire, sur un certain ensemble de classes
d’isomorphismes de modules de Drinfeld. 
Nous allons nous convaincre de la pertinence d’utiliser des modules
de Drinfeld
en lieu et place des courbes elliptiques. Cela fait, nous
décrirons certaines
propriétés de ces objets, puis notre action de groupe.
L’accent sera mis sur
son calcul effectif. Sera enfin évoquée la difficulté
algorithmique de casser
le protocole associé à cette construction ;
nous esquisserons la récente
attaque de Wesolowski.

Slides:

May 16, 2022. Maxime Romeas

Title:  A Framework for the Design of Secure and Efficient
Proofs
of Retrievability

Abstract: Proofs of Retrievability (PoR) protocols ensure
that a client can fully retrieve a large outsourced file from
an untrusted server. Good PoRs should have low communication
complexity, small storage overhead and clear security guarantees.
The focus of this talk is to design good PoR schemes with simple
security proofs. To this end, we use the Constructive Cryptography
setting by Maurer. We propose a framework for the design of
secure and efficient PoR schemes based on Locally Correctable
Codes. We give a first instantiation of our framework using the
high rate lifted codes introduced by Guo et al. We assert the security
of our PoR by solving a finite geometry problem, giving an explicit
formula for the probability of an adversary to fool the client.
Using the local correctability properties of Tanner codes, we get
another instantiation of our framework and derive an analogous
formula for the success probability of the audit.

Slides:

May 09, 2022. Joël Felderhoff

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:

April 05, 2022. Clément Ducros

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:

March 29, 2022. David Lubicz

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: