Résumé.

L'algorithme de factorisation ECM (Elliptic Curve Method) a été introduit en 1985 par H.W. Lenstra. Il est encore le plus rapide asymptotiquement pour trouver des petits facteurs d'un nombre composé et est utilisé comme sous-routine dans l'algorithme NFS (Number Field Sieve).

Après avoir rappelé brièvement la méthode, nous nous intéresserons à la construction de courbes ayant des meilleurs résultats pour ECM, tant sur le nombres d'opérations effectuées que sur la proportion de premiers trouvés.

Nous fournissons enfin des paramétrisations nous permettant de créer des familles infinies de courbes ayant actuellement le meilleur comportement connu pour ECM.

Résumé.

Choisir une courbe elliptique pour un usage cryptographique n’est pas une tâche aussi simple qu’il n’y paraît. C’est d’autant plus vrai quand il s’agit de standardiser une courbe destinée à être utilisée par un grand nombre de systèmes et pour une longue durée. En effet, alors que les critères de résistance aux attaques classiques sont bien compris, le processus de sélection une courbe correcte est source de « malléabilité » et des doutes ont été émis sur la possibilité de manipuler ce processus afin de générer une courbe qui tomberait dans une classe faible (mais dont la faiblesse ne serait connue que d’un nombre restreint de personnes). Dans cet exposé nous nous intéresserons aux différents critères à prendre compte lors de la génération d’une courbe, que ce soit pour satisfaire les plus paranoïaques ou les plus avides de performances, et à l’assurance qu’apporte le processus sur la « non-malléabilité » de la courbe produite, mais aussi à la construction de certificats permettant de vérifier rapidement qu’une courbe a bien été générée par un processus donné.

Résumé.

Après un rappel sur le principe du chiffrement homomorphe (Fully Homomorphic Encryption, FHE) et sur son utilisation dans le cloud, nous rappellerons le modèle de chiffrement FLIP (EUROCRYPT 2016) qui minimise la croissance du bruit inhérent au FHE. Dans le chiffrement par flots FLIP, une fonction booléenne (d’un grand nombre de variables $N\geq 500$, mais très simple) filtre un registre contenant les bits de la clé secrète permutés à chaque top d'horloge par une permutation pseudo-aléatoire. L’entrée de la fonction de filtrage est ainsi à poids de Hamming constant (égal à celui de la clé), et la résistance de FLIP aux attaques classiques (celle exploitant le biais du poids, celle de Berlekamp-Massey, celle par corrélation rapide, et l’attaque algébrique) doit donc être réévaluée dans ce nouveau contexte (ce que ne fait pas l’article introduisant FLIP). Cela ouvre un nouveau champ de recherche sur les fonctions booléennes. Nous étudierons les critères cryptographiques d’équilibre, de degré algébrique, de nonlinéarité et d’immunité algébrique sous ce type de contrainte.

Résumé.

Dans cet exposé, nous nous intéressons à la délégation de calculs cryptographiques coûteux à un (unique) serveur. Plus précisément, nous étudierons le cas de l'exponentiation, qui est une opération au coeur de la grande majorité des protocoles cryptographiques. Nous montrerons des attaques sur des schémas existants qui permettent au serveur malicieux de retrouver les données secrètes du client. Nous montrerons ensuite des constructions simples et sûres pour la délégation d'exponentiation dans différents cas de figure (base secrète ou public, exposant secret ou public par exemple) qui sont optimales.

Résumé.

Ces dernières années, de nombreuses fuites de données ont fait la une des medias : Yahoo, Dropbox, MySpace, … Ce sont plusieurs centaines de millions de données personnelles qui ont ainsi été publiées par des pirates sur Internet.

Parmi ces données, on retrouve notamment des données authentificatrices comme le couple (email, mot de passe). Une grande partie des sites touchés par les fuites ne stockent pas les mots de passe de manière sécurisé. Ceci permet à un attaquant de retrouver tout ou partie des mots de passe et donc de s'authentifier sur d'autres sites en cas de réutilisation des identifiants.

Dans cette conférence et au travers d'une petite démonstration, nous verrons comment un attaquant peut retrouver des mots de passe mal sécurisés et quelques statistiques concernant les fuites récentes puis nous nous attacherons à détailler certaines contre-mesures existantes, tant au niveau des utilisateurs que du stockage.

Résumé.

In this paper, we revisit fully homomorphic encryption (FHE) based on GSW and its ring variants. We notice that the internal product of GSW can be replaced by a simpler external product between a GSW and an LWE ciphertext. We show that the bootstrapping scheme FHEW of Ducas and Micciancio (Eurocrypt 2015) can be expressed only in terms of this external product. As a result, we obtain a speed up from less than 1 second to less than 0.1 seconds. We also reduce the 1GB bootstrapping key size to 24MB, preserving the same security levels, and we improve the noise propagation overhead by replacing exact decomposition algorithms with approximate ones.

Moreover, our external product allows to explain the unique asymmetry in the noise propagation of GSW samples and makes it possible to evaluate deterministic automata homomorphically as in (ePrint 2014/283) in an efficient way with a noise overhead only linear in the length of the tested word. Finally, we provide an alternative practical analysis of LWE based scheme, which directly relates the security parameter to the error rate of LWE and the entropy of the LWE secret key.

Résumé.

Today, the web is evolving at an amazing pace with a richer, more personal and more interactive user experience. Nevertheless, modern browser technologies, which provide the beauty and power of the web, also provide a darker side, a rich ecosystem of exploitable data that can be used to build unique browser fingerprints. In this presentation, I will explain how browser fingerprinting works and detail its different use from tracking to augmenting user authentication.

Résumé.

PDF

Résumé.

A recent line of works - initiated by Gordon, Katz and Vaikuntanathan (Asiacrypt 2010) - gave lattice-based constructions allowing users to authenticate while remaining hidden in a crowd. Despite five years of efforts, known constructions are still limited to static sets of users, which cannot be dynamically updated. This work provides new tools enabling the design of anonymous authentication systems whereby new users can join the system at any time.

Our first contribution is a signature scheme with efficient protocols, which allows users to obtain a signature on a committed value and subsequently prove knowledge of a signature on a committed message. This construction is well-suited to the design of anonymous credentials and group signatures. It indeed provides the first lattice-based group signature supporting dynamically growing populations of users.

As a critical component of our group signature, we provide a simple joining mechanism of introducing new group members using our signature scheme. This technique is combined with zero-knowledge arguments allowing registered group members to prove knowledge of a secret short vector of which the corresponding public syndrome was certified by the group manager. These tools provide similar advantages to those of structure-preserving signatures in the realm of bilinear groups. Namely, they allow group members to generate their own public key without having to prove knowledge of the underlying secret key. This results in a two-message joining protocol supporting concurrent enrollments, which can be used in other settings such as group encryption.

Our zero-knowledge arguments are presented in a unified framework where: (i) The involved statements reduce to arguing possession of a {−1,0,1}-vector x with a particular structure and satisfying P⋅x=vmodq for some public matrix P and vector v; (ii) The reduced statements can be handled using permuting techniques for Stern-like protocols. Our framework can serve as a blueprint for proving many other relations in lattice-based cryptography.

Résumé.

Cryptographic algorithms are vulnerable to side channel analysis which aims to extract sensitive information from observations of the device executing the operations. Several leakage models have been introduced to better understand this threat and to build accurate and efficient countermeasures. In 2003, Ishai, Sahai and Wagner introduced the d-probing security model, in which an attacker can observe at most d intermediate values during a processing. They also proposed an algorithm that securely performs the multiplication of 2 bits in this model, using only d(d + 1)/2 random bits to protect the computation. This was an important step since the security of a full cryptographic implementation can be obtained from secure schemes for the binary multiplication and the binary addition. In this work, we study the randomness complexity of multiplication algorithms secure in the d-probing model. We propose several contributions: we provide new theoretical characterizations and constructions and new practical constructions. We start with a theoretical treatment of the subject: we propose an algebraic model for multiplication algorithms and exhibit an algebraic characterization of the security in the d-probing model. Using this characterization, we prove a linear (in d) lower bound and a quasi-linear (non-constructive) upper bound for this randomness cost. Then, we construct a new generic algorithm to perform secure multiplication in the d-probing model that only uses d + d^2 /4 random bits. From a practical point of view, we consider the important cases d < 5 that are actually used in current real-life implementations and we build algorithms with a randomness complexity matching our theoretical lower bound for these small-order cases.

Joint work with Sonia Belaïd, Fabrice Benhamouda, Alain Passelègue, Adrian Thillard and Damien Vergnaud

Résumé.

La plupart des schémas de chiffrement basés sur les codes (McEliece [1], MDPC [2] notamment) reposent sur le fait de masquer la structure du code utilisé. Pour McEliece, cela a souvent conduit à des attaques efficaces. D’autre part, introduire du bruit dans les chiffrés peut conduire à des erreurs de déchiffrement, et le fait de ne pas pouvoir diminuer arbitrairement la probabilité de mal déchiffrer peut également conduire à des attaques [3]. Dans cet exposé, je présenterai une nouvelle approche (inspirée de [4]) pour la construction de schémas de chiffrement basés sur les codes, dont la sécurité ne dépend pas de la qualité du masquage de la structure. Cette approche est instanciée en métrique de Hamming et en métrique Rang, et conduit à des cryptosystèmes relativement efficaces (respectivement HQC et RQC*). Je présenterai la réduction de sécurité de IND-CPA au problème du « syndrom decoding » de codes quasi-cycliques ainsi qu’une analyse de la probabilité d’erreur de déchiffrement pour HQC. Asymptotiquement notre approche permet d’obtenir des tailles de clés publiques en O(λ^2) pour HQC et O(λ^{4/3}) pour RQC pour λ le paramètre de sécurité. Enfin je donnerai des jeux de paramètres concrets pour différents paramètres de sécurité pour HQC et RQC.

*HQC : Hamming Quasi-Cyclic, RQC : Rank Quasi-Cyclic

[1] : Robert J McEliece. A public-key cryptosystem based on algebraic. Coding Thv, 4244:114–116, 197
[2] : Rafael Misoczki, Jean-Pierre Tillich, Nicolas Sendrier, and Paulo SLM Barreto. Mdpc-mceliece: New mceliece variants from moderate density parity-check codes. In Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on, pages 2069–2073. IEEE, 2013.
[3] : Guo, Qian and Johansson, Thomas and Stankovski, Paul. A Key Recovery Attack on MDPC with CCA Security Using Decoding Errors. 22nd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2016
[4] : Michael Alekhnovich. More on average case vs approximation complexity. In 44th FOCS, pages 298–307. IEEE Computer Society Press, October 2003.

Résumé.

Après un bref survol du passé et du présent, nous présenterons l’algorithme de factorisation de Shor, qui fonctionne dans le modèle quantique, et qui sert de motivation à une grande partie des recherches sur les ordinateurs quantiques. Nous montrerons que l’arithmétique classique peut apporter son aide à certaines parties des implantations physiques de cet algorithme.

Résumé.

In this talk, we will present a probabilistic polynomial-time reduction from the lattice Bounded Distance Decoding (BDD) problem with parameter 1/(√2·γ) to the unique Shortest Vector Problem (uSVP) with parameter γ for any γ that is polynomial in the lattice dimension n. It improves the BDD to uSVP reductions of [Lyubashevsky and Micciancio, CRYPTO, 2009] and [Liu, Wang, Xu and Zheng, Inf. Process. Lett., 2014], which rely on Kannan's embedding technique. The main ingredient to the improvement is the use of Khot's lattice sparsification [Khot, FOCS, 2003] before resorting to Kannan's embedding, in order to boost the uSVP parameter.

This is a joint work with Shi Bai and Damien Stehlé.