Soutenance de thèse de Christopher Goyet

*** Veuillez m'excuser pour les réceptions multiples ***


Bonjour à tous,

j'ai le plaisir de vous convier à ma soutenance de thèse, intitulée

Cryptanalyse algébrique par canaux auxiliaires.

qui aura lieu

le mercredi 7 novembre 2012 à 14h30
au LIP6 (Campus de Jussieu), salle 25-26-105,

Rapporteurs
Aline GOUGET (Expert Cryptographie, Gemalto)
François-Xavier STANDAERT (Professeur, Université
catholique de Louvain)

Examinateurs:
Jean-Claude BAJARD (Professeur, Université Pierre et Marie Curie)
Claude CARLET (Professeur, Université Paris 8)

Directeurs:
Jean-Charles FAUGÈRE (Directeur de Recherche INRIA, Centre
Paris-Rocquencourt)
Guénaël RENAULT (Maître de Conférences, Université Pierre et
Marie Curie)
Encadrant Industriel:
Olivier ORCIÈRE (Expert en cryptographie -- Thales communications & security)


Des plans d'accès au campus sont disponibles sur le site de l'UPMC
(http://www.upmc.fr/fr/universite/campus_et_sites/a_paris_et_en_idf/jussieu.html). L'accès à la salle de soutenance se fera par le premier étage de la tour
26.

La soutenance sera suivie d'un pot auquel vous êtes cordialement invités.


Résumé [English version below]
-------------------------------------------
La cryptanalyse algébrique consiste à modéliser une primitive
cryptographique par un système d'équations polynomiales dont la
résolution permet de retrouver la clef secrète. L'objectif de cette
thèse est d'évaluer comment une information extérieure permet
d'accélérer significativement la résolution. Nous supposons que
l'information extérieure est obtenue par canal auxiliaire,
c'est-à-dire par des mesures physiques, ou bien suite à un
comportement anormal provoqué par des attaques actives du type
injection de fautes, ou bien encore à cause de la présence d'un
logiciel malveillant.

Appliqués à la cryptographie asymétrique, ces travaux ont conduit à la
publication d'une nouvelle attaque contre les schémas de signature de
type DSA. Inspiré par la factorisation implicite de May et
Ritzenhofen, cette attaque suppose que les clefs éphémères utilisées
pour construire les signatures de plusieurs messages donnés partagent
un certain nombre de bits en commun dont les valeurs sont
inconnues. Par exemple, seulement 4 LSBs partagés sur les clefs
éphémères de 100 messages signés sont suffisants pour obtenir une
attaque avec taux de réussite de 100% et lorsque 32 LSBs sont
partagés, cette méthode ne nécessite plus que 8 messages signés.

En ce qui concerne les chiffrements par blocs, nous présentons une
étude théorique des "Algebraic Side Channel Attacks" (ASCA) qui
explique l'efficacité de ces attaques et qui permet de proposer des
conditions théoriques de résistance. Afin de maitriser la complexité
de cette attaque, nous utilisons principalement des techniques de
résolution par base de Gröbner plutôt que par solveur SAT. Nous
montrons ainsi que la complexité d'une résolution par base de Gröbner
dépend d'une nouvelle notion d'immunité algébrique et de la
distribution des informations de fuite.

Enfin, nous étendons les ASCA en considérant différents modèles de
fuite et étudions l'influence de ces modèles sur l'efficacité de
l'étape de résolution.

Abstract
------------
Algebraic cryptanalysis is a technique consisting in modeling a
cryptographic primitive with a system of multivariate polynomial
equations whose solutions give the secret key.
The goal of this thesis is to evaluate how external information can
significantly speed up the resolution. We assume that external
information is obtained by side channel, i.e. by physical measures, or
by an anomalous behavior caused by active attacks with fault injection
or even by the presence of malware.

Applied to asymmetric cryptography, this work led to the publication
of a new attack against DSA-like signature schemes. Inspired by
implicit factorization of May and Ritzenhofen, this new attack
requires that the ephemeral keys used to sign several messages share a
given number of bits without necessarily knowing the value of the
shared bits. As an example of our results, only 4 LSBs shared on each
ephemeral keys of 100 signed messages are enough to make a
never-failing attack and that with 32 LSBs shared, the method needs
only 8 signed messages.

On the other hand, with regard to the block ciphers, we present a
theoretical study of "Algebraic Side Channel Attacks" (ASCA) in order
to explain the effectiveness of the algebraic phase of these attacks
and then we deduce theoretical conditions for resistance. We mainly
use Gröbner basis method for the solving step rather than SAT solver
to control the complexity of this attack. Then we show that the
complexity of the Gröbner basis computation in these attacks depends
on a new notion of algebraic immunity and the distribution of
information leakage.

Finally, we extend the ASCA by considering various leakage models and
by studying the influence of these models on the effectiveness of the
solving step.

Bien cordialement,
Christopher Goyet

Invitation à la soutenance de thèse de Sergey Legtchenko

Bonjour,

J'ai le plaisir de vous inviter à ma soutenance de thèse intitulée
"Exploiting player behavior in distributed architectures for online
games" ainsi qu'au pot qui s'en suivra.

La soutenance, se déroulera le Jeudi 25 Octobre à 14h, Tour 25-26, 1
étage, salle 105 du Laboratoire d'Informatique de Paris 6 (LIP6) situé
au:

Université UPMC
4, Place Jussieu
75005 Paris

Plan d'accès: http://www.lip6.fr/informations/comment.php

---------------------------------------------------------------------
Abstract:

Massively Multiplayer Online Games (MMOGs) are a very popular class of
distributed systems with more than 20 millions of active users
worldwide. MMOG have strong applicative requirements in terms of data
consistency, persistence, responsiveness and scalability. Shaped by
the behavior of the players in-game, MMOG workloads are data-intensive
and hardly predictable. Despite extensive research in the area, none
of the currently existing architectures is able to fully satisfy all
the requirements in presence of such complex workloads.

This thesis investigates the ability of MMOG architectures to better
accomodate the workload by monitoring player activity at runtime. By
doing that, the system is able to detect evolutions that are hard to
foresee at startup, and dynamically allocate ressources to handle the
load. We describe different techniques of runtime player monitoring
and propose mechanisms to incorporate user behavior in the
architectural design of MMOGs. Our experimentations are based on
realistic workloads and show that our mechanisms have negligible
overhead and improve global performances of MMOG distributed
architectures.

Résumé de la thèse :

Durant la dernière décennie, Les jeux massivement multijoueurs (MMOGs)
sont devenus extrêmement populaires et comptent désormais plus de 20
millions d'utilisateurs actifs à travers le monde. Les MMOGs sont des
systèmes distribués ayant des contraintes applicatives fortes en terme
de cohérence de données, persistance, réactivité et passage à
l'échelle. L'évolution des besoins applicatifs du MMOG au cours du
temps est difficilement prévisible car dépendante du comportement des
joueurs dans le monde virtuel. C'est pourquoi, malgré un important
effort de recherche dans le domaine, aucune des architectures
proposées ne satisfait pleinement toutes les contraintes requises.

Cette thèse explore les capacités des architectures distribuées à
s'adapter à la charge applicative grâce à une prise en compte du
comportement des joueurs lors de l'exécution. Le système est alors
capable de détecter des évolutions qui sont difficiles à prévoir à
priori, et dynamiquement allouer les ressources nécessaires à
l'application. Nous décrivons différentes techniques de surveillance
des joueurs et proposons des moyens de prendre en compte ces
informations au niveau de l'architecture. Nos expériences, effectuées
dans des conditions réalistes, montrent que nos mécanismes ont un
surcoût limité et permettent d'améliorer les performances globales du
système.

Bien cordialement,

Sergey Legtchenko

Soutenance de thèse: "Environnement de conception multi-niveaux unifié appliqué aux systèmes mix=?iso-8859-1?Q?unifi=E9_appliqu=E9_aux_syst=E8mes_mixtes=22?=

Bonjour,

j'ai le plaisir de vous inviter à la soutenance de thèse de Michel
Vasilevski ainsi qu'au pot qui suivra.
La thèse de doctorat de M. Vasilevski est intitulée:
"Environnement de conception multi-niveaux unifié appliqué aux systèmes
mixtes".
Veuillez trouver un résumé de ce travail ci-dessous et l'adresse suivante:
http://www-soc.lip6.fr/~hassan/phd_mv.php

La soutenance aura lieu le jeudi 04 octobre 2012 à 14h00 dans la Salle
211, Couloir 55-65, 4, Place Jussieu, 75252 Paris.

Le jury sera composé de :
- A. Vachoux, Professeur, Ecole Polytechnique Fédérale de Lausanne,
Rapporteur.
- G. Jacquemod, Professeur, Polytech' Nice Sophia-Antipolis, Rapporteur.
- I. O'Connor, Professeur, Ecole Centrale de Lyon, Examinateur.
- S. Scotti, Ingénieur, STMicroelectronics, Examinateur.
- M.-M. Louerat, Chargée de recherche UPMC, Examinatrice.
- F. Pecheux, Maitre de conférences UPMC, Examinateur.
- A. Greiner, Professeur UPMC, Co-Directeur de thèse.
- H. Aboushady, Maitre de conférences UPMC, Directeur de thèse.

Cordialement,

Hassan Aboushady.

Abstract:
Nowadays, System-on-Chips containing digital, analog and RF blocks are
very common and are present in almost all electronic devices. A
system-level model containing both the analog and digital parts is very
important to determine the circuit specifications and to validate the
desired system performance. Tools available to model such systems are
currently lacking: Matlab, a widely used high-level simulator is not
compatible with the integrated circuit design flow. VHDL-AMS, a language
for analog mixed-signal circuit description is very time-consuming for
large systems. Recently, an AMS extension of SystemC, called SystemC AMS,
has filled this gap of Mixed Signal modeling in a system level. At the
circuit level, the conventional analog design methodologies have been
mainly based on the analog designer approximated calculations and
computer-aided simulations for tuning. The design time of analog and RF
blocks is very dependent on the designer's experience. When the CMOS
process or the specifications are changed a complete redesign is
necessary. Moreover, it is very difficult to optimize the overall design
of a complex mixed-signal circuit because the design and simulation
environments used for the digital blocks are very different from those
used for the analog and RF blocks. The following points summarize the
contributions realized in this work:
- The first implementation of a fairly complex Mixed Signal model in
SystemC-AMS: a Wireless Sensor Network node.
- Refined models for a generic and configurable approach of system-level
modeling.
- An accurate linear and nonlinear circuit performance evaluation tool for
system-level refined models back-annotation and circuit-level optimized
design.
- An optimized circuit design methodology based on an accurate sizing tool
and the circuit performance evaluation tool.
- A unified Mixed Signal design environment with a very strong interaction
between system-level simulation and optimized circuit-level design.

Soutenance de thèse de Pierre-Jean Spaenlehauer

Bonjour à tous,

j'ai le plaisir de vous convier à ma soutenance de thèse, intitulée

Résolution de systèmes multi-homogènes et déterminantiels.

qui aura lieu

le mardi 9 octobre 2012 à 14h30
au LIP6 (Campus de Jussieu), salle 25-26-105,

après avis des rapporteurs
Bernd STURMFELS (Professeur, University of California, Berkeley)
Gilles VILLARD (Directeur de Recherche CNRS, École Normale
Supérieure de Lyon)

et devant le jury composé de
Jean-Claude BAJARD (Examinateur -- Professeur, Université Pierre
et Marie Curie)
Jean-Charles FAUGÈRE (Directeur -- Directeur de Recherche INRIA,
Centre Paris-Rocquencourt)
Antoine JOUX (Examinateur -- Professeur associé, Université de
Versailles Saint-Quentin-en-Yvelines)
Mohab SAFEY EL DIN (Directeur -- Professeur, Université Pierre
et Marie Curie)
Bruno SALVY (Examinateur -- Directeur de Recherche INRIA, École
Normale Supérieure de Lyon)
Gilles VILLARD (Rapporteur -- Directeur de Recherche CNRS, École
Normale Supérieure de Lyon)

Des plans d'accès au campus sont disponibles sur le site de l'UPMC
(http://www.upmc.fr/fr/universite/campus_et_sites/a_paris_et_en_idf/jussieu.html).
L'accès à la salle de soutenance se fera par le premier étage de la tour
26.

La soutenance sera suivie d'un pot auquel vous êtes cordialement invités.


Résumé [English version below]
-------------------------------------------
De nombreux systèmes polynomiaux multivariés apparaissant en Sciences
de l'Ingénieur possèdent une structure algébrique spécifique. En
particulier, les structures multi-homogènes, déterminantielles et les
systèmes booléens apparaissent dans une variété d'applications.
Une méthode classique pour résoudre des systèmes polynomiaux
passe par le calcul d'une base de Gröbner de l'idéal associé au
système.
Cette thèse présente de nouveaux outils pour la résolution de tels
systèmes structurés.

D'une part, ces outils permettent d'obtenir sous des hypothèses de
généricité des bornes de complexité du calcul de base de Gröbner
de plusieurs familles de systèmes polynomiaux structurés (systèmes
bilinéaires, systèmes déterminantiels, systèmes définissant des points
critiques, systèmes booléens). Ceci permet d'identifier des familles
de systèmes pour lequels la complexité arithmétique de résolution
est polynomiale en le nombre de solutions.

D'autre part, cette thèse propose de nouveaux algorithmes
qui exploitent ces structures algébriques pour améliorer
l'efficacité du calcul de base de Gröbner et de la résolution
(systèmes multi-homogènes, systèmes booléens). Ces résultats sont
illustrés par des applications concrètes en cryptologie (cryptanalyse
des systèmes MinRank et ASC), en optimisation et en géométrie réelle
effective (calcul de points critiques).


Abstract
------------
Multivariate polynomial systems arising in Engineering Science often carry
algebraic structures related to the problems they stem from. In
particular, multi-homogeneous, determinantal structures and boolean
systems can be met in a wide range of applications.
A classical method to solve polynomial systems is to compute a Gröbner
basis of
the ideal associated to the system. This thesis provides new tools for
solving such structured systems in the context of Gröbner basis algorithms.

On the one hand, these tools bring forth new bounds on the complexity of
the
computation of Gröbner bases of several families of structured systems
(bilinear systems, determinantal systems, critical point systems,
boolean systems). In particular, it allows the identification of
families of
systems for which the complexity of the computation is polynomial in
the number of solutions.

On the other hand, this thesis provides new algorithms which take
profit of these algebraic structures for improving the efficiency of
the Gröbner basis computation and of the whole solving process
(multi-homogeneous systems, boolean systems). These results are
illustrated by applications in cryptology (cryptanalysis of MinRank),
in optimization and in effective real geometry (critical point
systems).



Bien cordialement,
Pierre-Jean Spaenlehauer

Invitation à la soutenance de thèse de David Buffoni

Bonjour,

j'ai le plaisir de vous inviter à ma soutenance de thèse intitulée :

"Learning-to-Rank consistent surrogates for Information Retrieval tasks"

La soutenance aura lieu le jeudi 4 octobre 2012 à 11h00,
en salle 25-26/101 (1er étage),
au Laboratoire d'Informatique de Paris 6 (LIP6),
4 Place Jussieu, 75005 Paris.

Le traditionnel pot, auquel vous êtes conviés, suivra dans la même salle.

---------------------------------------------------------------------

Résumé de la thèse :
Dans l'ère technologique actuelle, gérer, contrôler et rechercher
l'information est devenue une composante importante de notre vie
quotidienne tout en étant un challenge crucial pour les chercheurs. Dans
cette thèse, nous abordons le problème de la recherche d'objets parmi une
plus grande collection, domaine appelé Recherche d'Information.
Nous l'étudierons dans le contexte d'Apprentissage Statistique de
Fonctions d'Ordonnancement où le but est d'apprendre une fonction de score
tout en cherchant à minimiser un risque reflétant la qualité de la liste
d'ordonnancement. Ce risque non-optimisable en pratique est alors
substitué par un risque auxiliaire suivant la propriété de la consistance.
Basés sur cette théorie, nous montrons une façon de dériver deux fonctions
de coût auxiliaires consistantes et qui seront validées expérimentalement.

Ces considérations théoriques ne peuvent cependant pas être directement
appliquées puisque les algorithmes d'apprentissage sont très sensibles à
la qualité des données. Pour y remédier, nous nous focalisons sur les
pretraitements nécessaires pour rendre les algorithmes d'apprentissage
d'ordonnancement efficaces sur deux cas d'études : les problèmes de
Recherche d'Information XML et de Recherche d'Information Texte-Image.
Dans les deux cas, les algorithmes d'apprentissage sont dépendants de la
qualité de la supervision, de l'échantillonnage des exemples
d'entrainement et des caractéristiques de description extraites. Pour
clore ces études, nous décrivons les expériences où nous améliorons les
performances par rapport aux autres méthodes de l'état-de-l'art.

abstract :
In this era of technology, managing, controlling and retrieving
informations sources has become a key part of our daily lives, and at
the same time it presents a crucial challenge to researchers.
In this thesis we tackle the problem of searching for items from a whole
collection of objects, this is usually called Information Retrieval.
We address in a Learning-to-Rank fashion where the goal is to learn a
scoring function while minimizing a risk which reflects the quality of the
ranked list. In practice, this risk cannot be directly optimized and the
main goal is to design related surrogate losses thanks to the consistency
property.
Starting from this property, we show a way to derive two consistent
surrogate loss functions with respect to some traditional Information
Retrieval metrics. The resultant experiments prove our methodology.

All these theoretical considerations cannot be directly applied due to
the fact that learning algorithms are sensitives to the data quality.
We focus our attention on the preprocessing that needs to be done
on the data to make Learning-to-Rank algorithms efficient in a
two case study: XML retrieval and Text-Image Retrieval problems.
For both, Learning-to-Rank algorithms are dependent on the
quality of the supervision, the sampling of the training examples
and the extracted features describing them. Finally, we conduct a series
of experiments on these two problems to outperform traditional
state-of-the-art Information Retrieval methods.

Composition du jury :

Mohand Boughanem -- Université Paul Sabatier -- Rapporteur
Patrick Gallinari -- Université Pierre et Marie Curie -- Directeur
Patrice Perny -- Université Pierre et Marie Curie -- Examinateur
Liva Ralaivola -- Université Aix-Marseille -- Rapporteur
Nicolas Usunier -- Université Pierre et Marie Curie -- Co-directeur
Nicolas Vayatis -- Ecole Normale Supérieure de Cachan -- Examinateur

Bien cordialement,

David

Re: [Rappel] Soutenance de thèse d'Olivier Roussel le mardi 25 septembre

Bonjour à tous,

Je vous rappelle que ma soutenance de thèse a lieu aujourd'hui mardi 25
septembre, à 14h, à Jussieu. Vous êtes également conviés au pot qui suivra.

Olivier Roussel a écrit :

> J'ai le plaisir de vous inviter à ma soutenance publique de thèse de
> doctorat, intitulée :
>
> *Génération aléatoire de structures ordonnées par le modèle de Boltzmann*.
>
> Cette soutenance aura lieu le
> Mardi 25 septembre 2012 à 14h00 au
> LIP6 - Université Pierre et Marie Curie - UPMC
> Tour 25-26 - Premier étage - Salle 105
> Campus de Jussieu
> 4, place Jussieu - 75005 Paris
>
> Accès : http://www.lip6.fr/informations/comment.php
>
>
> devant le jury constitué de :
>
> M. Philipe Duchon, LaBRI - Université de Bordeaux 1 Rapporteur
> M. Conrado Martínez, LSI - Universitat Politècnica de Catalunya
> Rapporteur
> M. Olivier Bodini, LIPN - Université Paris-Nord Examinateur
> M. Christoph Dürr, LIP6 - Université Pierre et Marie Curie
> Examinateur
> M. Cyril Nicaud, LIGM - Université Paris-Est Examinateur
> M. Konstantinos Panagiotou - Ludwig-Maximilians-Universität München
> Examinateur
> M. Bruno Salvy, LIP - École Normale Supérieure de Lyon
> Examinateur
> Mme Michèle Soria, LIP6, Université Pierre et Marie Curie
> Directrice
>
>
> Vous êtes également chaleureusement conviés au pot qui suivra, dans la
> même salle.
>
>
> _Résumé_ :
> Dans le domaine de la combinatoire, la génération aléatoire d'objets est
> un problème central relié à de nombreux aspects de la science
> combinatoire, que ce soit à l'énumération exacte ou asymptotique, ou à
> la vérification de conjectures. De nombreuses méthodes ont été proposées
> afin de résoudre efficacement ce problème, dont le modèle de Boltzmann.
> Ce modèle, au prix d'un contrôle moindre sur la taille des objets
> générés, assure les propriétés de complexité linéaire dans beaucoup de
> cas réels, et de facilité d'automatisation pour de larges classes d'objets.
> Cette thèse vise à étendre encore les classes d'objets combinatoires sur
> lesquelles ce modèle de Boltzmann peut s'appliquer, tout en conservant
> les propriétés d'efficacité et d'automatisation. La première partie est
> une étude des algorithmes de générations de Boltzmann existants, ainsi
> que de leur propriétés et leurs fondations mathématiques sous-jacentes.
> Dans une seconde partie, nous présentons notre idée de biaiser ces
> algorithmes pour étendre leur domaine de validité. Nous proposons une
> extension très générale, avant de l'appliquer à plusieurs opérateurs
> combinatoires tels que la dérivation, le produit de shuffle et
> l'opération de dépointage. Enfin, nous présentons un algorithme de
> génération uniforme pour le produit de Hadamard.
> Nous appuyons nos algorithmes et résultats par des exemples et données
> expérimentales illustrant le bien fondé de nos méthodes.

--
Olivier Roussel

Invitation à la soutenance de thèse de Phu Hung LE

Bonjour,

J'ai le plaisir de vous inviter à ma soutenance de thèse intitulée
"Protocole de Routage Multi-chemin pour des Réseaux Ad Hoc".

Elle aura lieu au Laboratoire d'Informatique de Paris 6 (LIP6) à Jussieu
(http://www.lip6.fr/informations/comment.php), le vendredi 28 Septembre 2012,
à 14h30, dans la salle 101, couloir 25-26, 1er étage et vous êtes
également chaleureusement conviés au pot qui suivra dans la salle 101,
couloir 26-00 du même étage.

==========
Jury
==========

Le jury sera composé de:

Rapporteurs :
M.André-Luc BEYLOT, Professeur, IRIT/ENSEEIHT, Toulouse, France.
M.Steven MARTIN, HDR à l'Université Paris-Sud, France.

Examinateurs :
Mme.Dominique GAIT, Professeur, Université de Technologie,
Troyes, France.
Mme.Thi Mai Trang NGUYEN, HDR à UPMC, Paris, France.

Directeur :
M.Guy PUJOLLE, Professeur, UPMC Sorbonne Universités.




==========
Abstract
==========

Mobile ad hoc networks (MANETs) consist of a collection of wireless
mobile nodes that move freely and self-configure without a preexisting
communication infrastructure.

In MANETs, under the arbitrary movement of nodes and highly dynamic
topology conditions, the routing protocols for fixed networks do not
perform well. To adapt to the rapid change of topology, many routing
protocols have been proposed. However, most of them chose the minimum
hop-count routes. This choice can lead to significant reduction of the
network performance because communication quality via the chosen links
is not good. Thus, the evaluation of link quality is indispensable and
interference is a key factor to be considered. In the literature,
most of the existing interference-aware protocols are single path and
the consideration for interference range is limited. Several proposed
interference-aware multi-path protocols for MANETs are either not
highly efficient or have the computational complexity of NP-hard.

To tackle the above problems, we first determine an interference
region of each link including all nodes that can interfere with this
link. Then, we propose a formula to evaluate the interference level of
each link. Based on the formula of the link interference, we develop a
series of interference-aware multi-path routing protocols for mobile
ad hoc networks. These interference-aware multi-path routing protocols
minimize the impact of interference on the paths from the source to
the destination to increase the network performance. The computational
complexity of the protocols is polynomial and each of them is most
suitable for a type of network size.

To demonstrate the efficiency of the interference-aware multi-path
routing protocols, we compare them to prominent protocols in different
network sizes and a high mobility environment when the RTS/CTS
(Request-To-Send/Clear-To-Send) mechanism is alternatively turned on
and turned off. The simulation results show that our protocols
significantly improve packet delivery fraction, and reduce end-to-end
delay, routing overhead, and normalized routing load.

The RTS/CTS mechanism is to restrict the collision caused by the
hidden terminals. However, we show that the RTS/CTS mechanism is not
suitable for mobile ad hoc network based on the simulation results.



Cordialement,
Phu Hung LE