November 8, 2018, Pierre Karpman (IMAG Grenoble) : New Instantiations of the CRYPTO 2017 Masking Schemes

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.

October 2, 2018, Jade Nardi (Université Toulouse 3) : Une méthode pour majorer le nombre de Fq points d’une courbe sur une surface torique

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.

March 26th, 2018, Katerina Mitrokotsa (Chalmers) : Outsourcing computations to a cloud that you don’t trust

Abstract: In this talk we discuss the problem of outsourcing computations to untrusted servers using homomorphic signcryption.  More precisely, we address the question of whether it is possible to homomorphically compute arbitrary functions on signcrypted data. The answer is affirmative and we propose a new cryptographic primitive, homomorphic signcryption with public verifiability and message privacy that can evaluate arbitrary circuits over signcrypted data. Public verifiability implies that anyone is able to publicly verify the validity of a message-signcryption pair. We achieve a rather strong notion of message privacy, which implies that even if we publish the pair (c_{f,y}, y), where c_{f,y} certifies y as the output of some
computation f over a dataset m (i.e., y = f(m)), no information is revealed about the data m, beyond what is revealed by y and f.
Furthermore, we give some highlights about employing this primitive in verifiable differentially privacy.

March 19th, 2018, Guénaël Renault (ANSSI): Résolution Algébrique Structurée

Lors de cet exposé, une revue de plusieurs résultats sur la résolution algébrique sera présentée.

Je montrerai comment l’utilisation des structures des données en entrée permet, dans certains cas, d’accélérer le processus de résolution.
Les problématiques traitées seront liées au calcul des racines d’un polynôme en une variable (théorie de Galois) à la recherche de ses racines entières (problèmes diophantiens) et la résolution de systèmes polynomiaux.

Une part importante de l’exposé portera sur les applications de ces résultats en cryptanalyse.

March 19th, 2018, Chitchanok Chuengsatiansup (EPI ARIC, Inria Lyon): Optimizing multiplications with vector instructions

In this talk, I will explain techniques to achieve fast and secure implementations.

I will introduce a vector unit which is a part of a CPU and ways to utilize it. I will also briefly emphasize the importance of and ways to prevent software side-channel attacks. Then, I will explain how to optimize scalar multiplication in Curve41417 and polynomial multiplication Streamlined NTRU Prime $9829^{739}$.

Karatsuba’s method play an important role in the former case, while combinations of Karatsuba’s method and Toom–Cook’s method are crucial in the latter case. Both implementations utilize the CPU’s vector unit.

February 13th, 2018, Jan Tuitman (KU Leuven): An update on p-adic point counting

Counting the number of points of an algebraic variety over a finite field, or equivalently computing its so called zeta function, is a central problem in computational number theory with applications to cryptography and coding theory. For elliptic curves and some curves of genus 2, variants of Schoof’s polynomial time algorithm can be used. For more general varieties, the best available algorithms are based on p-adic cohomology. Building on work of Kedlaya, Lauder and Harvey, over the past years we have obtained some of the best and most general algorithms of this type. The talk will give an overview of some of the recent work in this area and will be aimed at a rather general audience.

September 20, 2017, Simon Masson: Méthode GLV en dimension 4 sur les Q-courbes

On étudie une méthode de type GLV en dimension 4, basée sur des familles de Q-courbes avec un endomorphisme CM de petit degré. Par exemple, la courbe FourQ, proposée par Costello et Longa (Microsoft) et apportant 127 bits de sécurité, utilise cette méthode pour calculer efficacement [k]P. Afin d’étendre la proposition de Costello et Longa pour d’autres niveaux de sécurité, on développe des outils de recherche systématique de courbes et de construction des endomorphismes associés.

Nous obtenons une courbe apportant 254 bits de sécurité, possédant un endomorphisme agissant comme \sqrt{2} ainsi qu’un endomorphisme CM agissant comme \sqrt{-11} sur le groupe des points E(\mathbb{F}_{p^2}). On explicite et simplifie les expressions de ces endomorphismes. Le corps de définition de cette courbe possède une arithmétique efficace bien connue, qui permet d’accélérer à nouveau la multiplication scalaire.