Juan Garay, March 12, Cryptography in the Blockchain Era

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.”

November 21, 2023. Hugo Delavenne

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.


May 30, 2023. Marc-Olivier Renoux

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.


May 23, 2023. Michele Orrù

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 BenhamoudaTancrède Lepoint
Julian Loss, and Mariana Raykova.
Suggested reading: https://ia.cr/2020/945.

May 09-16, 2023. François Morain

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

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


April 11, 2023. Alain Couvreur

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.


April 04, 2023. Shane Gibbons

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.


March 21, 2023. Clément Ducros

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

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.

March 14, 2023. Christophe Levrat

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.

March 07, 2023. Anca Nitulescu

Title: Linear-map Vector Commitments and their Practical

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.