Let N=pq and e be the modulus and the public exponent of an RSA instance. We show that RSA is insecure if there exist two unknown suitably small integers x and y such that ex+y = 0 (mod p). As an application, we present the cryptanalysis of CRT-RSA if one of the private exponents, dp say, is suitably small. This improves a former result of Bleichenbacher and May on CRT-RSA where both the decryption exponents dp and dq are required to be suitably small.

Résumé au format pdf disponible ici.

In 2007, Meloni introduced a new type of arithmetic on elliptic curves when adding projective points sharing the same Z-coordinate. This talk presents further co-Z addition formulae (and register allocations) for various point additions on Weierstrass elliptic curves. It explains how the use of conjugate point addition and other implementation tricks allow one to develop efficient scalar multiplication algorithms making use of co-Z arithmetic. Specifically, this paper describes efficient co-Z based versions of Montgomery ladder, Joye's double-add algorithm, and certain signed-digit algorithms, as well as faster (X; Y)-only variants for left-to-right versions. Further, the proposed implementations are regular, thereby offering a natural protection against a variety of implementation attacks.

We describe a stream-based hash function that is not built on the Merkle-Daamgard structure. It is based on arithmetic with polynomials over finite fields and has several attractive features including a very large internal state space and the ability to produce variable length hashes.

Les travaux présentés dans cet exposé se situent dans le contexte du fingerprinting. Un distributeur de documents multimédia souhaite se prémunir contre la redistribution illégale des données en insérant dans chaque copie distribuée un identifiant propre à chaque utilisateur. En cas de redistribution de cette copie, il est donc possible de retrouver l'utilisateur indiscret. Afin de contrer les attaques par collusion, qui surviennent lorsque les utilisateurs se mettent à plusieurs pour créer une copie pirate, les identifiants doivent être pris dans un code anti-collusion. Cette thèse étudie une famille de codes anti-collusion particulière, les codes de Tardos. Ces codes probabilistes sont particulièrement intéressants, car leur longueur est optimale. Ils sont de plus faciles à implémenter, et remarquablement efficaces. Nous présentons une amélioration de la phase d'accusation des codes de Tardos. Plus spécifiquement nous montrons comment l'optimiser en fonction de la stratégie d'attaque des pirates. Nous proposons également des moyens d'estimer à partir d'une copie pirate le nombre d'attaquants qui se sont rassemblés pour la créer, ainsi que la stratégie qu'ils ont employée. Notre solution s'appuie sur un algorithme itératif a la EM(Expectation-Maximization). Une autre contribution est l'étude d'un environnement asymétrique.Dans un tel environnement, seul l'utilisateur est en possession de la copie marquée avec son identifiant. L'identifiant doit être partiellement inconnu du distributeur tout en assurant sa fonction de traçage. Nous présentons un schéma de fingerprinting asymétrique entièrement spécifié intégrant les codes de Tardos, en utilisant une primitive cryptographique appelée Oblivious Transfer.

In this talk, we present a code framework formalizing the problem of designing an efficient broadcast encryption scheme which is also capable of tracing traitors. Our code construction is based on a combinatorial object called (r,s)-disjunct matrix, which is designed to capture both the classic notion of disjunct matrix and the new requirement of revocation capability. We then analyse a probabilistic method for constructing (r,s)-disjunct matrices which helps design efficient Black-Box Trace&Revoke systems. To deal with “smart” pirates, we introduce a tracing technique called “shadow group testing” that uses (close to) legitimate broadcast signals for tracing.

Joint work with Hung Q. Ngo (State University of New York at Buffalo) and David Pointcheval (ENS)

Le décodage par maximum de vraisemblance d'un code-correcteur linéaire binaire est un des grands problèmes en théorie des codes-correcteurs. Il a été montré NP-difficile. Cependant, aucun des algorithmes de décodage génériques des codes-correcteurs d'erreurs ne prend en compte le groupe de permutation des codes. L'idée est basée sur l'utilisation d'un sous-code (\sigma-code) du sous-code idempotent d'un code. Nous montrerons des bornes sur la dimension du \sigma-code pour une permutation particulière \sigma et nous expliquerons comment utiliser cette information pour le décodage. Un bon exemple sont les codes de Reed-Muller pour lesquels on peut déterminer ou borner ces \sigma-codes.

Depuis les années 1990, l'on sait que la consommation électrique d'un appareil peu donner de l'information sur le secret cryptographique qu'il contient. Différentes mesures de protection ont été développées afin de rendre plus difficile l'extraction de cette information. En parallèle, les cryptanalystes ont mis au point des techniques de plus en plus avancées. Cependant, ces techniques reposent sur des "modèles de fuites" qui sont des hypothèses sur la façon dont la consommation évolue en fonction des données traitées. Ces modèles dépendent des caractéristiques des puces et la question de la validité de ces modèles pour certaines puces peut se poser. Dans ce contexte, les attaques par collisions ont une approche orthogonale au problème puisque la seule hypothèse faite est que les fuites correspondant aux traitements de deux valeurs identiques seront similaires.

Le principe de base de ce type d'attaque est de détecter une collision (deux traces de consommation similaires) et d'en déduire la valeur du XOR de deux octets de clef. Il en résulte un système linéaire qu'il suffit de résoudre par recherche exhaustive des octets "libres" afin de retrouver la clef. Cette méthode est fortement sensible au fausses détections et n'exploite pas la redondance de l'information. Des travaux ont été effectué pour essayer d'améliorer ce point mais les techniques utilisées restent très heuristiques.

Dans cet exposé, je me propose de présenter l'attaque par collisions puis de l'exprimer comme un problème de décodage de code LDPC. On verra alors que l'utilisation de techniques classiques de décodage permet de passer outre les limitations citées afin de tirer pleinement profit de la redondance de l'information ainsi que de sa nature "soft".

Dans cet exposé, je donnerai un panorama de certains algorithmes utilisés sur les variétés abéliennes en lien avec la cryptographie: arithmétique, couplage, et calcul d'isogénies. Si ces algorithmes sont bien compris dans le cadre des courbes elliptiques, les appliquer à des Jacobiennes de courbes dépend fortement de la géométrie de la courbe sous-jacente. L'emploi des fonctions thêta, qui forment un système de coordonnées "universel" sur toute variété abélienne, permet en revanche d'obtenir des algorithmes unifiés. Nous illustrerons l'emploi de ces fonctions thêta à travers de nombreux exemples.

Il s'agit d'un travail en commun avec David Lubicz et Romain Cosset.

Les primitives cryptographiques sont basées sur des problèmes difficiles en moyenne, au sens où presque toutes les instances sont difficiles. Traditionnellement, cette difficulté moyenne repose sur des expériences, ou sur la difficulté moyenne d'autres problèmes. Pourtant, en 1996, Ajtai a montré que résoudre n'importe quel problème de réseaux difficile dans le pire cas se réduisait à approcher le problème du plus court vecteur dans un réseau, sur une classe particulière, celle des réseaux de type SIS. Ainsi, l'existence de la moindre instance difficile d'un problème de réduction de réseau entraîne la difficulté de presque toutes les instances du problème SIS.

Cette découverte constitue une brique fondamentale dans la construction des schémas à base de réseaux. Alors que les problèmes classiques tels que RSA et le log discret ne sont supposés difficiles que pour des instances particulières, avec cette réduction, il devient désormais possible de baser la cryptographie sur des problèmes difficiles dans le pire cas. Malheureusement, la contrainte d'utiliser des réseaux de type SIS induit des cryptosystèmes avec un volume et une dimension qui restent assez élevés et les schémas qui en dérivent restent peu exploitables en pratique.

Dans cet exposé, nous présentons une nouvelle réduction pire-cas vers cas moyen, qui prouve à la fois la difficulté de réduire des réseaux aléatoires, et la difficulté du problème du sac à dos. Cela conduit à des cryptosystèmes plus naturels, et même quatre fois plus petits que leurs prédécesseurs pour un même niveau de sécurité.

Pas de séminaire en raison des journées ALEA

In the first part of the talk we will present a decoding algorithm based on a lifting decoding scheme. This leads to a unique decoding algorithm for Reed-Solomon codes over Galois rings with a very low complexity, and a list decoding algorithm. We will show that, using erasures in our algorithms, allows to decode more errors than half the minimum distance with a high probability. Finally we will apply these techniques to interleaved linear codes over a finite field and obtain a decoding algorithm that can recover more errors than half the minimum distance. In the second part we will present the implementation of decoding algorithm which is a work in progress.

Kloosterman sums have recently become the focus of much research, most notably due to their applications in cryptography and their relations to coding theory. In particular, Mesnager has shown that the value 4 of binary Kloosterman sums gives rise to several infinite classes of bent functions, hyper-bent functions and semi-bent functions in even dimension, thus extending classical results of Dillon.

In this talk we analyze the different strategies used to find zeros of binary Kloosterman sums to develop and implement efficient deterministic algorithms to find the value 4 of such sums. We then present experimental results showing that the value 4 of binary Kloosterman sums gives rise to bent functions for small dimensions in a case with no mathematical solution so far.

In this talk we will survey the state of the art in Functional Encryption with special focus on Hidden Vector Encryption schemes and show its applicability to Private and Searchable Remote Storage. Our thesis is that Predicate Encryption offers solid Cryptographic foundations for Remote Storage but several issues remain to be addressed before we can deploy usable and private remote storage. Furthermore we will survey some recent achievements in the context of publicly verifiable computation.

ARMADILLO2 is the recommended variant of a multi-purpose cryptographic primitive dedicated to hardware which has been proposed by Badel et al. in CHES 2010. This primitive based on data-dependant bit transpostion is very innovative. Using a generalisation of the parallel matching technique presented by Marìa Naya-Plasencia at CRYPTO 2011 we propose a meet-in-the-middle attack on the Armadillo function. The parallel matching method is a new technique to speed up complexities of the problem consisting in merging lists of big size. This method allow us to propose a key recovery attack of the FILMAC and the stream cipher application. Finally we propose a (second) preimage attack on its hashing application mode. Our attacks have been validated experimentally by implementing cryptanalysis on scaled variants that match the theoretical predicted complexities.

This is a joint work with Mohamed Ahmed Abdelraheem, Marìa Naya-Plasencia, Marion Videau, and Erik Zenner.

Partant du constat que le problème du codage par syndrome avec positions verrouillées ne possède pas toujours de solution, on propose d'exhiber des conditions nécessaires et suffisantes en fonction de la distance duale du code utilisé pour que le problème précédent possède au moins une solution [1]. On remarque que plus le défaut de Singleton du code est petit (i.e. plus le code est proche d'être M.D.S.), meilleures sont les bornes introduites. Par la nature combinatoire de ces bornes, on propose de généraliser certaines d'entre elles aux codes systématiques { vus comme une généralisation des codes linéaires. On en déduit que dans un tel contexte, que les codes systématiques peuvent être des bons candidats. Ensuite, on introduit une méthode qui permet d'assurer l'insertion, au prix d'une légère baisse de l'embedding efficiency [2]. En utilisant cette méthode avec les codes de Hamming binaire, on est capable d'atteindre exactement les bornes précédentes.

Résumé au format pdf

Pas de séminaire en raison des journées du GDR IM

L'utilisation des courbes elliptiques et hyperelliptiques en cryptographie nécessite de pouvoir calculer en un temps raisonnable l'ordre de la courbe elliptique et dans le cas hyperelliptique, de la jacobienne de la courbe. T. Satoh proposa à Eurocrypt 2009 un algorithme polynomial pour vérifier si l'ordre de la jacobienne d'une courbe hyperelliptique de la forme Y^2 = X^5 + aX^3 + bX définie sur un corps fini Fq admet un grand facteur premier. Son approche consiste à obtenir différents candidats pour la fonction zeta de la jacobienne sur Fq en partant de la fonction zeta de la jacobienne sur une extension où la jacobienne se partage en deux courbes elliptiques. L'approche de T. Satoh se généralise pour obtenir l'expression exacte de la fonction zeta de jacobienne de courbes hyperelliptiques de genre 2 de la forme ci-dessus et Y^2 = X^6 + aX^3 + b. On a obtenu les expressions exactes des fonctions zeta par des résolutions successives d'équations de degré 2.

Les systèmes à bases de couplages utilisent des courbes elliptiques particulières présentant un petit degré de plongement par rapport à un grand sous-groupe d'ordre premier. Les formules explicites d'ordre des jacobiennes des deux familles de courbes hyperelliptiques permettent de construire des jacobiennes ayant les propriétés voulues pour une utilisation en cryptographie à base de couplages. Pour cela on a étendu les méthodes existantes dans le cas elliptique, à savoir la méthode de Cocks-Pinch et la méthode cyclotomique (ou de Brezing-Weng). Les formules exactes permettent de voir que les restrictions faites précédemment sur le degré de plongement sont excessives. Les algorithmes présentés sont valables pour n'importe quel degré de plongement. Pour illustrer notre méthode on propose des exemples pour un patit degré de plongement avec rho = 4 pour une méthode à la Cocks-Pinch et rho = 3 pour une méthode de type Brezing-Weng.

We present in this talk a new problem which consists in solving non-linear equations modulo a prime q = poly(n) with noise (typically a Gaussian), i.e., some equations of the algebraic system are erroneous. This problem, that we have called Polynomial With Errors (PWE), is a non-linear (and rather natural) generalization of the well-known Learning With Errors (LWE) problem [1, 2, 3]. We recall that LWE is the problem of solving linear equation with noise.

We present in this talk theoretical complexity results on PWE. Note that the hardness of PWE is supported by the hardness of solving algebraic equations without errors ; the PoSSo problem. Solving non-linear system being significantly harder than solving a linear system, it is reasonable to expect that solving PWE will be harder than LWE. However, it can be shown that if the number of equations is ≥ poly(n) (n being the number of variables) then PWE is essentially equivalent to an instance of PWE with bigger parameters. Therefore, the most interesting case to consider is PWE for a fixed and small number i.e. < poly(n) of equations. We denote by boundPWE this problem, i.e. PWE with a bounded (< poly(n)) number of samples. We prove that boundPWE has a decision/search equivalence (deciding that a solution exists is equivalent to find a solution) a weak average-case/worst-case reduction. As a by-product, we show that these results also hold for the noiseless version of this problem, i.e. PoSSo.

Finally, we will briefly sketch an algorithm for solving bound PWE/PWE and discuss about the possibly to construct cryptographic schemes based on our new problems.

Résumé au format pdf ici

Après une partie introductive sur les codes correcteurs d'erreurs, je me focaliserai plus précisément sur les codes de Reed et Muller et sur une interprétation géométrique de leurs paramètres. Partant de cette interprétation, je montrerai comment rechercher de bons sous-codes des codes de Reed-Muller à deux ou trois variables par de jolies méthodes géométriques. On montrera en particulier comment certains codes BCH aux paramètres extrémaux peuvent naturellement se décrire comme des sous-codes de codes de Reed-Muller à deux variables.

Pas de séminaire en raison des journées en la mémoire de Philippe Flajolet

On établira dans cet exposé un lien entre le problème de la minimisation de la somme des quotients partiels et l'élaboration d'un algorithme efficace de calcul de point résistant aux attaques SPA.

NTRU is a fast public key cryptosystem presented in 1996 by Hoffstein, Pipher and Silverman. It operates in the ring of truncated polynomials. In NTRU, a public key is a polynomial defined by the combination of two private polynomials. In this paper, we consider NTRU with two different public keys defined by different private keys. We present a lattice-based attack to recover the private keys assuming that the public keys share polynomials with a suitable number of common coefficients.

Dans cet exposé, Je présenterais rapidement le système de représentation des nombres basé sur le théorème des restes chinois (RNS) et je montrerais comment et pourquoi il est bien adapté au calcul de couplage, en particulier pour les grands degrés d'extension comme pour les courbes BN et pour les implémentations matérielles (FPGA dans notre cas).

We present a study on the algebraic degree of iterated permutations seen as multivariate polynomials. Such constructions are in the heart of many modern symmetric primitives, including block ciphers and hash functions. The estimation of this degree is of major importance, as functions with a low degree are vulnerable to many attacks, for instance higher-order differential, algebraic or cube attacks. We derive a new bound on the degree of iterated permutations, composed of parallel applications of a number of balanced Sboxes. In a more general case, we show that the degree of the iterated primitive depends on the algebraic degree of the inverse of the permutation which is iterated and we extract new bounds from this relation. The above results permit us to establish structural distinguishers to many hash functions, candidates of the NIST SHA-3 competition, such as Keccak, Luffa, ECHO and JH, and to a higher-degree variant of the KN block cipher.

Joint work with Anne Canteaut and Christophe De Cannière.

La cryptographie sur courbes elliptiques et hyperelliptiques, et plus spécialement celle reposant sur les couplages, demande d'effectuer des calculs dans des corps finis de petites caractéristiques. Dès lors développer des opérateurs matériels pour effectuer les opérations arithmétiques sur ces corps est un problème intéressant, que ce soit dans un but de performances (ces opérations sont mal supportés par les processeurs généralistes) ou pour obtenir des accélérateurs spécifiques pour les calculs cryptographiques.

Durant cet exposé, nous examinerons la représentation des éléments de corps finis de petites caractéristiques et la réalisation d'opérations sur ceux-ci afin de décrire un coprocesseur arithmétique pour corps finis. Parmi ces opérations, la plus coûteuse est la multiplication. C'est pourquoi nous montrerons différents algorithmes pour effectuer le produit et discuterons des différents compromis performance/consommation de ressources obtenue lors de l'implémentation matérielle de ceux-ci. Nous illustrerons l'utilisation de ces opérateurs par différents accélérateurs matériels pour le calcul de couplage.

Travaux réalisé avec : Jean-Luc Beuchat, LCIS, Université de Tsukuba, Japon. Jérémie Detrey, Equipe-projet CARAMEL, INRIA Nancy Grand-Est, France.

Les systèmes d'accréditation anonyme permettent aux utilisateurs d'obtenir des accréditations certifiées (permis de conduire, carte d'étudiant, etc.) auprès d'organisations émettrices et de prouver la possession de ces accréditations auprès de fournisseurs de services tout en minimisant l'information révélée. A CANS 2010, Guajardo, Mennink et Schoenmakers ont introduit le concept d'accréditations anonymes avec attributs chiffrés, où certains attributs sont cachés à certaines parties et lisibles par d'autres. Leur construction est sûre dans le modèle de l'oracle aléatoire et basée sur l'utilisation de signatures aveugles. Ces dernières sont, malheureusement, «one-show », i.e. à usage unique. Les utiliser plusieurs fois permet de casser l'anonymat. Les auteurs laissent comme problème ouvert la construction d'un schéma d' accréditation anonyme avec attributs chiffrés qui soit « multi-show », i.e. où les accréditations peuvent être utilisées plusieurs fois sans casser la sécurité du schéma. Nous donnons ici une réponse positive à cette question.

We prove NP-hardness of equivalence and representation problems of quadratic forms under probabilistic reductions, in particular for indefinite ternary quadratic forms with integer coefficients. We present identifications and signatures based on these hard problems. The bit complexity of signature generation and verification is quadratic using integers of bit length 150.