La recherche sur les bases de données chiffrées vise à rendre efficace une tâche apparemment simple : déléguer le stockage de données à un serveur qui ne serait pas de confiance, tout en conservant des fonctionnalités de recherche. Avec le développement des services de stockage dans le Cloud, destinés aussi bien aux entreprises qu'aux individus, la mise au point de solutions efficaces à ce problème est essentielle pour permettre leur déploiement à large échelle. Le principal problème de la recherche sur bases de données chiffrées est qu'un schéma avec une sécurité ''parfaite'' implique un surcoût en termes de calcul et de communication qui serait inacceptable pour des fournisseurs de services sur le Cloud ou pour les utilisateurs - tout du moins avec les technologies actuelles. Cette thèse propose et étudie de nouvelles notions de sécurité et de nouvelles constructions de bases de données chiffrées permettant des recherches efficaces et sûres. En particulier, nous considérons la confidentialité persistante et la confidentialité future de ces bases de données, ce que ces notions impliquent en termes de sécurité et d'efficacité, et comment les réaliser. Ensuite, nous montrons comment protéger les utilisateurs de bases de données chiffrées contre des attaques actives de la part du serveur hébergeant la base, et que ces protections ont un coût inévitable. Enfin, nous étudions les attaques existantes contre ces bases de données chiffrées et comment les éviter. / Searchable encryption aims at making efficient a seemingly easy task: outsourcing the storage of a database to an untrusted server, while keeping search features. With the development of Cloud storage services, for both private individuals and businesses, efficiency of searchable encryption became crucial: inefficient constructions would not be deployed on a large scale because they would not be usable. The key problem with searchable encryption is that any construction achieving ''perfect security'' induces a computational or a communicational overhead that is unacceptable for the providers or for the users --- at least with current techniques and by today's standards. This thesis proposes and studies new security notions and new constructions of searchable encryption, aiming at making it more efficient and more secure. In particular, we start by considering the forward and backward privacy of searchable encryption schemes, what it implies in terms of security and efficiency, and how we can realize them. Then, we show how to protect an encrypted database user against active attacks by the Cloud provider, and that such protections have an inherent efficiency cost. Finally, we take a look at existing attacks against searchable encryption, and explain how we might thwart them.

In this thesis we review bilinear maps and their usage in modern cryptography, i.e. the theoretical framework of pairing-based cryptography including the underlying mathematical hardness assumptions. The theory is based on algebraic structures, elliptic curves and divisor theory from which explicit constructions of pairings can be defined. We take a closer look at the more commonly known Weil pairing as an example. We also elaborate on pairings in practice and give numerical examples of how pairing-friendly curves are defined and how different type of cryptographical schemes works.

Message Authentication Codes (MACs) are valuable tools for ensuring the integrity of messages. MACs may be built around a keyed hash function. Our main motivation was to prove that universal hash functions can be employed as underlying primitives of MACs in order to provide provable security in ultra-low-power applications such as the next generation self-powered sensor networks. The idea of using a universal hash function (NH) was explored in the construction of UMAC. This work presents three variations on NH, namely PH, PR and WH. The first hash function we propose, PH, produces a hash of length 2w and is shown to be 2^(-w)-almost universal. The other two hash functions, i.e. PR and WH, reach optimality and are proven to be universal hash functions with half the hash length of w. In addition, these schemes are simple enough to allow for efficient constructions. To the best of our knowledge the proposed hash functions are the first ones specifically designed for low-power hardware implementations. We achieve drastic power savings of up to 59% and speedup of up to 7.4 times over NH. Note that the speed improvement and the power reduction are accomplished simultaneously. Moreover, we show how the technique of multi- hashing and the Toeplitz approach can be combined to reduce the power and energy consumption even further while maintaining the same security level with a very slight increase in the amount of key material. At low frequencies the power and energy reductions are achieved simultaneously while keeping the hashing time constant. We develope formulae for estimation of leakage and dynamic power consumptions as well as energy consumption based on the frequency and the Toeplitz parameter t. We introduce a powerful method for scaling WH according to specific energy and power consumption requirements. This enables us to optimize the hash function implementation for use in ultra-low-power applications such as "Smart Dust" motes, RFIDs, and Piconet nodes. Our simulation results indicate that the implementation of WH-16 consumes only 2.95 ìW 500 kHz. It can therefore be integrated into a self- powered device. By virtue of their security and implementation features mentioned above, we believe that the proposed universal hash functions fill an important gap in cryptographic hardware applications.

The security of a cryptosystem in most cases relies on the key being kept secret. Quantum key distribution (QKD) enables two authenticated parties without other prior information to share a perfectly secure key. However, repeatedly using the same key to encrypt many different messages is not perfectly secure. A trivial method to obtain a secret key is to use QKD to reestablish a new key for each message. In this thesis, we study an efficient method to update the keys. We call this method quantum key evolution (QKE). The QKE provides a new secret key in each round of the protocol. Therefore, a new secret key is established for next round of protocol execution. We study two problems to present secure schemes applying the QKE. First, we present a new quantum message transmission protocol, to transmit long secret message using less quantum bits than the methods of incorporating QKD with one-time pad, as well as some quantum secure direct communication protocols. Second, we present three-party authenticated quantum key distribution protocols which enable two communicating parties to authenticate the other's identity and establish a session key between them via a trusted center. For the security of our protocols, we give formal standard reduction proofs to the security of our protocols. We show that the security of our protocol is equivalent to the security of BB84 protocol which has been proved to be unconditionally secure. Therefore, our protocols are unconditionally secure.

Public key encryption plays a vital role in securing sensitive data in practical applications. The security of many encryption schemes relies on mathematical problems related to the difficulty of factoring large integers. In particular, subgroup problems in composite order groups are a general class of problems widely used in the construction of secure public-key encryption schemes. This thesis studies public-key encryption schemes that are provably secure based on the difficulty of subgroup or other integer factorisation related problems in the standard model. Firstly, a number of new public-key encryption schemes are presented which are secure in the sense of indistinguishability against chosen-ciphertext attack in the standard model. These schemes are obtained by instantiating the two previous paradigms for chosen-ciphertext security by Cramer and Shoup, and Kurosawa and Desmedt, with three previously studied subgroup membership problems. The resulting schemes are very efficient, and are comparable if not superior in terms of efficiency when compared to previously presented instantiations. Secondly, a new approach is presented for constructing RSA-related public key encryption schemes secure in the sense of indistinguishability against chosenciphertext attack without random oracles. This new approach requires a new set of assumptions, called the Oracle RSA-type assumptions. The motivating observation is that RSA-based encryption schemes can be viewed as tag-based encryption schemes, and as a result can be used as a building block in a previous technique for obtaining chosen-ciphertext security. Two example encryption schemes are additionally presented, each of which is of comparable efficiency to other public key schemes of similar security. Finally, the notion of self-escrowed public-key infrastructures is revisited, and a security model is defined for self-escrowed encryption schemes. The security definitions proposed consider adversarial models which reflect an attacker's ability to recover private keys corresponding to public keys of the attacker's choice. General constructions for secure self-escrowed versions of ElGamal, RSA, Cramer-Shoup and Kurosawa-Desmedt encryption schemes are also presented, and efficient instantiations are provided. In particular, one instantiation solves the 'key doubling problem' observed in all previous self-escrowed encryption schemes. Also, for another instantiation a mechanism is described for distributing key recovery amongst a number of authorities.

In March 2000, 1 million litres of raw sewage was released into the water system of Maroochy Shire on Queensland’s sunshine coast. This environmental disaster was caused by a disgruntled ex-contractor using a radio transmitter to illicitly access the electronically controlled pumps in the control system. In 2007 CNN screened video footage of an experimental attack against a electrical generator. The attack caused the generator to shake and smoke, visually showing the damage caused by cyber attack. These attacks highlight the importance of securing the control systems which our critical infrastructures depend on. This thesis addresses securing control systems, focusing on securing the communications for supervisory control and data acquisition (SCADA) systems. We review the architectures of SCADA systems and produce a list of the system constraints that relate to securing these systems. With these constraints in mind, we survey both the existing work in information and SCADA security, observing the need to investigate further the problem of secure communications for SCADA systems. We then present risk modelling techniques, and model the risk in a simple SCADA system, using the ISM, a software tool for modelling information security risk. In modelling the risk, we verify the hypothesis that securing the communications channel is an essential part of an effective security strategy for SCADA systems. After looking at risk modelling, and establishing the value of securing communications, we move on to key management for SCADA systems. Appropriate key management techniques are a crucial part of secure communications, and form an important part of the contributions made in this work. We present a key management protocol that has been designed to run under the constraints specific to SCADA systems. A reductionist security proof is developed for a simplified version of the protocol, showing it is secure in the Bellare Rogaway model.

Les échanges des informations confidentielles ou critiques dans un environnement public, et donc potentiellement hostile, nécessitent l'emploi de techniques cryptographiques (protocoles et primitives). Malheureusement, l'expérience montre qu'une mauvaise conception, ou une expression peu claire des propriétés et hypothèses de sécurité attendues conduisent à des attaques, et qu'il faut parfois des années avant que celles-ci soient découvertes et corrigées. D'où l'adoption croissante de la sécurité prouvable, où on donne une définition rigoureuse des objectifs de sécurité et des démonstrations mathématiques que ceux-ci sont remplis. Par ailleurs, la complexité et la diversité des systèmes cryptographiques croît également. Il est donc largement admis qu'il n'est plus viable d'écrire ou vérifier manuellement des démonstrations cryptographiques (Bellare& Rogaway 2004, Shoup 2004, Halevi 2005) et qu'il faut développer des méthodes de vérification des systèmes cryptographiques assistées par ordinateur. L'objectif de cette thèse est d'effectuer des progrès significatifs dans cette direction. Plus précisement on s'interesse à la preuve formelle de protocoles cryptographiques. Vérifier des protocoles cryptographiques requiert le développement d'un cadre théorique qui doit permettre: - une modélisation précise des protocoles cryptographiques et des propriétés de sécurité qu'on veut prouver dans le modèle calculatoire. - mise en place de stratégies d'automatisation de preuves. - prise en compte des modèles plus réalistes pour l'adversaire (canaux cachés, ressources de calcul). A la fin de la thèse on a obtenu un cadre formel et un ensemble de méthodes logicielles capable d'aider à la vérification des protocoles cryptographiques. / Critical and private information are exchanged on public environment. To protect it from dishonest users, we use cryptographic tools. Unfortunately, bad conception, poorly written security properties and required security hypothesis lead to attacks, and it may take years before one discover the attack and fix the security schemes involved. In this context, provable security provides formal definitions for security objectives and implied mathematical proofs that these objectives are fullfilled. On another hand, complexity and variety of cryptographic systems are increasing, and proofs by hand are too complicated to write and to verify (Bellare& Rogaway 2004, Shoup 2004, Halevi 2005). Thus, we need computer-assisted verification methods for cryptographic systems. The aim of this thesis is to progress in this direction. More precisely we want significant progress over formal proofs on cryptographic protocols. To verify cryptographic protocols we need to develop a theoritical framework providing: - a precise modelisation for cryptographic protocols and security properties we want to prove in the computationnal model, - designing tactics to automate proofs, - taking into account realistic models for adversary (side-channels...). By the end of the thesis we have enhanced a theoretical framework and computing tools helping verifying cryptographic protocols.

The topic of this thesis are mask based one-pass authenticated encryption schemes with associated data. Formal security requirements (AUTH and PRIV), scheme requirements as well as mask system requirements are specified. The- orems regarding fulfillment of security requirements are proven given specified scheme assumptions. The proof utilizes the game-hopping technique. The the- sis contains enumeration of masking systems as well as a selection of schemes with verification that requirements are fulfilled. Last but not least, this thesis presents an attack on the OPP scheme. Recommendation on fixing this scheme is also provided. 1

La cryptographie basée sur les réseaux a connu depuis quelques années un très fort développement notamment du fait qu’il existe des systèmes cryptographiques basés sur les réseaux avec des propriétés de sécurité plus fortes que dans les cas plus classiques de théorie des nombres. Les problèmes difficiles des réseaux, par exemple le problème de trouver des vecteurs courts non nuls, semblent résister aux attaques utilisant des ordinateurs quantiques et les meilleurs algorithmes qui existent pour les résoudre sont exponentiels en fonction du temps. L’objet de cette thèse est la construction de primitives cryptographiques à clé publique pour l’ano- nymat dont la sécurité repose sur des problèmes difficiles des réseaux.Nous nous intéressons aux schémas de signature de cercle. Tout d’abord, nous proposons une nouvelle définition d’anonymat et nous exposons un nouveau schéma de signature de cercle. Ensuite, nous donnons une étude de sécurité rigoureuse suivant deux définitions de résistance la contrefaçon. La première est la résistance à la contrefaçon contre les attaques à sous-cercles choisis et la deuxième est la résistance à la contrefaçon contre les attaques de corruption interne.Nous présentons ensuite un nouveau schéma d’identification de cercle et nous développons une analyse complète de sa sécurité. Enfin, nous montrons que les techniques utilisées pour construire le schéma précédent peuvent être utilisées pour construire un schéma d’identification de cercle à seuil. / Lattice-based cryptography has known during the last decade rapid develop- ments thanks to stronger security properties. In fact, there exist lattice-based cryp- tographic systems whose security is stronger than those based on the conventional number theory approach. The hard problems of lattices, for example the problem of finding short non-zero vectors, seems to resist quantum computers attacks. Mo- reover, the best existing algorithms solving them are exponential in time. The pur- pose of this thesis is the construction of public key cryptographic primitives for anonymity, whose security is based on the latter.In particular, we are interested in ring signature schemes. First, we propose a new formal definition of anonymity and we present a new ring signature scheme. Second, we give a rigorous study of security, following two definitions of unfor- geability. The first of which is unforgeability against chosen-subring attacks and the other one is unforgeability with respect to insider corruption.Afterwards, we present a new ring identification scheme and we develop a full analysis of its security. Finally, we show that the techniques used to build this scheme, can be used to construct a threshold ring identification scheme.

Le chiffrement fonctionnel est une technique émergente en cryptographie dans laquelle une autorité toute puissante est capable de distribuer des clés permettant d’effectuer des calculs sur des données chiffrées de manière contrôlée. La mode dans ce domaine est de construire des schémas qui sont aussi expressifs que possible, c’est-à-dire du chiffrement fonctionnel qui permet l’évaluation de n’importe quel circuit. Ces contributions délaissent souvent l’efficacité ainsi que la sécurité. Elles reposent sur des hypothèses fortes, très peu étudiées, et aucune construction n’est proche d’être pratique. Le but de cette thèse est d’attaquer ce défi sous un autre angle : nous essayons de construire des schémas de chiffrement fonctionnel les plus expressifs que nous le pouvons en se basant sur des hypothèses standards, tout en conservant la simplicité et l’efficacité des constructions. C’est pourquoi nous introduisons la notion de chiffrement fonctionnel pour l’évaluation de produits scalaires, où les messages sont des vecteurs ~x, et l’autorité peut transmettre des clés correspondants à des vecteurs ~y qui permettent l’évaluation du produit scalaire h~x, ~yi. Cette fonctionnalité possède immédiatement des applications directes, et peut aussi être utilisé dans d’autres constructions plus théoriques, leproduit scalaire étant une opération couramment utilisée. Enfin, nous présentons deux structures génériques pour construire des schémas de chiffrement fonctionnels pour le produit scalaire, ainsi que des instanciations concrètes dont la sécurité repose sur des hypothèses standards. Nous comparons aussi les avantages et inconvénients de chacune d’entre elles. / Functional encryption is an emerging framework in which a master authority can distribute keys that allow some computation over encrypted data in a controlled manner. The trend on this topic is to try to build schemes that are as expressive possible, i.e., functional encryption that supports any circuit evaluation. These results are at the cost of efficiency and security. They rely on recent, not very well studied assumptions, and no construction is close to being practical. The goal of this thesis is to attack this challenge from a different angle: we try to build the most expressive functional encryption scheme we can get from standard assumption, while keeping the constructions simple and efficient. To this end, we introduce the notion of functional encryption for inner-product evaluations, where plaintexts are vectors ~x, and the trusted authority delivers keys for vectors ~y that allow the evaluation of the inner-product h~x, ~yi. This functionality already offers some direct applications, and it can also be used for theoretical constructions, as inner-product is a widely used operation. Finally, we present two generic frameworks to construct inner-product functional encryption schemes, as well as some concrete instantiations whose security relies on standard assumptions. We also compare their pros and cons.