Author: Thomas DEBRIS

Title: On the (in)security of ROS

Abstract: Schnorr’s (blind) signatures, proposed more
than 30 years ago, have been the foundation for dozens
of cryptographic protocols of today, such as multisignatures,
threshold signatures, zero-knowledge protocols, e-cash,
and electronic voting systems. Most of these protocols,
when concurrent executions are allowed, hinge on 
a cryptographic assumption called ROS, whose hardness
was already debated by Schnorr himself (Schnorr’01).
In this talk, we present an algorithm solving the ROS 
(Random inhomogeneities in a Overdetermined Solvable
system of linear equations) problem in polynomial time
for $\ell > \log p$ dimensions. Our algorithm can be combined
with Wagner’s attack and leads to a sub-exponential solution
for any dimension $\ell$ with best complexity known so far.
Our algorithm leads to practical attacks against a number
of constructions proposed in the literature. 

Joint work with Fabrice Benhamouda, Tancrède Lepoint, 
Julian Loss, and Mariana Raykova.
Suggested reading: https://ia.cr/2020/945.

Title: Computing isogenies — part I modular equations

Abstract: We explain the methods used to compute
modular equations of large degree, for use in the SEA
algorithm. We also give some details on how to find
the isogenous curve required in the algorithm.

Title: Computing isogenies — part II the Charlap-Coley-Robbins
Polynomials

Abstract: We give properties of CCR polynomials,
an alternative to classical modular polynomials,
with interesting algebraic properties.

Slides:

Title: Codes et courbes modulaires

Abstract: Résumé. Cet exposé est une version courte du
mini cours que j’ai donné à ACT Zurich l’été dernier. Le but
est de présenter les grandes lignes de la preuve historique
du théorème de Tsfasman Vladut et Zink montrant qu’il
existe des suites de codes dont les paramètres
asymptotiques battent ceux des courbes modulaires.

Slides:

Title: Hull attacks on the Lattice Isomorphism Problem

Abstract: The lattice isomorphism problem (LIP) asks
one to find an isometry between two lattices. It has
recently been proposed as a foundation for cryptography
in independent works. This problem is the lattice variant
of the code equivalence problem, on which the notion of
the hull of a code can lead to devastating attacks.
In this talk I will present the cryptanalytic role of an
adaptation of the hull to the lattice setting, which we call the
s-hull. Specifically, we show that the hull can be helpful
for geometric attacks: for certain lattices the minimal
distance of the hull is relatively smaller than that of the
original lattice, and this can be exploited. The attack cost
remains exponential, but the constant in the exponent is halved.
Our results suggests that one should be very considerate
about the geometry of hulls when instantiating LIP for
cryptography. They also point to unimodular lattices as attractive
options, as they are equal to their own hulls. Remarkably,
this is already the case in proposed instantiations,
namely the trivial lattice Z^n and the Barnes-Wall lattices.

Slides:

Title: Correlated Pseudorandomness from the Hardness
of the Quasi-Abelian Decoding Problem: the MPC
perspective.

Abstract: Secure multiparty computation relies on a
reliable source of correlated randomness to achieve
better efficiency. Recently, Boyle et al. explained how
correlated randomness can be generated by pseudorandom
correlation generators (PCGs). We construct PCGs for
random oblivious linear evaluation (OLE) correlation,
using a new assumption, the quasi-abelian syndrome
decoding problem (QA-SD). Furthermore, our PCG is also
said to be programmable and can be used to generate
multiparty correlated randomness to be used in silent
secure N -party protocols. Previous works constructed
very efficient (non-programmable) PCGs for correlations
such as random oblivious transfer but were less satisfying
in the case of the OLE. Using our new PCGs, we obtain the
first efficient n-party silent secure computation protocols
for computing general arithmetic circuit over F_q for any q>2.
I will explore how correlated randomness helps in multiparty
computation and explain the different tools we used to finally
conclude with the construction of our PCGs.

Title: Cohomologie étale des courbes et comptage de
points sur les surfaces

Abstract: L’algorithme de Schoof permet de compter
les points d’une courbe elliptique sur un corps fini de
caractéristique p en temps polynomial en log(p). C’est
une instance particulière d’une stratégie plus générale
envisagée pour compter les points sur n’importe quelle
variété, consistant à calculer l’action de Frobenius sur
des groupes de cohomologie étale. Dans cet exposé,
j’expliquerai ce qu’est la cohomologie étale des courbes,
je décrirai un algorithme pour la calculer et présenterai
les obstacles restant à surmonter pour en déduire une
méthode efficace de comptage de points sur les surfaces.

Title: Linear-map Vector Commitments and their Practical
Applications

Abstract. Vector commitments (VC) are a cryptographic
primitive that allows one to commit to a vector and then
“open” some of its positions efficiently by showing a small
proof. Vector commitments are increasingly recognized as
a central tool to scale highly decentralized networks of
large size and whose content is dynamic. 
In this talk, we study a generalisation to linear-map openings
for vector commitments (LVC) and examine the demands
on the properties that a vector commitment should satisfy
in the light of the emerging plethora of applications: updatability
for commitments and openings, unbounded aggregation for
openings, linear homomorphism, and maintainability for stored
proofs of opening.  
We propose new constructions that improve the state-of-the-art
in several dimensions and offer new trade-offs. We first present
two pairing-based VC constructions that allow openings to inner
products IP based on the properties of monomial and Lagrange
polynomial basis. Then extend them to generic LVC via aggregation. 
Secondly, we show how to build a tree-based maintainable VC
scheme that can be instantiated from any underlying VC scheme
with homomorphic proofs of opening. We show how to achieve
a stronger, more flexible form of maintainability: our schemes
allow us to arbitrarily tune the memory used to save on the
opening time to obtain the desired trade-off.
Our focus is on building efficient schemes that do not require
a new trusted setup (we can reuse existing ceremonies for other
pairing-based schemes, such as “powers of tau” run by real-world
systems such as Zcash or Filecoin) and add maintainability to
existing VC or membership proofs (e.g. to Caulk).
We then show how these properties can be useful in the practical
setting of stateless cryptocurrencies, a payment system based
on a distributed ledger where neither validators of transactions
nor system users need to store the full ledger state. 

Slides:

Title: Cryptographic Smooth Neighbors

Abstract: We explore the number-theoretic problem
of finding two large and consecutive smooth integers
(which we call smooth twins). This has been the subject
of many recent isogeny-based cryptosystems whereby
finding parameters is related to this problem. Despite
the simplicity of the problems description, it is actually
not easy to find these integers. This is in large part due
to the fact that, for a smoothness bound B, there are
finitely many B-smooth twins. So extracting these
smooth twins from a large set is very difficult.
We revisit this problem by giving an optimised
implementation of the Conrey-Holmstrom-McLaughlin
“smooth neighbors” algorithm. While this algorithm
is not guaranteed to return the complete set of
B-smooth twins, in practice it returns a very close
approximation to the complete set, but does so in a tiny
fraction of the time of its exhaustive counterparts.
We exploit this algorithm to find record-sized
solutions to the pure twin smooth problem.
Additionally, we present a new general method for
finding smooth twins that draws inspiration from
the probabilistic methods that have been presented
in the literature. One can view this new method has
a hierarchy of the known methods since they appear
as a special case of this more general framework.
Subsequently, we use the twins that were found from these
computations to produce cryptographic parameters for the
isogeny-based signature scheme SQISign which requires a
slightly modified setup compared to the pure twin smooth
problem. In particular, the corresponding computable
isogeny degrees within our NIST-I parameters are
significantly smoother than that of prior work. In addition
we propose the first parameter sets geared towards
efficient SQISign instantiations at NIST’s security
levels III and V.

Slides: