Category: Uncategorized

The advent of blockchain protocols such as Bitcoin has ignited much excitement, not only for their realization of novel financial instruments, but also for offering alternative solutions to classical problems in fault-tolerant distributed computing and cryptographic protocols. Underlying many of such protocols is a primitive known as “proof of work” (PoW), which for over 20 years has been liberally applied in the cryptography and security literature to a variety of settings, including spam mitigation, sybil attacks, and denial of service protection; its role in the design of blockchain-based protocols, however, is arguably its most impactful application. At a high level, the way PoWs enable such protocols is by slowing message passing for all parties indiscriminately, thus generating opportunities for honest parties’ views to converge, under the assumption that their aggregate computational power exceeds that of the adversary.

In this talk we discuss the evolution of our understanding of the PoW primitive, where pinning down the exact properties sufficient to prove the security of the protocols they enable has been elusive. We first identify such properties, and then construct a protocol whose security can be reduced to them in the standard model, assuming a common reference string (CRS). All previous protocols rely on the “random oracle” methodology. Second, regarding the realizability of important problems in distributed computing and cryptographic protocols, such as Byzantine agreement and secure multiparty computation, we show how this type of primitive allows us to realize them in the presence of a higher number of corrupted parties and weaker setup assumptions. We resolve this apparent contradiction with a new paradigm we call “Resource-Restricted Cryptography,” which hints at “how to do cryptography when cryptography is not possible.”

Titre: Quantum state synthesis complexity classes

Abstract: Quantum state synthesis problems can be
seen as the quantum analog of functional problems
of generating a solution to a problem, and not only
to decide its acceptance. Studying these problems
as complexity classes is very recent (2022), and
the results tend to prove that quantum state synthesis
complexity classes have similar relationships between
themselves as their equivalent quantum decision classes.
The quantum aspect requires new parameters and adds
constraints that make these questions non-trivial,
contrary to the classical settings case.

Slides:

Titre: Bell theorem and its generalization: From foundations
to applications

Abstract: Quantum correlations are obtained when
multiple parties perform independent measurements
on a shared quantum state.  Bell’s seminal theorem 
proves that certain correlations predicted by quantum
theory resist explanations in terms of any Local Hidden
Variable theory based on shared randomness. I’ll first
review the Bell theorem. Then, some of its foundational
main consequences (e.g., no “reasonable” theory of
information replacing quantum information theory can
allow for cloning of information) and some of its concrete
applications (e.g., device independent cryptography).
At last, I will discuss recent generalization of this theorem 
in the context of causal quantum networks, in which
multiple parties perform independent measurements
on several, independent quantum states. In particular,
I’ll show that Real Quantum Theory (the information theory 
obtained replacing complex by real numbers in standard
Quantum Information Theory) can be ruled out by
a Bell-like experiment.

Slides:

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:

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.

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:

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:

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:

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:

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: