L'objet de cette thèse est l'étude de diverses primitives cryptographiques utiles dans des protocoles Diffie-Hellman. Nous étudions tout d'abord les protocoles Diffie-Helmman sur des structures commutatives ou non. Nous en proposons une formulation unifiée et mettons en évidence les différents problèmes difficiles associés dans les deux contextes. La première partie est consacrée à l'étude de pseudo-paramétrisations de courbes algébriques en temps constant déterministe, avec application aux fonctions de hachage vers les courbes. Les propriétés des courbes algébriques en font une structure de choix pour l'instanciation de protocoles reposant sur le problème Diffie-Hellman. En particulier, ces protocoles utilisent des fonctions qui hachent directement un message vers la courbe. Nous proposons de nouvelles fonctions d'encodage vers les courbes elliptiques et pour de larges classes de fonctions hyperelliptiques. Nous montrons ensuite comment l'étude de la géométrie des tangentes aux points d'inflexion des courbes elliptiques permet d'unifier les fonctions proposées tant dans la littérature que dans cette thèse. Dans la troisième partie, nous nous intéressons à une nouvelle instanciation de l'échange Diffie-Hellman. Elle repose sur la difficulté de résoudre un problème de factorisation dans un anneau de polynômes non-commutatifs. Nous montrons comment un problème de décomposition Diffie-Hellman sur un groupe non-commutatif peut se ramener à un simple problème d'algèbre linéaire pourvu que les éléments du groupe admettent une représentation par des matrices. Bien qu'elle ne soit pas applicable directement au cas des polynômes tordus puisqu'ils n'ont pas d'inverse, nous profitons de l'existence d'une notion de divisibilité pour contourner cette difficulté. Finalement, nous montrons qu'il est possible de résoudre le problème Diffie-Hellman sur les polynômes tordus avec complexité polynomiale. / In this thesis, we study several cryptographic primitives of use in Diffie-Hellman like protocols. We first study Diffie-Hellman protocols on commutative or noncommutative structures. We propose an unified wording of such protocols and bring out on which supposedly hard problem both constructions rely on. The first part is devoted to the study of pseudo-parameterization of algebraic curves in deterministic constant time, with application to hash function into curves. Algebraic curves are indeed particularly interesting for Diffie-Hellman like protocols. These protocols often use hash functions which directly hash into the curve. We propose new encoding functions toward elliptic curves and toward large classes of hyperelliptic curves. We then show how the study of the geometry of flex tangent of elliptic curves unifies the encoding functions as proposed in the litterature and in this thesis. In the third part, we are interested in a new instantiation of the Diffie-Hellman key exchange. It relies on the difficulty of factoring in a non-commutative polynomial ring. We show how to reduce a Diffie-Hellman decomposition problem over a noncommutative group to a simple linear algebra problem, provided that group elements can be represented by matrices. Although this is not directly relevant to the skew polynomial ring because they have no inverse, we use the divisibility to circumvent this difficulty. Finally, we show it's possible to solve the Diffie-Hellman problem on skew polynomials with polynomial complexity.

Résumé non transmis / Summary not transmitted

L'avènement de l'informatique quantique permet de réétudier les primitives cryptographiques avec une sécurité inconditionnelle, c'est à dire sécurisé même contre des adversaires tout puissants. En 1984, Bennett et Brassard ont construit un protocole quantique de distribution de clé. Dans ce protocole, deux joueurs Alice et Bob coopèrent pour partager une clé secrète inconnue d'une tierce personne Eve. Ce protocole a une sécurité inconditionnelle et n'a pasd'équivalent classique.Dans ma thèse, j'ai étudié les primitives cryptographiques à deux joueurs où ces joueurs ne se font pas confiance. J'étudie principalement le pile ou face quantique et la mise-en-gage quantique de bit. En informatique classique, ces primitivessont réalisables uniquement avec des hypothèses calculatoires, c'est-à-dire en supposant la difficulté d'un problème donné. Des protocoles quantiques ont été construits pour ces primitives où un adversaire peut tricher avec une probabilité constante strictement inférieure à 1, ce qui reste impossible classiquement. Néanmoins, Lo et Chau ont montré l'impossibilité de créer ces primitives parfaitement même en utilisant l'informatique quantique. Il reste donc à déterminer quelles sont les limites physiques de ces primitives.Dans une première partie, je construis un protocole quantique de pile ou face où chaque joueur peut tricher avec probabilité au plus 1/racine(2) + eps pour tout eps > 0. Ce résultat complète un résultat de Kitaev qui dit que dans un jeu de pile ou face quantique, un joueur peut toujours tricher avec probabilité au moins 1/racine(2). J'ai également construit un protocole de mise-en-gage de bit quantique optimal où un joueur peut tricher avec probabilité au plus 0,739 + eps pour tout eps > 0 puis ai montré que ce protocole est en fait optimal. Finalement, j'ai dérivé des bornes inférieures et supérieures pour une autre primitive: la transmission inconsciente, qui est une primitive universelle.Dans une deuxième partie, j'intègre certains aspects pratiques dans ces protocoles. Parfois les appareils de mesure ne donnent aucun résultat, ce sont les pertes dans la mesure. Je construis un protocole de lancer de pièce quantique tolérant aux pertes avec une probabilité de tricher de 0,859. Ensuite, j'étudie le modèle dispositif-indépendant où on ne suppose plus rien sur les appareils de mesure et de création d'état quantique.Finalement, dans une troisième partie, j'étudie ces primitives cryptographiques avec un sécurité computationnelle. En particulier, je fais le lien entre la mise en gage de bit quantique et les protocoles zero-knowledge quantiques.

Dans la première partie, on dérive formellement les équations \PFS (\textbf{P}ressurised and \textbf{F}ree \textbf{S}urface) pour les écoulements mixtes en conduite fermée avec variation de géométrie. On écrit l'approximation de ces équations à l'aide d'un solveur VFRoe et d'un solveur cinétique en décentrant les termes sources aux interfaces. En particulier, on propose le décentrement d'un terme de friction, donnée par la loi de Manning-Strickler, en introduisant la notion de \emph{pente dynamique}. Enfin, on construit un schéma bien équilibré préservant les états stationnaires au repos en définissant une matrice à profil stationnaire conçue pour le schéma VFRoe. Suivant cette idée, on construit, en toute généralité, un schéma bien équilibré préservant tous les états stationnaires. Pour traiter les points de transitions (i.e. le changement de type d'écoulement surface libre vers charge et vice et versa), on étend la méthode des \og ondes fantômes\fg~ dans ce contexte et on propose un traitement complètement cinétique. Dans la deuxième partie, on étudie des équations primitives compressibles simplifiées dans le cadre de la modélisation de la dynamique de l'atmosphère. En particulier, on obtient un résultat d'existence de solutions faibles globales en temps en dimension $2$ d'espace. On établit également un résultat de stabilité de solutions faibles pour le modèle en dimension $3$ d'espace. À cet égard, on introduit un changement de variables convenable qui permet de transformer les équations initiales en un modèle plus simple à étudier. Dans la troisième et dernière partie, on présente une courte introduction à la cavitation. En particulier, on rappelle les différents types de cavitation et les modèles mathématiques de Rayleigh-Plesset pour l'étude d'une bulle isolée et un modèle de mélange plus complexe. En vue de modéliser la cavitation dans les conduites fermées, on introduit un modèle à deux couches pour prendre en compte, dans un premier temps, l'effet d'une poche d'air comprimée par la surface libre et les bords de la conduite. En particulier, le système obtenu, à $4$ équations, est généralement non hyperbolique et ses valeurs propres ne sont pas calculables explicitement. On propose alors une approximation numérique basée sur un schéma cinétique mono-couche. Dans le dernier chapitre, on dérive formellement un modèle de transport de sédiments basé sur l'équation de Vlasov couplée à des équations de Navier-Stokes compressibles avec un tenseur de viscosité anisotrope. Ce modèle est ensuite obtenu par le biais de deux analyses asymptotiques.

We present robust explicit construction of 3D configuration spaces using controlled linear perturbation. The input is two planar parts: a fixed set and a moving set, where each set is bounded by circle segments. The configuration space is the three-dimensional space of Euclidean transformation (translations plus rotations) of the moving set relative to the fixed set. The goal of constructing the 3D configuration space is to determine the boundary representation of the free space where the intersection of the moving set and fixed set is empty. To construct the configuration space, we use the controlled linear perturbation algorithm. The controlled linear perturbation algorithm assigns function signs that are correct for a nearly minimal input perturbation. The output of the algorithm is a consistent set of function signs. This approach is algorithm-independent, and the overhead over traditional floating point methods is reasonable. If the fixed and moving sets are computer representations of physical objects, then computing the configuration space greatly aids in many computational geometry problems. The main focus of computing the configuration space is for the path planning problem. We must find if a path exists from the start to the goal, where the fixed set is the obstacle, and the moving set is the object trying to reach the goal.

This dissertation studies two different aspects of two-player interaction in the model of quantum communication and quantum computation.First, we study two cryptographic primitives, that are used as basic blocks to construct sophisticated cryptographic protocols between two players, e.g. identification protocols. The first primitive is ''quantum bit commitment''. This primitive cannot be done in an unconditionally secure way. However, security can be obtained by restraining the power of the two players. We study this primitive when the two players can only create quantum Gaussian states and perform Gaussian operations. These operations are a subset of what is allowed by quantum physics, and plays a central role in quantum optics. Hence, it is an accurate model of communication through optical fibers. We show that unfortunately this restriction does not allow secure bit commitment. The proof of this result is based on the notion of ''intrinsic purification'' that we introduce to circumvent the use of Uhlman's theorem when the quantum states are Gaussian. We then examine a weaker primitive, ''quantum weak coin flipping'', in the standard model of quantum computation. Mochon has showed that there exists such a protocol with arbitrarily small bias. We give a clear and meaningful interpretation of his proof. That allows us to present a drastically shorter and simplified proof.The second part of the dissertation deals with different methods of proving lower bounds on the quantum query complexity. This is a very important model in quantum complexity in which numerous results have been proved. In this model, an algorithm has restricted access to the input: it can only query individual bits. We consider a generalization of the standard model, where an algorithm does not compute a classical function, but generates a quantum state. This generalization allows us to compare the strength of the different methods used to prove lower bounds in this model. We first prove that the ''multiplicative adversary method'' is stronger than the ''additive adversary method''. We then show a reduction from the ''polynomial method'' to the multiplicative adversary method. Hence, we prove that the multiplicative adversary method is the strongest one. Adversary methods are usually difficult to use since they involve the computation of norms of matrices with very large size. We show how studying the symmetries of a problem can largely simplify these computations. Last, using these principles we prove the tight lower bound of the INDEX-ERASURE problem. This a quantum state generation problem that has links with the famous GRAPH-ISOMORPHISM problem.

In der vorliegenden Arbeit wird die flexible Steuerungsarchitektur Apeca für Systeme der Robotik sowie der robotergestützten Fertigungstechnik vorgestellt. Dafür werden verschiedene Anforderungen identifiziert und innerhalb eines Entwurfs vereint. Ein Hauptaugenmerk des dabei entstandenen Konzeptes ist es, einen vereinfachten Engineeringprozess für den Steuerungsentwurf zu ermöglichen. Dieser Ansatz wird durch die Verwendung von Aktionsprimitiven ermöglicht, die in Form atomarer Systemverhalten in einer speziellen Modulhierarchie eingesetzt werden. Hierzu erfolgt innerhalb der Steuerungsarchitektur eine Trennung zwischen einem funktionsorientierten verhaltensbasierten Modell zur hierarchischen sowie funktionell parallelen Ausführung von Aktionsprimitiven und einem ablauforientierten Modell zur aufgabenabhängigen Aktivierung derselben. Mit Hilfe eines Nutzerkonzepts werden diese Modelle verschiedenen Anwendern zugeordnet. Die objektorientierte Realisierung dieses Entwurfs ermöglicht die Verwendung und Synchronisation von mehreren Teilsystemen innerhalb einer Steuerung. In der Arbeit wird sowohl der entstandene Entwurf diskutiert als auch eine prototypische Implementierung vorgestellt. Abschließend werden die Ergebnisse anhand verschiedener Demonstrationsszenarien präsentiert. / In this present work, the Apeca framework, a flexible control architecture for robotic systems, is introduced. The conceptual design combines different requirements identified in miscellaneous robotic control approaches. The main focus of the resulting concept is on a simplified engineering process for the controller design. This approach is supported by the use of atomic system behaviors, the so called action primitives, in a special module hierarchy. For this purpose a distinction between a functional behavior based system model with hierarchically and also parallelly executed action primitives and a sequential control system model with a task-dependent activation of the primitives is proposed. These models are assigned to different users through a distinct user concept. An object-oriented implementation of the proposed architecture allows the utilization and synchronisation of multiple (sub-)systems within one framework. In this work the proposed framework will be discussed, a prototypical implementation will be presented and results based on different experimental scenarios will be shown.

Dans plusieurs tâches de la robotique, la vision est considérée comme l’élément essentiel avec lequel la perception de l’environnement ou l’interaction avec d’autres utilisateurs peut se réaliser. Néanmoins, les artefacts potentiellement présents dans les images capturées rendent la tâche de reconnaissance et d’interprétation de l’information visuelle extrêmement compliquée. Il est de ce fait, très important d’utiliser des primitives robustes, stables et ayant un taux de répétabilité élevé afin d’obtenir de bonnes performances. Cette thèse porte sur les problèmes de localisation et de détection de fermeture de boucle d’un robot mobile en utilisant la saillance visuelle. Les résultats en termes de précision et d’efficacité des applications de localisation et de détection de fermeture sont évalués et comparés aux résultats obtenus avec des approches de l’état de l’art sur différentes séquences d’images acquises en milieu extérieur. Le principal inconvénient avec les modèles proposés pour l’extraction de zones de saillance est leur complexité de calcul, ce qui conduit à des temps de traitement important. Afin d’obtenir un traitement en temps réel, nous présentons dans ce mémoire l’implémentation du détecteur de régions saillantes sur la plate forme reconfigurable DreamCam. / In several tasks of robotics, vision is considered to be the essential element by which the perception of the environment or the interaction with other users can be realized. However, the potential artifacts in the captured images make the task of recognition and interpretation of the visual information extremely complicated. It is therefore very important to use robust, stable and high repeatability rate primitives to achieve good performance. This thesis deals with the problems of localization and loop closure detection for a mobile robot using visual saliency. The results in terms of accuracy and efficiency of localization and closure detection applications are evaluated and compared to the results obtained with the approaches provided in literature, both applied on different sequences of images acquired in outdoor environnement. The main drawback with the models proposed for the extraction of salient regions is their computational complexity, which leads to significant processing time. To obtain a real-time processing, we present in this thesis also the implementation of the salient region detector on the reconfigurable platform DreamCam.

Connaître la position 3D d’instruments robotisés peut être très utile dans le contexte chirurgical. Nous proposons deux méthodes automatiques pour déduire la pose 3D d’un instrument avec une unique section pliable et équipé avec des marqueurs colorés, en utilisant uniquement les images fournies par la caméra monoculaire incorporée dans l'endoscope. Une méthode basée sur les graphes permet segmenter les marqueurs et leurs coins apparents sont extraits en détectant la transition de couleur le long des courbes de Bézier qui modélisent les points du bord. Ces primitives sont utilisées pour estimer la pose 3D de l'instrument en utilisant un modèle adaptatif qui prend en compte les jeux mécaniques du système. Pour éviter les limites de cette approche dérivants des incertitudes sur le modèle géométrique, la fonction image-position-3D peut être appris selon un ensemble d’entrainement. Deux techniques ont été étudiées et améliorées : réseau des fonctions à base radiale avec noyaux gaussiens et une régression localement pondérée. Les méthodes proposées sont validées sur une cellule expérimentale robotique et sur des séquences in-vivo. / Knowing the 3D position of robotized instruments can be useful in surgical context for e.g. their automatic control or gesture guidance. We propose two methods to infer the 3D pose of a single bending section instrument equipped with colored markers using only the images provided by the monocular camera embedded in the endoscope. A graph-based method is used to segment the markers. Their corners are extracted by detecting color transitions along Bézier curves fitted on edge points. These features are used to estimate the 3D pose of the instrument using an adaptive model that takes into account the mechanical plays of the system. Since this method can be affected by model uncertainties, the image-to-3d function can be learned according to a training set. We opted for two techniques that have been improved : Radial Basis Function Network with Gaussian kernel and Locally Weighted Projection. The proposed methods are validated on a robotic experimental cell and in in-vivo sequences.

This master thesis deals with the implementation of variants of cryptographic libraries containing primitives for elliptic curves. By creating custom metering charts to compare each implementation. The main task was not only the implementation of libraries but also the design and implementation of test scenarios together with the creation of measurement methods for different libraries and hardware platforms. As a result, a number of experimental tests were conducted on different curves and their parameters so that the results of the work included complex problems of elliptic curves in cryptography. The main parameters were power, time and memory consumption.