This thesis deals with issues of secure authentication and key management in the Internet of Things. It describes basic protocols used in IoT, cryptographic primitives, communication technologies in IoT and end elements. It also includes a measuring the performance of cryptographic primitives on Raspberry Pi and selecting the appropriate LPWAN simulation technology. The conclusion of the work is devoted to the simulation of a LoRaWAN network

The concept of wireless sensor network (WSN) is where tiny devices (sensor nodes), positioned fairly close to each other, are used for sensing and gathering data from its environment and exchange information through wireless connections between these nodes (e.g. sensor nodes distributed through out a bridge for monitoring the mechanical stress level of the bridge continuously). In order to easily deploy a relatively large quantity of sensor nodes, the sensor nodes are typically designed for low price and small size, thereby causing them to have very limited resources available (e.g. energy, processing power). Over the years, different security (cryptographic) primitives have been proposed and refined aiming at utilizing modern processor’s power e.g. 32-bit or 64-bit operation, architecture such as MMX (Multi Media Extension) and etc. In other words, security primitives have targeted at high-end systems (e.g. desktop or server) in software implementations. Some hardware-oriented security primitives have also been proposed. However, most of them have been designed aiming only at large message and high speed hashing, with no power consumption or other resources (such as memory space) taken into considerations. As a result, security mechanisms for ultra-low power (<500µW) devices such as the wireless sensor nodes must be carefully selected or designed with their limited resources in mind. The objective of this project is to provide implementations of security primitives (i.e. encryption and authentication) suitable to the WSN environment, where resources are extremely limited. The goal of the project is to provide an efficient building block on which the design of WSN secure routing protocols can be based on, so it can relieve the protocol designers from having to design everything from scratch. This project has provided three main contributions to the WSN field.  Provides analysis of different tradeoffs between cryptographic security strength and performances, which then provide security primitives suitable for the needs in a WSN environment. Security primitives form the link layer security and act as building blocks for higher layer protocols i.e. secure routing protocol.  Implements and optimizes several security primitives in a low-power microcontroller (TI MSP430F1232) with very limited resources (256 bytes RAM, 8KB flash program memory). The different security primitives are compared according to the number of CPU cycles required per byte processed, specific architectures required (e.g. multiplier, large bit shift) and resources (RAM, ROM/flash) required. These comparisons assist in the evaluation of its corresponding energy consumption, and thus the applicability to wireless sensor nodes.  Apart from investigating security primitives, research on various security protocols designed for WSN have also been conducted in order to optimize the security primitives for the security protocols design trend. Further, a new link layer security protocol using optimized security primitives is also proposed. This new protocol shows an improvement over the existing link layer security protocols. Security primitives with confidentiality and authenticity functions are implemented in the TinyMote sensor nodes from the Technical University of Vienna in a wireless sensor network. This is to demonstrate the practicality of the designs of this thesis in a real-world WSN environment. This research has achieved ultra-low power security primitives in wireless sensor network with average power consumption less than 3.5 µW (at 2 second packet transmission interval) and 700 nW (at 5 second packet transmission interval). The proposed link layer security protocol has also shown improvements over existing protocols in both security and power consumption. / Dissertation (MEng (Computer Engineering))--University of Pretoria, 2008. / Electrical, Electronic and Computer Engineering / unrestricted

Dans cette thèse, nous étudions les constructions cryptographiques prouvées pour la protection de la vie privée. Pour cela nous nous sommes intéressés aux preuves et arguments à divulgation nulles de connaissance et leurs applications. Un exemple de ces constructions est la signature de groupe. Ce protocole a pour but de permettre à un utilisateur de s'authentifier comme appartenant à un groupe, sans révéler son identité. Afin que les utilisateurs restent responsable de leurs agissements, une autorité indépendante est capable de lever l'anonymat d'un utilisateur en cas de litige. Une telle construction peut ainsi être utilisée, par exemple, dans les systèmes de transport en commun. Un utilisateur qui rentre dans un bus prouve ainsi son appartenance aux utilisateurs possédant un abonnement valide, sans révéler qui il est, et évitant ainsi que la société de transport ne le trace. En revanche, en cas d'incident sur le réseau, la société peut faire appel à la police pour lever l'anonymat des usagers présents au moment de l'incident. Nous avons proposé deux constructions de ces signatures de groupe, prouvées sûres sous des hypothèses simples dans le monde des couplages et des réseaux euclidiens. Dans la continuité de ces travaux, nous avons aussi proposé la première construction de chiffrement de groupe (l'équivalent de la signature de groupe pour le chiffrement) à base de réseaux euclidiens. Finalement, ces travaux nous ont amené à la construction d'un schéma de transfert inconscient adaptatif avec contrôle d'accès à base de réseaux euclidiens. Ces constructions à base de réseaux ont été rendues possibles par des améliorations successives de l'expressivité du protocole de Stern, qui reposait initialement sur la difficulté du problème du décodage de syndrome. / In this thesis, we study provably secure privacy-preserving cryptographic constructions.We focus on zero-knowledge proofs and their applications.Group signatures are an example of such constructions.This primitive allows users to sign messages on behalf of a group (which they formerly joined), while remaining anonymous inside this group.Additionally, users remain accountable for their actions as another independent authority, a judge, is empowered with a secret information to lift the anonymity of any given signature.This construction has applications in anonymous access control, such as public transportations.Whenever someone enters a public transportation, he signs a timestamp. Doing this proves that he belongs to the group of people with a valid subscription.In case of problem, the transportation company hands the record of suspicious signatures to the police, which is able to un-anonymize them.We propose two constructions of group signatures for dynamically growing groups. The first is based on pairing-related assumptions and is fairly practical. The second construction is proven secure under lattice assumptions for the sake of not putting all eggs in the same basket.Following the same spirit, we also propose two constructions for privacy-preserving cryptography.The first one is a group encryption scheme, which is the encryption analogue of group signatures. Here, the goal is to hide the recipient of a ciphertext who belongs to a group, while proving some properties on the message, like the absence of malwares. The second is an adaptive oblivious transfer protocol, which allows a user to anonymously query an encrypted database, while keeping the unrequested messages hidden.These constructions were made possible through a series of work improving the expressiveness of Stern's protocol, which was originally based on the syndrome decoding problem.

Dans cette thèse,nous étudions comment exploiter des contraintes spatio-temporelles,notamment le principe d'impossibilité de transmission supraluminique,dans le but de créer des primitives cryptographiques sûres,par exemple la vérification de position ou la "mise en gage de bit''(bit commitment). D'après le principe d'impossibilité de transmission supraluminique,aucun vecteur physique d'information ne peut voyager plus vite que la vitesse de la lumière. Ce principe entraîne une contrainte sur le temps de communication entre deux points éloignés. Ce délai dans le transfert d'information peut être utilisé comme une contrainte temporelle interdisant la communication. En cryptographie multi-agents,il est connu que l'hypothèse de non-communication entre les agents permet de réaliser de manière sécurisée de nombreuses primitives comme la "mise en gage de bit'' et l'un des buts de cette thèse est de comprendre à quel point les contraintes spatio-temporelles peuvent être exploitèes pour simuler des scénarios de non-communication. Dans la première partie de cette thèse nous étudions comment utiliser une contrainte de non-communication pour essayer de vérifier la position d'une personne.Dans la dernière partie,nous nous penchons sur deux exemples de protocoles de ``mise en gage de bit'' relativistes afin d'en étudier la sécurité contre des adversaires classiques. Pour conclure cette thèse,nous mentionnons quelques problèmes ouverts intéréssants. Ces problèmes ouverts peuvent être très utiles pour comprendre le rôle de contraintes spatio-temporelles,par exemple de l'impossibilité de transmission supraluminique,dans la conception de primitives cryptographiques parfaitement sûres. / In this thesis we have studied how to exploit relativistic constraints such as the non-superluminal signalling principle to design secure cryptographic primitives like position-verification and bit commitment. According to non-superluminal signalling principle, no physical carrier of information can travel faster than the speed of light. This put a constraint on the communication time between two distant stations. One can consider this delay in information transfer as a temporal non-communication constraint. Cryptographic primitives like bit-commitment, oblivious transfer can be implemented with perfect secrecy under such non-communication assumption between the agents. The first part of this thesis has studied how non-signalling constraints can be used for secure position verification. Here, we have discussed about a strategy which can attack any position verification scheme. In the next part of this thesis we have discussed about the nonlocal games, relevant for studying relativistic bit commitment protocols. We have established an upper bound on the classical value of such family of games. The last part of this thesis discusses about two relativistic bit commitment protocols and their security against classical adversaries. We conclude this thesis by giving a brief summary of the content of each chapter and mentioning interesting open problems. These open problems can be very useful for better understanding of the role of spacetime constraints such as non-superluminal signalling in designing perfectly secure cryptographic primitives.

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.

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.

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.

The thesis focuses on cryptographic algorithms of low performance devices, and mutual authentication of authentication server and user using smart cards. In the first part of this thesis the cryptography, cryptographic primitives, cryptographic goals, security models and cryptographic algorithms of low performance devices are presented. The second part focuses on low performance devices as RFID tags, NFC technology, microcontrollers and smart cards (.NET cards, java cards, MIFARE cards). The practical part deals with the comparison of chosen low performance devices and measure the time required for encryption and decryption using different cryptographic algorithms on Gemalto .NET Smart Card V2+. This thesis describes and explains the three authentication schemes for mutual authentication of remote server and user using smart cards. The new authentication scheme, which is based on the second related scheme, attempts to eliminate possible security attacks and keeps efficiency. For all four authentication schemes the application is implemented to test required time for authentication of server and user using smart cards.

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. / Quantum computing allows us to revisit the study of quantum cryptographic primitives with information theoretic security. In 1984, Bennett and Brassard presented a protocol of quantum key distribution. In this protocol, Alice and Bob cooperate in order to share a common secret key k, which has to be unknown for a third party that has access to the communication channel. They showed how to perform this task quantumly with an information theoretic security; which is impossible classically.In my thesis, I study cryptographic primitives with two players that do not trust each other. I study mainly coin flipping and bit commitment. Classically, both these primitives are impossible classically with information theoretic security. Quantum protocols for these primitives where constructed where cheating players could cheat with probability stricly smaller than 1. However, Lo, Chau and Mayers showed that these primitives are impossible to achieve perfectly even quantumly if one requires information theoretic security. I study to what extent imperfect protocols can be done in this setting.In the first part, I construct a quantum coin flipping protocol with cheating probabitlity of 1/root(2) + eps for any eps > 0. This completes a result by Kitaev who showed that in any quantum coin flipping protocol, one of the players can cheat with probability at least 1/root(2). I also constructed a quantum bit commitment protocol with cheating probability 0.739 + eps for any eps > 0 and showed that this protocol is essentially optimal. I also derived some upper and lower bounds for quantum oblivious transfer, which is a universal cryptographic primitive.In the second part, I study some practical aspects related to these primitives. I take into account losses than can occur when measuring a quantum state. I construct a Quantum Coin Flipping and Quantum Bit Commitment protocols which are loss-tolerant and have cheating probabilities of 0.859. I also construct these primitives in the device independent model, where the players do not trust their quantum device. Finally, in the third part, I study these cryptographic primitives with information theoretic security. More precisely, I study the relationship between computational quantum bit commitment and quantum zero-knowledge protocols.

Cette thèse étudie deux aspects d'interaction entre deux joueurs dans le modèle du calcul et de la communication quantique.Premièrement, elle étudie deux primitives cryptographiques quantiques, des briques de base pour construire des protocoles cryptographiques complexes entre deux joueurs, comme par exemple un protocole d'identification. La première primitive est la ``mise en gage quantique". Cette primitive ne peut pas être réalisée de manière inconditionnellement sûre, mais il possible d'avoir une sécurité lorsque les deux parties sont soumis à certaines contraintes additionnelles. Nous étudions cette primitive dans le cas où les deux joueurs sont limités à l'utilisation d'états et d'opération gaussiennes, un sous-ensemble de la physique quantique central en optique, donc parfaitement adapté pour la communication via fibres optiques. Nous montrons que cette restriction ne permet malheureusement pas la réalisation de la mise en gage sûre. Pour parvenir à ce résultat, nous introduisons la notion de purification intrinsèque, qui permet de contourner l'utilisation du théorème de Uhlman, en particulier dans le cas gaussien. Nous examinons ensuite une primitive cryptographique plus faible, le ``tirage faible à pile ou face'', dans le modèle standard du calcul quantique. Carlos Mochon a donné une preuve d'existence d'un tel protocole avec un biais arbitrairement petit. Nous donnons une interprétation claire de sa preuve, ce qui nous permet de la simplifier et de la raccourcir grandement.La seconde partie de cette thèse concerne l'étude de méthodes pour prouver des bornes inférieures dans le modèle de la complexité en requête. Il s'agit d'un modèle de complexité central en calcul quantique dans lequel de nombreux résultats majeurs ont été obtenus. Dans ce modèle, un algorithme ne peut accéder à l'entrée uniquement en effectuant des requêtes sur chacun des bits de l'entrée. Nous considérons une extension de ce modèle dans lequel un algorithme ne calcule pas une fonction, mais doit générer un état quantique. Cette généralisation nous permet de comparer les différentes méthodes pour prouver des bornes inférieures dans ce modèle. Nous montrons d'abord que la méthode par adversaire ``multiplicative" est plus forte que la méthode ``additive". Nous montrons ensuite une réduction de la méthode polynomiale à la méthode multiplicative, ce qui permet de conclure à la supériorité de la méthode par adversaire multiplicative sur toutes les autres méthodes. Les méthodes par adversaires sont en revanche souvent difficiles à utiliser car elles nécessite le calcul de normes de matrices de très grandes tailles. Nous montrons comment l'étude des symétries d'un problème simplifie grandement ces calculs. Enfin, nous appliquons ces formules pour prouver la borne inférieure optimale du problème INDEX-ERASURE un problème de génération d'état quantique lié au célèbre problème GRAPH-ISOMORPHISM. / 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.