«

»

Résumé des exposés du séminaire du 07 octobre

  • Matthieu Finiasz (ENSTA ParisTech) –  »Surcoût asymptotique en communication pour la protection de la vie privée dans une recherche par mots clefs »

Le chiffrement homomorphique (simplement homomorphique ou pleinement homomorphique) est un outil central des protocoles de protection de la vie privée. Il permet de chiffrer une requête qu’un serveur peut ensuite traiter (sans avoir à la déchiffrer) pour retourner une réponse que seul l’utilisateur peut déchiffrer. Ostrovsky et Skeith ont ainsi proposé en 2005 un protocole de recherche par mots clef, utilisant le cryptosystème de Paillier, permettant de masquer les mots recherchés. L’inconvénient principal de ce protocole (mis à part les calculs un peu lourds liés au chiffrement homomorphique) est le volume des communications : la taille de la requête et celle de la réponse du serveur.

Nous proposons deux variantes de ce protocole permettant d’optimiser ces communications en utilisant des codes correcteurs d’erreur : des codes de Reed-Solomon pour l’un, et des LDPC irréguliers pour l’autre. Asymptotiquement, le surcoût en communication lié à la protection de la vie privée peut devenir négligeable par rapport au volume des documents récupérés.

  • Christophe Guyeux (Université de Franche-Comté) – Annulé et reporté au 3 février
  • Maria Naya-Plasencia (Université de Versalilles-Saint Quentin)How to Improve Rebound Attacks (and New Applications)

Résumé : Rebound attacks are a state-of-the-art method for the analysis of hash functions.Such attacks are based on a well chosen differential path and have been applied to several hash functions from the SHA-3 competition, providing the best known analysis in these cases. In this talk, we will describe the main idea of rebound attacks, and we will show how can we improve most of them. This is done by identifying a common family of problems at the bottleneck of these attacks: « merging large lists with respect to a relation t ». Theses problems can be studied out of the rebound-attack context, and we provide several algorithms that efficiently solve some subcases, which are directly applicable to several practical instances.

Recently, we proposed new applications of this approach — recognizing an instance of the list-merging problem and applying the ad-hoc algorithm that solves it — which provide the best known analysis against the hash functions ECHO, JH (SHA-3 finalist) and the multipurpose primitive ARMADILLO2. We will describe the intuition behind these latest applications.