GREYC
Laboratoire de mathématiques Nicolas Oresme


Séminaire Cryptologie & Sécurité
Contacts :
À venir :
Des nouveaux défis cryptographiques pour les cartes à puce.

Résumé.

La carte à puce est à la base de la sécurité des systèmes informatiques. Elle a fait ses preuves dans de nombreux secteurs en tant que moyen de paiement ou d’authentification. L’objectif de cette présentation est de reconsidérer la sécurité de ces cartes face à des nouveaux modèles d’adversaires : la substitution d’algorithme et les ordinateurs quantiques. Dans un premier temps, nous nous intéresserons à la famille de protocoles sécurisés SCP (de l’anglais Secure Channel Protocols). Nous présenteront la notion des attaques par substitution d’algorithmes, qui a été développée après la révélation de Snowden. Nous montrons qu’il existe un membre de la famille SCP qui résiste aux modifications malveillantes dans les implémentations des schémas cryptographiques. Dans un deuxième temps, nous chercherons à rendre les schémas post-quantiques pratiques pour les systèmes à puissance de calcul limitée. En particulier, nous étudions l’échantillonnage de distributions gaussiennes discrètes. Il y a deux problèmes dans les algorithmes d’échantillonnage : ils ont besoin d’un espace de stockage important et/ou ils impliquent très souvent des opérations mathématiques qui ne sont pas disponibles sur les cartes comme le calcul d’une exponentielle sur des nombres réels à précision arbitraire. Nous présenterons des premiers pas vers des nouvelles approches qui sont mieux adaptées aux cartes.

[7 février 2018 | 14h | Campus II - Salle S3-351]
Passé:
Implémentation efficace de la multiplication Modulaire pour la cryptographie à clé publique de grande caractéristique.

Résumé.

Cette exposé traite l’implémentation matérielle de la méthode CIOS (Coarsely Integrated Operand Scanning) de la multiplication modulaire de Montgomery. Dans ce travail nous avons combiné cette méthode CIOS avec une architecture systolique efficace. D'après nos connaissances, c'est la première implémentation d'une telle conception. Nos architectures visaient à réduire le nombre de cycles d'horloge de la multiplication dans les corps finis. Les résultats d'implémentation proposées pour les algorithmes CIOS se concentrent sur différents niveaux de sécurité utiles en cryptographie. Cette architecture a été conçue pour utiliser le DSP48 flexible sur les FPGA de Xilinx. Nos architectures sont évolutives et dépendent uniquement du nombre et de la taille des mots. Par exemple, nous fournissons des résultats d'implémentation pour des mots de 8, 16, 32 et 64 bits en 33, 66, 132 et 264 cycles d'horloge.

[10 janvier 2018 | 14h | Campus II - Salle S3-351]
On the Ring-LWE and Polynomial-LWE Problems

Résumé.

The Ring Learning With Errors problem (RLWE) comes in various forms. Vanilla RLWE is the decision dual-RLWE variant, consisting in distinguishing from uniform a distribution depending on a secret belonging to the dual OK^vee of the ring of integers OK of a specified number field K. In primal-RLWE, the secret instead belongs to OK. Both decision dual-RLWE and primal-RLWE enjoy search counterparts. Also widely used is (search/decision) Polynomial Learning With Errors (PLWE), which is not defined using a ring of integers OK of a number field K but a polynomial ring Z[x]/f for a monic irreducible f in Z[x]. We show that there exist reductions between all of these six problems that incur limited parameter losses. More precisely: we prove that the (decision/search) dual to primal reduction from Lyubashevsky et al. [EUROCRYPT 2010] and Peikert [SCN 2016] can be implemented with a small error rate growth for all rings (the resulting reduction is nonuniform polynomial time); we extend it to polynomial-time reductions between (decision/search) primal RLWE and PLWE that work for a family of polynomials f that is exponentially large as a function of deg f (the resulting reduction is also non-uniform polynomial time); and we exploit the recent technique from Peikert et al. [STOC 2017] to obtain a search to decision reduction for RLWE. The reductions incur error rate increases that depend on intrinsic quantities related to K and f.

Based on joint work with Miruna Roșca and Damien Stehlé.

[22 novembre 2017 | 14h | Campus II - Salle S3-351]
Transfert inconscient adaptatif avec contrôle d'accès à partir d'hypothèses sur les réseaux euclidiens

Résumé.

Adaptive oblivious transfer (OT) is a protocol where a sender initially commits to a database {M_i}_{i=1}^N . Then, a receiver can query the sender up to k times with private indexes ρ_1, …, ρ_k so as to obtain M_{ρ_1}, …, M_{ρ_k} and nothing else. Moreover, for each i ∈ [k], the receiver’s choice ρ_i may depend on previously obtained messages {M_ρ_j}_{j < i} . Oblivious transfer with access control (OT-AC) is a flavor of adaptive OT where database records are protected by distinct access control policies that specify which credentials a receiver should obtain in order to access each M_i . So far, all known OT-AC protocols only support access policies made of conjunctions or rely on ad hoc assumptions in pairing-friendly groups (or both). In this paper, we provide an OT-AC protocol where access policies may consist of any branching program of polynomial length, which is sufficient to realize any access policy in NC^1. The security of our protocol is proved under the Learning-with-Errors (LWE) and Short-Integer-Solution (SIS) assumptions. As a result of independent interest, we provide protocols for proving the correct evaluation of a committed branching program on a committed input.

[15 novembre 2017 | 14h | Campus II - Salle S3-351]
Quelle courbe elliptique adéquate pour le calcul du couplage Optimal Ate pour le niveau de sécurité 128 bits?

Résumé.

Dans cet exposé je m’intéresse au calcul du couplage Optimal Ate en considérant les nouveaux niveaux de sécurité. En effet, fin 2016, les optimisations sur le calcul de logarithme discret sur les corps finis ont mené à un changement au niveau de niveau de sécurité du calcul des couplages. Par exemple, la courbe BN (la plus adéquate pour le calcul du couplage) possédant avant un niveau de sécurité de 128 bits mais maintenant que 100 bits après les résultats de Barbulescu et Kim. Récemment, Barbulescu et Duquesne ont conclut que la courbe elliptique la plus adéquate pour le calcul du couplage Optimal Ate pour le niveau de sécurité 128 bits est KSS16 et non pas BN. Notre but était de vérifier la conclusion de Barbulescu et Duquesne en passant à l'implémentation soft. Dans notre travail, nous avons étudié deux points: Le premier point concerne le calcul de l'algorithme de Miller optimisé pour le couplage Optimal Ate sur les courbes KSS16. Cette optimisation est grâce à la multiplication creuse '8-sparse-multiplications'.

Le deuxième point concerne l'implémentation du couplage Optimal Ate sur les courbes elliptiques: KSS16, BN et BLS12 en utilisant les nouvelles paramétrisations qui rassurent un niveau de sécurité de 128 bits. Notre étude comparative a confirmé que la courbe BN reste un fort candidat pour le calcul du couplage Optimal Ate. Cette conclusion nous a ouvert plusieurs points de recherche que nous sommes actuellement en train de les voir tels que le calcul du carré compressé dans F_{p^{16}} afin d'accélérer le calcul du couplage optimal Ate sur les courbes de degré de plongement k=16 (la meilleure théoriquement). Aussi chercher la courbe optimale pour les hauts niveaux de sécurité (voir 192 et 256).

[8 novembre 2017 | 14h | Campus II - Salle S3-351]
Optimisation d'un mode opératoire en arbre pour le hachage parallèle

Résumé.

Nous nous intéressons à des modes opératoires parallèles pour une fonction de hachage supposée être à taux unitaire, avec un état interne de la même taille qu'un bloc du message. Calculatoirement, une telle fonction a la caractéristique intéressante de ne nécessiter que k appels à la primitive sous-jacente pour traiter un message de k blocs. Afin de concrétiser une telle fonction, nous utilisons une variante de la construction de Merkle-Damgård (Coron et al., CRYPTO 2005). Nous construisons alors une fonction de hachage s'appuyant sur cette dernière au moyen d'un arbre ayant toutes ses feuilles à la même profondeur. Dans ce travail, nous caractérisons les structures arborescentes à utiliser pour réduire au mieux le temps d'exécution de la fonction qui en résulte. Ensuite, sans affecter ce temps d'exécution, nous montrons comment réduire le nombre de processeurs. En particulier, nous cherchons à libérer les processeurs le plus rapidement possible à chaque étape du calcul. Enfin, nous donnons un exemple de fonction de hachage utilisant ces optimisations et les résultats de Bertoni et al. (IJIS 2014), qui assure son indifférentiabilité d'une fonction de hachage idéale.

[18 octobre 2017 | 14h | Campus II - Salle S3-351]
Middle-Product Learning With Errors

Résumé.

We introduce a new variant MP-LWE of the Learning With Errors problem (LWE) making use of the Middle Product between polynomials modulo an integer q. We exhibit a reduction from the Polynomial-LWE problem (PLWE) parametrized by a polynomial f, to MP-LWE which is defined independently of any such f. The reduction only requires f to be monic with constant coefficient coprime with q. It incurs a noise growth proportional to the so-called expansion factor of f. We also describe a public-key encryption scheme with quasi-optimal asymptotic efficiency (the bit-sizes of the keys and the run-times of all involved algorithms are quasi-linear in the security parameter), which is secure against chosen plaintext attacks under the MP-LWE hardness assumption. The scheme is hence secure under the assumption that PLWE is hard for at least one polynomial f of degree n among a family of f’s which is exponential in n.

This talk is based on https://eprint.iacr.org/2017/628.pdf, a paper accepted at Crypto 2017. This is joint work with Amin Sakzad, Damien Stehlé and Ron Steinfeld.

[4 octobre 2017 | 14h | Campus II - Salle S3-351]
Archives :   2010   2011   2012   2013   2014   2015   2016   2017