Place : LIX, Salle Philippe Flajolet.

Title: Nearly linear time encodable codes beating the Gilbert-Varshamov bound.

Place : LIX, Salle Henri Poincaré.

Title : Un algorithme géométrique efficace pour le calcul d’espaces de Riemann-Roch.

Abstract : Le calcul effectif de bases d’espaces de Riemann-Roch intervient dans de
nombreux domaines pratiques, notamment pour l’arithmétique dans les jacobiennes
de courbes ou pour la construction de codes correcteurs d’erreurs
algébraico-géométriques. Nous proposons une variante probabiliste de type Las
Vegas de l’algorithme de Brill et Noether décrit par Goppa pour le calcul d’une
base de l’espace de Riemann-Roch L(D) associé à un diviseur D sur une courbe
plane projective C de degré d définie sur un corps parfait K suffisamment
grand. On prouve que sa complexité (estimée par le nombre d’opérations
arithmétiques dans le corps K) est en O(max(d^(2 \omega), deg(D_+)^(\omega)))
où \omega est la constante de l’algèbre linéaire et D_+ est le plus petit
diviseur effectif supérieur ou égal à D. Cet algorithme probabiliste peut
échouer, mais sous quelques conditions on prouve que sa probabilité d’échec est
bornée par O(max(d^4,deg(D_+)^2)/|E|) où E est un sous ensemble fini de K dans
lequel on peut choisir des éléments de K uniformément aléatoirement. Nous avons
implémenté cet algorithme en C++/NTL et nous présenterons des résultats
expérimentaux qui semblent indiquer une amélioration des temps de calculs par
rapport à l’implémentation dans le logiciel de calcul formel Magma.

Travail commun avec Pierre-Jean Spaenlehauer.

Place : LIX, Salle Henri Poincaré

Titre : Compressing Vector OLE

Abstract : Oblivious linear-function evaluation (OLE) is a secure
two-party protocol allowing a receiver to learn any linear combination
of a pair of field elements held by a sender. OLE serves as a common
building block for secure computation of arithmetic circuits,
analogously to the role of oblivious transfer (OT) for boolean circuits.
A useful extension of OLE is vector OLE (VOLE), allowing the receiver to
learn any linear combination of two vectors held by the sender. In
several applications of OLE, one can replace a large number of instances
of OLE by a smaller number of long instances of VOLE. This motivates the
goal of amortizing the cost of generating long instances of VOLE.

We suggest a new approach for fast generation of pseudo-random instances
of VOLE via a deterministic local expansion of a pair of short
correlated seeds and no interaction. This provides the first example of
compressing a non-trivial and cryptographically useful correlation with
good concrete efficiency. Our VOLE generators can be used to enhance the
efficiency of a host of cryptographic applications. These include secure
arithmetic computation and noninteractive zero-knowledge proofs with
reusable preprocessing.

Our VOLE generators are based on a novel combination of function secret
sharing (FSS) for multi-point functions and linear codes in which
decoding is intractable. Their security can be based on variants of the
syndrome decoding assumption over large fields that resist known
attacks. We provide several constructions that offer tradeoffs between
different efficiency measures and the underlying intractability assumptions.

Toward the end of the talk, I will also discuss exciting recent
developments of this work regarding the compression of more general
(pseudo)random bilinear correlations.

Antonin Leroux, 13:30, élève école

Efficient Proactive Multi-Party Computation

Secure Multi-Party Computation (MPC) allows a set of “n” distrusting
parties to compute functions on their private inputs while guaranteeing
secrecy of inputs while ensuring correctness of the computation. Most
MPC protocols can achieve such security only against a minority of
corrupted parties (e.g., there is an honest majority > n/2). Based on
cryptographic assumptions, security against dishonest majorities can be
obtained but requires more computation and communication. These levels
of security are often not sufficient in real life especially threats
that require long-term security against powerful persistant attackers
(e.g., so called Advanced Persistent Threats). In such cases, all the
parties involved in the protocol may become corrupted at some point.
Proactive MPC (PMPC)aims to address such mobile persistent threats; PMPC
guarantees privacy and correctness against an adversary allowed to
change the set of corrupted parties over time but that is bounded by a
threshold at any given instant. Until recently, PMPC protocols existed
only against a dishonest minority. The first generic PMPC protocol
against a dishonest majority was introduced in a recent work to be
presented in September 2018, it presents a feasibility result
demonstrating that it can be achieved but with high communication
complexity: O(n^4).

This talk presents our most recent work which develops an efficient
generic PMPC protocol secure against a dishonest majority. We improve
the overall complexity of the generic PMPC from O(n^4) to O(n^2)
communication. Two necessary stepping stones for generic PMPC are
Proactive Secret Sharing (PSS) and a secure distributed multiplication
protocol. In this work we introduce a new PSS scheme requiring only
O(n^2) communications. We also present a multiplication protocol against
dishonest majorities in the proactive setting; this protocol introduces
a new efficient way to perform multiplication in dishonest majority
without using pre-computation.

--

Place : LIX Salle Henri Poincaré

Abstract : Supersingular isogeny-based cryptography is one of the newer families of post-quantum proposals. An interesting feature thereof is their comparatively low bandwidth occupation, which stems from the possibility of key compression. However, compression and decompression introduce a significant overhead to the overall processing cost despite recent progress. In this talk I indicate the main processing bottlenecks involved in key compression and decompression, and describe recent, substantial improvements for each of them. Some of these techniques may have an independent interest for other, more conventional areas of elliptic curve cryptography as well.

Place : LIX Salle Henri Poincaré

Abstract : Secure Multi-Party Computation (MPC) allows a set of “n” distrusting parties to compute functions on their private inputs while guaranteeing secrecy of inputs while ensuring correctness of the computation. Most MPC protocols can achieve such security only against a minority of corrupted parties (e.g., there is an honest majority > n/2). Based on cryptographic assumptions, security against dishonest majorities can be obtained but requires more computation and communication. These levels of security are often not sufficient in real life especially threats that require long-term security against powerful persistant attackers (e.g., so called Advanced Persistent Threats). In such cases, all the parties involved in the protocol may become corrupted at some point. Proactive MPC (PMPC)aims to address such mobile persistent threats; PMPC guarantees privacy and correctness against an adversary allowed to change the set of corrupted parties over time but that is bounded by a threshold at any given instant. Until recently, PMPC protocols existed only against a dishonest minority. The first generic PMPC protocol against a dishonest majority was introduced in a recent work to be presented in September 2018, it presents a feasibility result demonstrating that it can be achieved but with high communication complexity: O(n^{^4}).

Place : LIX Salle Henri Poincaré

Place : LIX Salle Henri Poincaré

Place : LIX Salle Henri Poincaré

Abstract : At CRYPTO 2017, Belaïd et al. presented two new private multiplication algorithms over finite fields, to be used in secure masking schemes. To date, these algorithms have the lowest known complexity in terms of bilinear multiplication and random masks respectively, both being linear in the number of shares d+1. Yet, a practical drawback of both algorithms is that their safe instantiation relies on finding matrices satisfying certain conditions. In their work, Belaïd et al. only address these up to d=2 and 3 for the first and second algorithm respectively, limiting so far the practical usefulness of their constructions. In this paper, we use in turn an algebraic, heuristic, and experimental approach to find many more safe instances of Belaïd et al.’s algorithms. This results in explicit instantiations up to order d=6 over large fields, and up to d=4 over practically relevant fields such as F_128.

Place : LIX Salle Henri Poincaré

Place : LIX Salle Philippe Flajolet

Abstract : Pour majorer le nombre de Fq-points d’une courbe plane C, Stöhr et Voloch ont déterminé une courbe D dont l’intersection avec C correspond exactement aux points de C dont l’image par le Frobenius appartient à leur tangente. Ceci donne une borne via la théorie de l’intersection.
On propose d’adapter cette idée à une courbe C sur une surface torique lisse. On trouve autant de courbes D qu’il y a de cartes affines sur cette surface, dont l’intersection avec C contiendrait les points rationnels sur une carte affine donnée. Cette méthode donne des majorations sur les surfaces de Hirzeburch qui raffine des bornes existantes.