In 2001, Boneh, Lynn, and Shacham presented a pairing-based signature scheme known as the BLS signature scheme. In 2003, Boneh, Gentry, Lynn, and Shacham presented the first aggregate signature scheme called the BGLS aggregate signature scheme. The BGLS scheme allows for N users with N signatures to combine their signatures into a single signature. The size of the resulting signature is independent of N. The BGLS signature scheme enjoys roughly the same level of security as the BLS scheme. In 2005, Waters presented a pairing-based signature scheme which does not assume the existence of random oracles. In 2007, Lu, Ostrovsky, Sahai, Shacham, and Waters presented the LOSSW aggregate signature scheme which does not assume the existence of random oracles. The BLS, BGLS, Waters, and LOSSW authors each chose to work with a restricted class of pairings. In each scheme, it is clear that the scheme extend to arbitrary pairings. We present the schemes in their full generality, explore variations of the schemes, and discuss optimizations that can be made when using specific pairings. Each of the schemes we discuss is secure assuming that the computational Diffie-Hellman (CDH) assumption holds. We improve on the security reduction for a variation of the BGLS signature scheme which allows for some restrictions of the BGLS signature scheme can be dropped and provides a stronger guarantee of security. We show that the BGLS scheme can be modified to reduce public-key size in presence of a certifying authority, when a certain type of pairing is used. We show that patient-free bit-compression can be applied to each of the scheme with a few modifications.

In 2001, Boneh, Lynn, and Shacham presented a pairing-based signature scheme known as the BLS signature scheme. In 2003, Boneh, Gentry, Lynn, and Shacham presented the first aggregate signature scheme called the BGLS aggregate signature scheme. The BGLS scheme allows for N users with N signatures to combine their signatures into a single signature. The size of the resulting signature is independent of N. The BGLS signature scheme enjoys roughly the same level of security as the BLS scheme. In 2005, Waters presented a pairing-based signature scheme which does not assume the existence of random oracles. In 2007, Lu, Ostrovsky, Sahai, Shacham, and Waters presented the LOSSW aggregate signature scheme which does not assume the existence of random oracles. The BLS, BGLS, Waters, and LOSSW authors each chose to work with a restricted class of pairings. In each scheme, it is clear that the scheme extend to arbitrary pairings. We present the schemes in their full generality, explore variations of the schemes, and discuss optimizations that can be made when using specific pairings. Each of the schemes we discuss is secure assuming that the computational Diffie-Hellman (CDH) assumption holds. We improve on the security reduction for a variation of the BGLS signature scheme which allows for some restrictions of the BGLS signature scheme can be dropped and provides a stronger guarantee of security. We show that the BGLS scheme can be modified to reduce public-key size in presence of a certifying authority, when a certain type of pairing is used. We show that patient-free bit-compression can be applied to each of the scheme with a few modifications.

Providing a security proof is always an important issue in the process of designing a cryptographic scheme or protocol. We often show the security of a cryptosystem via ¡§problem reduction.¡¨ In this thesis, lots of emphasis was put on the review of techniques for proving the security of cryptosystems. These techniques consist of Random Oracle Model and Forking Lemma. We also introduced some well-known cryptographic schemes which can be proved secure using these techniques. Then we offered a security proof of a blind signature scheme based on the one proposed by Fan. In the end, we made a comparison between our proof and the proof of another blind signature scheme provided by David Pointcheval and Jacques Stern. Some arguments and discussions about using the Random Oracle Model to prove the security of a cryptosystem were also included.

This thesis is concerned with the design and analysis of practical provably-secure encryption schemes. We give several results that include new schemes with attractive tradeoffs between efficiency and security and new techniques for analyzing existing schemes. Our results are divided into three chapters, which we summarize below. The Twin Diffie-Hellman Problem. We describe techniques for analyzing encryption schemes based on the hardness of Diffie-Hellman-type problems. We apply our techniques to several specific cases of encryption, including identity-based encryption, to design a collection of encryption schemes that offer improved tradeoffs between efficiency and evidence for security over similar schemes. In addition to offering quantitative advantages over prior work in this area, our technique also simplifies security proofs for these types of encryption schemes. Our main tool in this chapter is the notion of Twin Diffie-Hellman Problems, which provide an intermediate step for organizing security reductions and reveal very simple variants of known schemes with correspondingly simple, but non-obvious, analyses. Non-Malleable Hash Functions. We consider security proofs for encryption that are carried out in the random oracle model, where one declares that a scheme's hash functions are ``off limits' for an attacker in order to make a proof go through. Such proofs leave some doubt as to the security of the scheme in practice, when attackers are free to exploit weaknesses in the hash functions. A particular concern is that a scheme may be insecure in practice no matter what very strong security properties its real hash functions satisfy. We address this doubt for an encryption scheme of Bellare and Rogaway by showing that, using appropriately strong hash functions, this scheme's hash functions can be partially instantiated in a secure way.

Les contremesures de masquage et de dissimulation permettent de rendre plus compliquées les attaques sur les implémentations de chiffrement symétrique. Elles sont aussi toutes deux aisément implémentables (et ce de façon automatisable) dans des flots EDA (Electronic Design Automation) pour ASIC (Application Specific Integrated Circuit) ou FPGA (Field Programmable Gates Array), avec certes différents niveaux d'expertise requis selon la contremesure concernée. Le masquage assure une protection "dynamique" s'appuyant sur un mélange d'aléa en cours de calcul. Nous montrons comment optimiser l'usage de cet aléa grâce à un codage qui permet de compresser les fuites d'information (leakage squeezing). Les limites du masquage s'étudient grâce à des outils de statistique, en analysant des distributions de probabilités. L'outil maître pour évaluer les imperfections des logiques DPL (Dual-rail with Precharge Logic style) est l'analyse stochastique, qui tente de modéliser des fuites "statiques" combinant plusieurs bits. L'inconvénient du masquage est que les attaques sont structurelles à l'utilisation d'aléa : si une attaque réussit sur une partie de la clé (e.g. un octet), alors a priori tous les autres octets sont de façon consistante vulnérables à la même attaque. La situation est différente avec les DPL : en cas de problème d'implémentation, seuls les octets de clés impliqués dans les parties déséquilibrées sont compromis, et non toute la clé. Une façon encore moins coûteuse de protéger les implémentations cryptographiques contre les attaques physiques est la résilience. C'est un usage astucieux de primitives a priori non protégées qui permet d'assurer la protection des secrets. L'avantage des approches résilientes est leur simplicité de mise en oeuvre et (idéalement), leur prouvabilité. Le principal inconvénient est que les contraintes d'usage ne sont souvent pas compatibles avec les standards actuels. Ainsi, nous pensons que davantage de recherche dans ce domaine pourrait globalement être profitable à l'industrie de la sécurité de systèmes embarqués.

Kerberos is a widely-deployed network authentication protocol that is being considered for standardization. Like other standard protocols, Kerberos is no exception to security flaws and weaknesses, as has been demonstrated in several prior works. Provable security guarantees go a long way in restoring users' faith, thus making a protocol an even stronger candidate for standards. In this thesis, our goal was thus to provide provable security support for Kerberos and other practical protocols. Our contributions are three-fold: We first look at the symmetric encryption schemes employed in the current version 5 of Kerberos. Several recent results have analyzed a significant part of Kerberos v.5 using formal-methods-based approaches, which are meaningful only if the underlying encryption schemes satisfy strong cryptographic notions of privacy and authenticity. However, to our knowledge these schemes were never analyzed and proven to satisfy such notions. This thesis aims to bridge this gap. Our provable security analyses confirm that some of the encryption scheme options in Kerberos v.5 already provide privacy and authenticity, and for the remaining we suggest slight modifications for the same. We next turn our attention to the ways in which the keys and other random strings needed in cryptographic schemes employed by practical protocols are generated. Randomness needs to be carefully generated for the provable security guarantees to hold. We propose an efficient pseudorandom generator (PRG) based on hash functions. The security of our PRG relies on exponential collision-resistance and regularity of the underlying hash function. Our PRG can be used to generate various strings, like session keys, sequence numbers, confounders, etc., which are all suggested to be generated randomly in the Kerberos v.5 specification, but no algorithms are mentioned. Each of the above strings are required to satisfy different properties, all of which are trivially satisfied by the pseudorandom strings output by a PRG. Finally, we look at the problem of revocation associated with two relatively new types of encryption schemes: identity-based encryption (IBE) and attribute-based encryption (ABE). While these encryption schemes are relatively less efficient compared to public-key encryption schemes, they have already been used (and are very likely to be used in future, as well) in many practical protocols due to their attractive features. Any setting, public-key, identity-based, or attribute-based, must provide a means to revoke users from the system. However, unlike public-key encryption, there has been little prior work on studying the revocation mechanisms in an IBE or ABE. We propose new primitives and their efficient and provably secure instantiations, focusing on the revocation problem. We would like to note that even though all the results presented in this thesis are motivated mainly by provable security in practice, only the first bullet above has a direct impact on a practical and widely deployed protocol Kerberos. Our PRG is the most efficient construction among theoretical PRGs, but it may still not be efficient enough to be directly usable in practical protocols. And our results and techniques for revocation in IBE and ABE have found much wider applications in information security, such as mobile social networks, cloud-based secure health records, data outsourcing systems, vehicular ad-hoc networks, etc.

Informal analysis of authenticated key establishment (ake) protocols was commonly accepted as the valid argument for their security in the past. Although it can provide some confidence in protocol correctness, experience has shown time and again that ake protocols are likely to contain flaws even after an informal analysis is completed. Therefore, it has become increasingly common to expect a formal analysis, and preferably a mathematical proof, of any published ake protocol in order to obtain increased confidence in its security. In this research we use an appropriate model for analysing ake protocols based on its features and properties. The model allows us to design ake protocols modularly and reuse existing protocol components. We provide a detailed description of its formalisation, operations and usage. This description also includes ways of extracting new protocol components from existing ake protocols. Following the description of the model, we propose a new unauthenticated key establishment protocol for two-party communications. By composing this protocol with authentication protocols, we can construct several new secure ake protocols. These new protocols are compared with existing protocols for their computational efficiency. The comparison shows that our new proven secure protocols are as efficient as the existing protocols with an informal security analysis. We then propose a three-party key establishment protocol which involves a trusted server and two users. We also propose a non-interactive authentication protocol and discuss it and a variant of it. These components are used to construct a secure three-party ake protocol that supports a privacy framework. This framework allows users to remain anonymous while conducting electronic transactions with an independent service provider. A new password-based authentication protocol is proposed to address the problem of authentication using passwords. This protocol carries a proof of security and satisfies a slightly relaxed definition of security. We demonstrate its application by composing it with existing key establishment protocols. To maximise its use, we modified a two-party key establishment protocol to become three-party server based. By using the server for authentication, two users within a common network domain can establish a secure session key. Only a small number of ake protocols are demonstrated in this thesis. There exist many more provably secure ake protocols that can be constructed using the protocol components presented by applying the approach of "mix and match". That is, each new component results in a number of new ake protocols depending on the number of existing components.

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.