Locally Decodable Codes (LDCs) are error correcting codes with decoding algorithm of sublinear query complexity (i.e. to decode one message bit, the decoder needs to read only a few, ideally constant, codeword bits). LDCs have numerous application in Data Structures, Hardness Amplification, Private Information Retrievals and Probabilistically Checkable Proofs(PCPs). In the last decade, constructing efficient LDCs has been a major research area in Theoretical Computer Science. Still existence of polynomial rate constant query LDC remain a major open problem.

Recent results show the computational limitations of the adversary help in designing better error correcting codes.We consider the problem of designing Locally Decodable Codes against an adversary that is computationally bounded in terms of running time. In this work we prove that in the case of constant query linear locally decodable codes the computational bound does not make the adversary less powerful, unless both the sender and the receiver shares a secret key. We also show that if both the sender and the receiver shares a secret key then there is a constant query locally decodable code (against a computationally bounded adversary) that has better rate than information theoretic constant query LDCs. (joint work with Sourav Chakraborty).

• il faudra attendre quelques mois ...

This article introduces a new Combined Attack on a CRT- RSA implementation resistant against Side-Channel Analysis and Fault Injection attacks. Such implementations prevent the attacker from ob- taining the signature when a fault has been induced during the compu- tation. Indeed, such a value would allow the attacker to recover the RSA private key by computing the gcd of the public modulus and the faulty signature. The principle of our attack is to inject a fault during the sig- nature computation and to perform a Side-Channel Analysis targeting a sensitive value processed during the Fault Injection countermeasure execution. The resulting information is then used to factorize the public modulus, leading to the disclosure of the whole RSA private key. After presenting a detailed account of our attack, we explain how its complex- ity can be significantly reduced by using lattice reduction techniques. We also provide simulations that confirm the efficiency of our attack as well as two different countermeasures having a very small impact on the performance of the algorithm. As it performs a Side-Channel Analysis during a Fault Injection countermeasure to retrieve the secret value, this article recalls the need for Fault Injection and Side-Channel Analysis countermeasures as monolithic implementations.

Structure-preserving signatures (SPS) are signature schemes where messages, signatures and public keys all consist of elements of a group over which a bilinear map is efficiently computable. This property makes them useful in cryptographic protocols as they nicely compose with other algebraic tools like the Groth-Sahai proof systems. In this work, we consider SPS systems with homomorphic properties and suggest applications that have not been provided before by ordinary SPS. We build linearly homomorphic structure-preserving signatures under simple assumptions and show that the primitive makes it possible to verify the calculations performed by a server on outsourced encrypted data. Then, we give a generic construction of non-malleable structure-preserving commitment from any linearly homomorphic SPS. This notably provides the first constant-size non-malleable commitment to group elements.

In this paper, we present a new attack on RSA with a public exponent e satisfying an equation ed-k(N+1-ap-bq) = 1 where a/b is an unknown approximation of q/p. We show that RSA is insecure when certain amount of the Least Significant Bits (LSBs) of ap and bq are known. Further, we show that the existence of good approximations a/b of q/p with small a and b substantially reduces the requirement of LSBs of ap and bq. The attack is based on Coppersmith's method for solving modular polynomial equations.

A pseudo-random generator (PRNG) is a deterministic algorithm that produces numbers whose distribution is indistinguishable from uniform. A formal security model for PRNGs with input was proposed in 2005 by Barak and Halevi. This model involves an internal state that is refreshed with a (potentially biased) external random source and a cryptographic function that outputs random numbers from the internal state. It offers resilience, forward security, backward security and robustness against an attacker with (partial) knowledge of the internal state and (partial) control of the entropy source. We propose new security definitions for PRNGs with input, which encompass all the previous notions and capture the intuition that entropy from the source should be accumulated into the state of the PRNG. We apply these properties to give accurate assessments on the Linux PRNGs /dev/random and /dev/urandom. We then propose a simple and fast construction (in the standard model) that achieves our new definitions.

Joint work with Damien Vergnaud (ENS), David Pointcheval (ENS), Yevgeniy Dodis (NYU) and Daniel Wichs (NEU).

Dans un schéma à base de couplages, le chiffrement consiste en deux opérations sur la courbe elliptique: la multiplication scalaire d'un point et le calcul de couplage. Lorsqu'on dispose d'endomorphismes efficacement calculables de la courbe, on peut améliorer ces calculs, à l'aide d'un réseau euclidien qu'on associe à la base d'endomorphismes. Je présenterai d'abord des travaux de ma thèse, permettant d'améliorer le calcul de couplage à l'aide d'endomorphismes de petit degré.
Ensuite, je présenterai brièvement des travaux en cours (avec Aurore Guillevic) sur l'algorithme de multiplication scalaire pour des jacobiennes de courbes de genre 2. Je montrerai que dans ce cas, nous sommes confrontés à un problème lié à la réduction des réseaux de petite dimension.

The decision Learning With Errors (LWE) problem, introduced by Regev in 2005 has proven an invaluable tool for designing provably secure cryptographic protocols. We show that LWE is classically at least as hard as standard worst-case lattice problems, even with polynomial modulus. Previously this was only known under quantum reductions.
Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent cryptographic constructions, most notably fully homomorphic encryption schemes This work has been done with Z. Brakerski, C. Peikert, O. Regev and D. Stehlé.

Résumé en pdf.

Broadcast encryption has applications in Pay TV and content protection for DVDs. Broadcast encryption schemes have been proven secure under a variety of security models. We clarify the relationship between existing notions of security and provide a unifying framework. We then present an efficient scheme that fulfills the strongest security notion under standard assumptions.

Cheng et Wan étudient depuis 2004 comment le logarithme discret sur les corps non premiers se réduit à un certain problème de décodage des codes de Reed-Solomon. Leur objectif est de prouver la difficulté du décodage des codes de Reed-Solomon, en présence d'un grand nombre d'erreurs, sous l'hypothèse que le logarithme discret est difficile. Nous nous sommes proposés d'étudier la réduction dans un sens direct : comment utiliser des algorithmes de décodage connus pour construire un algorithme de calcul de logarithmes discrets sur les corps finis. La méthode se situe dans le contexte général de calcul de bases d'index, où la technique de découverte de relations repose sur le décodage. Dans un premier temps, nous avons utilisé des algorithmes de décodage unique, comme celui de Gao, par opposition au décodage en liste. Ces méthodes ont été implantées en Magma et NTL. Bien que cette méthode ne semble pas aussi performante que les méthodes classiques à la Adleman, il y a toutefois de nombreuses thématiques originales qui émergent.

Nous ferons aussi le point sur la difficulté du décodage des codes de Reed-Solomon.

Le calcul sécurisé multipartite est un ensemble de techniques cryptographiques permettant d'assurer des calculs interactifs à plusieurs parties, de telle façon que seul le résultat du calcul soit révélé et que les entrées de chaque partie restent secrètes. Ces dernières années, de nombreux progrès ont été réalisés pour que ces techniques, souvent assez lourdes en temps de calcul et en quantité de données échangées, deviennent plus utilisables en pratique.

L'exposé commencera par une introduction aux principales techniques de calcul sécurisé utilisées dans le cadre des applications à l'identification biométrique. Nous ferons ensuite une présentation de nos résultats récents dans ce domaine: la sécurisation d'un processus d'identification basé sur du filtrage biométrique (contrairement à l'état de l'art qui jusque là ne considérait que la sécurisation d'une identification basée sur des tests d'authentification sur toute la base) et l'accélération du calcul sécurisé de distances de Hamming.

It is well-known that several discrete-logarithm-based signature schemes are insecure when a few consecutive bits of the random nonces (used at each signature generation) are known for a reasonably small number of signatures (e.g. works by Howgrave-Graham and Smart [2001], Nguyen and Shparlinski [2002]). In practice, this knowledge may be due to a weak random number generator, a timing attack or using some probe on the device used to generate the signatures. In this talk, we will show that a private key for several discrete-logarithm-based authentication schemes (e.g. Schnorr identification or GPS signatures) can be efficiently recovered given a fraction of the random nonce bits (not necessarily consecutive) used in each signature. Asymptotically, for n signatures, the fraction of known bits can be as small as 2ln(2)/n (e.g. for a 128 bits security level, 355 sessions are enough on average to recover a private key in Schnorr identification scheme if a single bit of the nonce is leaked at each protocol execution).

Résumé en pdf.

De nombreuses attaques sur des cartes à puce de type Java Card ont été publiées ces dernières années. L'objectif de la plupart d'entre elles consiste à obtenir le code d'applications stockée dont on ne dispose ni du binaire di du source, et donc de violer la confidentialité de la plateforme de développement voir l'intégrité de ces applications en les modifiants à l'exécution. L'ajout d'énergie externe à la carte amène une autre dimension dans la mesure où il devient possible d'obtenir un comportement déviant de la carte et dès lors les attaques valides sur une plate forme de développement deviennent valides sur des produits. Nous montrons qu'il est même possible de franchir la couche de virtualisation et d'exécuter du code natif sur le processeur en d'autre terme d'être capable de reverser le système d'exploitation et donc de travailler en boite blanche pour d'autres attaques.

L'un des rôles de la cryptographie moderne est d'assurer l'authentification pour l'accès aux services numériques. Dans ce contexte, la traçabilité des personnes constitue bien souvent l'envers de la médaille. Afin de répondre à cette problématique majeure du respect de la vie privée, tout en maintenant des politiques de droits d'accès, il serait ainsi souhaitable de concilier authentification et anonymat. Parmi les outils que la cryptographie propose pour répondre à ce besoin, les accréditations anonymes permettent un usage anonyme d'attributs certifiés pour accéder à un service de façon authentifiée. Nous proposons dans un premier temps d'utiliser le concept de signatures caméléons dans le cadre des accréditations anonymes. Les signatures caméléons permettent la modification contrôlée, par une personne habilitée, d'un document signé après la génération de la signature. Nous proposons dans un second temps d'utiliser le concept de signatures agrégeables dans le cadre des accréditations anonymes. Les signatures agrégeables permettent la réunion de plusieurs signatures individuelles en un agrégat de taille constante. Leur utilisation dans les accréditations anonymes permet de simplifier l'utilisation de plusieurs accréditations au sein d'un même protocole d'authentification.

Among the variants of public key encryption schemes, the proxy re-encryption primitive allows a user, say Alice, to decide that a delegate, say Bob, will be able to read her private messages. This is made possible thanks to a third party, the proxy, which is given a re-encryption key to transform a ciphertext intended to Alice into a ciphertext intended to Bob. It exists different flavors of proxy re-encryption schemes. Some of them are unidirectional and allow the proxy to translate a ciphertext only from Alice to Bob. The other case is called bidirectional and permits the proxy, with only one re-encryption key, to translate from Alice to Bob but also from Bob to Alice. Most of the time, a bidirectional scheme is multi-hop, meaning that a ciphertext can be forwarded several times, and a unidirectional scheme is single-hop, meaning that a ciphertext can be transformed just once.

In this talk, we investigate the way to design a combined (single/multi hop) proxy re-encryption scheme which permits both unidirectional single-hop and bidirectional multi-hop. We formalize this concept, give several generic results and finally propose a practical construction. We argue that this case is very interesting in practice to the design of a secure and privacy-preserving cloud storage system, such as defined by Ateniese et al. in 2006, and particularly when the device of a user is lost.