A computational group is pseudo-free if an adversary cannot find solutions in this group for equations that are not trivially solvable in the free group. This notion was put forth by Rivest at TCC 2004 as a unifying abstraction of multiple group-related hardness assumptions commonly used in cryptography. Rivest's conjecture that the RSA group is pseudo-free had been settled by Micciancio for the case of RSA moduli that are the product of two safe primes. This result holds for a static setting where the adversary is only given the description of the group (together with a set of randomly chosen generators) and has to come up with the equation and the solution.

In this paper we explore a powerful extension of the notion of pseudo-freeness. We identify, motivate, and study pseudo-freeness in face of adaptive adversaries who may learn solutions to other non-trivial equations before having to solve a new non-trivial equation.

We present a novel, carefully crafted definition of adaptive pseudo-freeness that walks a fine line between being too weak and being unsatisfiable. We show that groups that satisfy our definition yield, via a generic construction, digital and network coding signature schemes.

Finally, we obtain concrete constructions of such schemes in the RSA group by showing this group to be adaptive pseudo-free. In particular, we demonstrate the generality of our framework for signatures by showing that most existing schemes are instantiations of our generic construction.

This is a joint work with Dario Catalano and Bogdan Warinschi. An extended abstract appears in the proceedings of Eurocrypt 2011. A full version is available at http://eprint.iacr.org/2011/053.

Les isogénies sont un outil important pour l'étude des cryptosystèmes basés sur les courbes, non seulement parce qu'elles transportent le problème du logarithme discret, mais aussi par la riche structure de graphe qu'elles permettent d'exploiter.

Nous présenterons d'abord cette structure de graphe d'isogénies, aussi bien dans le cas des courbes elliptiques que dans celui des courbes hyperelliptiques, en prenant soin d'insister sur les aspects algorithmiques sous-jacents.

Ensuite, nous considèrerons le problème consistant à construire des courbes "pairing-friendly", c'est-à-dire munies d'un couplage calculable efficacement, et verrons comment la structure du graphe d'isogénies peut être exploitée pour le résoudre plus rapidement.

Enfin, nous nous pencherons sur le problème inverse, celui du calcul des anneaux d'endomorphismes, et verrons qu'une fois encore la structure du graphe d'isogénies permet de le résoudre très efficacement. Cela a des retombées positives notamment pour la construction de courbes "pairing-friendly".

Les réseaux de téléphonie mobile sont apparus au cours des années 80, mais ils se sont développés au cours des années 90 avec l'apparition d'un réseau dit de seconde génération, le "Global System for Mobile Communications" (GSM). Si à l'origine, ces réseaux concernaient uniquement le transport de la voix, ils ont évolué vers le transport des données (GPRS) et l'utilisation de nouvelles technologies plus efficaces en terme de débit (les réseaux 3G et 4G).

Malgré ces évolutions et bien que vieux de 20 ans, les réseaux GSM restent aujourd'hui largement utilisés. Dans cet exposé, nous examinerons les différents mécanismes de protection impliqués lors de la transmission sans fil entre le terminal et le réseau de l'opérateur en GSM et GPRS. Nous verrons comment ces mécanismes peuvent être aujourd'hui contournés et comment les faiblesses présentes dans le protocole GSM permettent de compromettre la sécurité du protocole de transport de données GPRS.

Pour conclure sur une note plus optimiste, je décrirai brièvement les difficultés liées à la mise en pratique des attaques présentées et les contre-mesures adoptées dans le protocole 3G UMTS.

Depuis quelques années, les applications basées sur des dispositifs sans contact ont le vent en poupe. La facilité et praticité de ce mode de communication ont attisé l'intérêt des industriels. Ainsi, il est désormais possible de réaliser l'inventaire d'un entrepôt en quelques minutes, ou encore de valider son ticket de métro sans procédure particulière. Il semble évident que de tels systèmes doivent être sécurisés. En effet, ils doivent assurer l'authentification des objets ou des personnes légitimes de manière quasi permanentes. En revanche, un fraudeur ne doit pas être capable d'être authentifié à tort par le système. Enfin, personne ne doit pouvoir obtenir des informations personnelles concernant le porteur d'un dispositif sans contact.

Bien que la problématique semble facile, il n'existe à ce jour aucun modèle de sécurité faisant l'unanimité. Après avoir détaillé les objectifs devant être remplis par un modèle de sécurité, je présenterai différents modèles existants qui selon moi ne parviennent pas à définir le modèle ultime

L'étude du groupe de classes d'idéaux d'un corps de nombres est un problème de théorie des nombres permettant notamment la résolution d'équations Diophantiennes, la vérification de conjectures non prouvées, ainsi que la représentation de groupes de matrices sur un corps de nombres.

Dans le cas des corps quadratiques, le difficulté de résoudre le problème du logarithme discret dans le groupe de classes a attiré l'attention de la communauté cryptographique au début des années 90. Plusieurs cryptosystèmes ont été proposés reposant sur ce problème, et les attaques disponibles à ce jour sont sous-exponentielles en L(1/2), c'est-à-dire plus lentes que pour la factorisation d'entiers RSA de taille équivalente qui a pour complexité L(1/3).

Les récents travaux sur les isogénies entres courbes elliptiques ont mis en évidence l'importance du rôle des calculs concernant le groupe de classes d'idéaux d'un corps de nombres quadratique dans l'évaluations d'isogénies ainsi que la description du groupe d'endomorphismes d'une courbe.

Durant l'exposé, nous prendrons le temps de décrire le groupe de classes d'idéaux d'un corps de nombres ainsi que les algorithmes sous-exponentiels classiques permettant d'en calculer la structure. Ensuite, nous nous intéresserons à des résultats sur la sécurité des cryptosystèmes basés sur les corps de nombres avant de terminer par des travaux en cours sur des améliorations pratiques de l'algorithme d'évaluation d'isogénies de Bröker-Charles-Lauter.

La réduction forte de réseaux est la clé de la plupart des attaques contre les cryptosystèmes basés sur les réseaux. Entre la réduction HKZ, forte mais trop coûteuse, et la réduction LLL, plus faible mais rapide, existent plusieurs tentatives d'obtenir des compromis efficaces. Celle qui semble atteindre le meilleur rapport temps/qualité est la réduction BKZ, introduite par Schnorr et Euchner en 1991. Cependant, aucune borne de complexité raisonnable sur cet algorithme n'était connue jusqu'à maintenant. Nous prouvons qu'après O~(n^3/k^2) appels à une routine de HKZ-réduction, BKZ_k renvoie une base telle que la norme du premier vecteur est bornée par ~= gamma_k ^ (n/2(k-1)) * det(L)^(1/n). Le principal outil de la preuve est l'analyse d'un système dynamique linéaire associé à cet algorithme.

Strong lattice reduction is the key element for most attacks against lattice-based cryptosystems. Between the strongest but impractical HKZ reduction and the weak but fast LLL reduction, there have been several attempts to find efficient trade-offs. Among them, the BKZ algorithm introduced by Schnorr and Euchner in 1991 seems to achieve the best time/quality compromise in practice. However, no reasonable time complexity upper bound was known so far for BKZ. We give a proof that after O~(n^3/k^2) calls to a k-dimensional HKZ reduction subroutine, BKZ_k returns a basis such that the norm of the first vector is at most ~= gamma_k ^ (n/2(k-1)) * det(L)^(1/n). The main ingredient of the proof is the analysis of a linear dynamic system related to the algorithm.

Le premier décodage algébrique pour les codes de Goppa est dû à Patterson en 1975. Cette méthode décode jusqu'à t, la capacité de correction du code. Les codes de Goppa font partie de la famille des codes alternants, c'est-à-dire des codes restreints à un sous- corps de Reed-Solomon généralisé, il est donc pos- sible d'adapter toutes les méthodes de décodages des codes de Reed-Solomon aux codes de Goppa, comme le célèbre algorithme de décodage en liste de Gurus- wami et Sudan. Ce procédé nous permet alors de décoder jusqu'à la borne de Johnson générique, qui est plus grand que t. Dans son mémoire de thèse, Guruswami propose une méthode pour décoder en liste les codes restreints géométriques jusqu'à la borne de Johnson q-aire, qui est plus grande que la borne de Johnson générique. On propose alors d'appliquer cette même méthode aux codes alternants, et tout particulièrement aux codes de Goppa binaires. Bernstein, Lange et Pe- ters expliquent comment dans le cryptosystème de McEliece, on peut utiliser le décodage en liste. On conclura alors par la réduction de clé de McE- liece obtenue grâce à cet algorithme de décodage en liste.

Résumé au format pdf ici.

Imagine the government is taking a census, and you as an individual are worried that by participating, private information about you (such as your address, age, ethnicity, etc.) may eventually be revealed when the government publishes the census data. How can the government assure you that by using an appropriate release mechanism that "sanitizes" census data, no individual's privacy will be compromised?

This question has been studied for a long time in the statistics community, and more recently the computer science community has contributed the formal notion of differential privacy, which captures the idea that "no individual's data can have a large effect on the output of the release mechanism". This has been interpreted to mean that individuals should be comfortable revealing their information, since little private information is leaked.

In this talk, we first give an introduction to this fast-developing area of research. We then investigate the above interpretation about the guarantees of differential privacy. We argue that the interpretation is incomplete because unless participation in the database somehow explicitly benefits the individuals, they will always refuse to participate regardless of whether the release mechanism is differentially private or not. We then show that by combining differential privacy with the notion of incentives and truthfulness from game theory, one can take (almost) any release mechanism that motivates individuals to participate and modify it so that in addition it satisfies differential privacy.

Une carte d'identité préservant la vie privée est un objet personnel, qui a exactement les mêmes utilisations qu'une carte nationale d'identité traditionnelle, mais sans révéler plus d'information qu'il n'est utile pour une finalité particulière. Ainsi avec une telle carte, un citoyen peut prouver sa nationalité lorsqu'il passe la frontière, démontrer qu'il appartient à une certaine tranche d'âge afin d'obtenir une réduction au cinéma ou encore accéder aux services locaux qui sont réservés aux habitants d'une commune, sans pour autant avoir à révéler son nom, son prénom ou sa date de naissance.

Plus précisément, la vie privée de son propriétaire est protégée à travers l'utilisation d'accréditations anonymes stockées sur la carte, qui permettent à son utilisateur de prouver certaines propriétés binaires liées à son identité mais sans avoir à révéler explicitement celle-ci ou d'autres informations non-nécessaires. De plus, il est impossible de tracer les actions réalisées par l'utilisateur de la carte, même si celui-ci prouve plusieurs fois la même affirmation (propriété de non-chaînabilité). Une carte à puce résistante aux attaques logicielles et matérielles stocke les informations personnelles de l'utilisateur protégeant ainsi à la fois sa vie privée et prévenant les risques de contrefaçon. Enfin, l'utilisateur s'authentifie à la carte par biométrie, interdisant ainsi une autorisation frauduleuse dans la situation où la carte est volée ou perdue.

Durant cette présentation, j'introduirais le concept de la carte d'identité préservant la vie privée ainsi les propriétés fondamentales qu'une telle carte devrait idéalement satisfaire. Ensuite, je décrirais deux propositions d'implémentation de la carte, une reposant sur l'utilisation d'une carte à puce résistante aux attaques et l'autre sur une combinaison extracteurs flous (fuzzy extractors en anglais) - preuves à divulgation nulle. Enfin, je conclurais par une discussion sur des extensions possibles.

Travail conjoint réalisé avec Yves Deswarte, LAAS-CNRS

Zero-knowledge proofs of knowledge are now used in numerous applications and permit to prove the knowledge of secrets with many (complex) properties. Among them, the proof that a secret lies in a given interval is very useful in the context of electronic voting, e-cash or anonymous credentials. In this talk, we propose new contributions to the practical use of these so-called range proofs. We first introduce a variant of the signature-based method due to Camenisch, Chaabouni and Shelat, which allows the prover to avoid pairing computation. We also give several improvements to the solution of Lipmaa, Asokan and Niemi based on the multi-base decomposition of the secret. We finally make the first complete comparison between all existing range proofs. This permits to prove that our methods are useful in many practical cases. This also allows service designers to decide the best method to use, depending on their practical needs and constraints on the size of the interval, the power of the verifier and the prover, etc.

Radio Frequency Identification (RFID) allows to identify and authenticate objects or subjects without any physical nor optical contact, using transponders - micro-circuits with an antenna - queried by readers through a radio frequency channel. This technology is one of the most promising of this decade and is already widely used in applications such as access cards, public transportation, payment cards, and passports.

After quite a brief introduction about RFID, we will focus in this talk on the security and privacy research challenges related to this field. We will especially discuss about impersonation and authentication protocols, including (but not limited to) relay attacks and synchronized protocols. We will then also consider the malicious traceability problem, the cryptographic means to solve it, and the related open questions. We will finally conclude with the current and future research trends in RFID security and privacy.

Dans de nombreux protocoles cryptographiques, il est nécessaire de disposer de fonctions de hachage à valeur dans le groupe des points d'une courbe elliptique (ou plus généralement dans la jacobienne d'une courbe hyperelliptique). Nous expliquerons comment il est possible de construire de telles fonctions à partir de fonctions de hachage plus classiques (à valeur dans des chaînes de bits) d'une façon qui préserve la sécurité des protocoles considérés. L'étude de ces fonctions et les preuves de sécurité associées mettent en jeu des outils mathématiques variés, depuis des calculs élémentaires dans les corps finis jusqu'à des résultats plus sophistiqués de géométrie et de théorie des nombres.

We give a gentle introduction to the arithmetic on Jacobians of hyperelliptic curves of genus g and describe how these objects can be used in cryptography. As a special case, this includes elliptic curve cryptography (g=1) which is ubiquitous in modern day cryptosystems.

Then we look at Lenstra's elliptic curve factorization method (ECM), inspired by Pollard's p-1 algorithm. One can replace elliptic curves (g=1) with Jacobians of hyperelliptic curves of higher genus to get an analogous algorithm (HECM), but in general this will not be competitive with elliptic curves as the arithmetic is slower for higher genus. We report on a recent implementation of HECM in genus 2 due to R. Cosset which is competitive with ECM and we describe some of the objects (Kummer surfaces) and ideas used to bridge the gap.

Many (public-key) identification schemes have been proposed since the introduction of Zero-knowledge proofs. One of the most well known is the Fiat-Shamir Scheme, which relies on the hardness of a number-theoretic problem. Since then, several schemes were proposed that do not rely on number-theoretic, but rather on combinatorial problems. An example is the Scheme based on the hardness of Syndrome Decoding proposed by Stern in 1993.

In this talk, we first focus on the identification scheme based on the Isomorphism of Polynomials with One Secret (IP1S) that was proposed by Patarin in 1996. Here, the public key is formed by two tuples of quadratic forms. The secret key is a matrix that, when composed with the first one, yields the second one. This scheme enjoys shorter keys than many other schemes and does not require preliminary agreement on a common string. Patarin proposed concrete parameters that have not been broken faster than exhaustive search so far. On the theoretical side, IP1S has been shown to be harder than Graph Isomorphism, which makes it an interesting target.

We present a new algorithms to attack the IP1S problem, and we analyze its complexity and success probability. We show that they it solve a (big) constant fraction of all the instances in polynomial time. We verified that our algorithms are very efficient in practice. All the parameters proposed by Patarin are now broken in a few seconds.

We will also consider the "full" (and harder) isomorphism of polynomials problem (that is, with two secret matrices).

This work will be presented at PKC'11.

In this talk we will present a new signature scheme whose security is related to standard lattice problem, i.e. SVP and CVP.

We recall briefly the general setting of LPC: a lattice cryptosystem using lattice Groebner bases. We investigate the use of Normal Form function defined by Groebner basis to solve the lattice approximate CVP. This allows to approach the formal security analysis of LPC.

We show haw to define instances of LPC suitable for a signature protocol, and discuss how an analysis of an instances of the private key may confirm that some of the attack not only will be hard, but in case of success the heuristic of some of them will fail.

Soient $\F$ un corps parfait, et $\Y=Y_1,\dots,Y_n$ des indeterminées sur $\F$. Un ensemble triangulaire (unitaire) $\T=(T_1,\dots,T_n)$ est une famille de polynômes de $\F[\Y]$ telle que pour tout $i$, $T_i \in \F[Y_1,\dots,Y_i]$ est unitaire et réduit modulo $\langle T_1,\dots,T_{i-1}\rangle$. Le degré de $\T$ est le produit $\deg(T_1,Y_1)\cdots \deg(T_n,Y_n)$. Ces objets permettent de résoudre de nombreux problèmes pour les systèmes d'équations polynomiales.

Cet exposé, s'intéresse à la complexité de diverses opérations modulo un ensemble triangulaire~: la multiplication, l'inversion (quand celà est possible), calculer la norme de $A\in \F[\Y]/\langle T\rangle$, le problème de composition modulaire (i.e. calculer $F(G_1(\Y),\cdots,G_m(Y)) \mod \langle T\rangle$) et le problème transposé de projection des puissances, et enfin le problème de changement d'ordre.

Nous décrirons pour ces problèmes des algorithmes ayant une complexité binaire quasi-linéaire en la taille du problème, ce qui améliore les algorithmes existants quand le nombre de variables $s$ n'est pas borné par une constante.

Enfin, nous illustrerons brièvement une application de ces algorithmes dans le cas du problème de comptage de points des courbes elliptiques. (Ce résumé en pdf.)

Dans cet exposé un modèle algébrique pour la caractérisation des codes correcteurs systématiques est présentée. L'intérêt pour cette famille dérive de la volonté de généraliser les codes linéaires afin de rechercher des codes qui soient optimaux du point de vue de la distance. En fait, il est possible démontrer que tout code linéaire est équivalent à un code systématique, mais il existe des codes systématiques non-linéaires à distance plus grande de tout linéaire qui partage les mếme paramètres n (longueur) k (dimension). A la base de cette approche, le fait que tout code systématique est en correspondance avec la base de Groebner réduites de son idéal d'annulation. Grâce à cette correspondance, nous décrivons un algorithme qui, étant donnés n,k,d entiers, fournit la car- actérisation des codes systématiques avec paramètres n,k et distance au moins d. Le point central de l'algorithme est le calcul de la base de Groebner d'un certain idéal B(n,k,t) qui est invariant sous l'action d'un groupe de permuta- tions et présente de propriétés d'inclusions dans d'autres idéaux du même type (par ex. dans B(n+1,k,t+1) et B(n+1,k+1,t)). Avec des techniques similaires, il est possible aussi de formuler un algorithme pour le calcul de la distribution des distances d'un code systématique et une nouvelle borne pour la distance de ces codes.

Miller’s algorithm is at the heart of all pairing-based cryptosystems since it is used in the computation of pairing such as that of Weil or Tate and their variants. Most of the optimizations of this algorithm involve elliptic curves of particular forms, or curves with even embedding degree, or having an equation of a special form. Other improvements involve a reduction of the number of iterations. In this article, we propose a variant of Miller’s formula which gives rise to a generically faster algorithm for any pairing friendly curve. Concretely, it provides an improvement in cases little studied until now, in particular when denominator elimination is not available. It allows for instance the use of elliptic curve with embedding degree not of the form 2i 3j , and is suitable for the computation of optimal pairings. We also present a version with denominator elimination for even embedding degree. In our implementations, our variant saves between 10% and 40% in running time in comparison with the usual version of Miller’s algorithm without any optimization.

Une isogénie est un morphisme de variétés abeliennes qui préserve la structure de groupe.

Calculer des isogénies, oui, mais quoi et comment ? Si dans le contexte du bon vieil algorithme SEA le problème est bien défini et relativement bien compris, la cryptographie moderne pose des nouveaux problèmes qui nécessitent des réponses... rapides !

Dans cet exposé nous allons passer en revue les différentes définitions du problème du "calcul d'isogénies", avec leurs motivations respectives. Nous allons ensuite présenter le zoo d'algorithmes de calcul d'isogénies, puis nous allons entrer dans les détails de certaines variantes et améliorations, en quête de la complexité optimale : elle ne sera atteinte que dans des cas très spécifiques, ce qui nous amènera à conclure sur les obstacles qui nous entravent et sur les perspectives futures.

Building a provably-secure public key cryptosystem based on the hardness of the subset sum problem has been an intriguing problem since the late 1970's. In this work, we give a very simple construction of such a scheme. In addition to the simplicity of the construction and the security proof, the hardness assumption of our scheme is weaker than that of all other existing subset-sum based encryption schemes, namely the lattice-based schemes of Ajtai and Dwork (STOC '97), Regev (STOC '03, STOC '05), and Peikert (STOC '09).

This is joint work with Adriana Palacio and Gil Segev that appeared at the Theory of Cryptography Conference (TCC) 2010