<p>Public key encryption was first proposed by Diffie and Hellman [16], and widely popularised with the RSA cryptosystem [37]. Over the years, the security goals of public key encryption have been studied [17, 22], as have adversary models [30, 36], and many public key cryptosystems have been proposed and analysed.</p><p>It turns out that the security of many of those cryptosystems [16, 18, 22, 29, 34, 35] are based on a common class of mathematical problems, called subgroup membership problems. Cramer and Shoup [10] designed a chosen-ciphertextsecure cryptosystem based on a general subgroup membership problem (generalising their previous work [9]), and provided two new instances. Yamamura and Saito [41] defined a general subgroup membership problem, catalogued several known subgroup membership problems, and designed a private information retrieval system based on a subgroup membership problem. Nieto, Boyd and Dawson [31] designed a cryptosystem based on essentially a symmetric subgroup membership problem (see Section 4.4 and Section 6.1).</p><p>Chapter 2 and 3 contain certain preliminary discussions necessary for the later work. In Chapter 4, we discuss subgroup membership problems, both abstractly and concrete families. For all of the concrete examples, there is a related problem called the splitting problem. We discuss various elementary reductions, both abstract and for concrete families. In cryptographic applications, a third related problem, called the subgroup discrete logarithm problem, is also interesting, and we discuss this in some detail. We also discuss a variant of the subgroup membership problem where there are two subgroups that are simultaneously hard to distinguish. We prove a useful reduction (Theorem 4.11) for this case. The technique used in the proof is reused throughout the thesis.</p><p>In Chapter 5, we discuss two homomorphic cryptosystems, based on trapdoor splitting problems. This gives us a uniform description of a number of homomorphic cryptosystems, and allows us to apply the theory and results of Chapter 4 to the security of those cryptosystems.</p><p>Using the technique of Theorem 4.11, we develop a homomorphic cryptosystem that is not based on a trapdoor problem. This gives us a fairly efficient cryptosystem, with potentially useful properties.</p><p>We also discuss the security of a homomorphic cryptosystem under a nonstandard assumption. While these results are very weak, they are stronger than results obtained in the generic model.</p><p>In Chapter 6, we develop two key encapsulation methods. The first can be proven secure against passive attacks, using the same technique as in the proof of Theorem 4.11. The second method can be proven secure against active attacks in the random oracle model, but to do this, we need a certain non-standard assumption.</p><p>Finally, in Chapter 7 we discuss a small extension to the framework developed by Cramer and Shoup [10], again by essentially reusing the technique used to prove Theorem 4.11. This gives us a cryptosystem that is secure against chosen ciphertext attacks, without recourse to the random oracle model or nonstandard assumptions. The cryptosystem is quite practical, and performs quite well compared to other variants of the Cramer-Shoup cryptosystem.</p>

Public key encryption was first proposed by Diffie and Hellman [16], and widely popularised with the RSA cryptosystem [37]. Over the years, the security goals of public key encryption have been studied [17, 22], as have adversary models [30, 36], and many public key cryptosystems have been proposed and analysed. It turns out that the security of many of those cryptosystems [16, 18, 22, 29, 34, 35] are based on a common class of mathematical problems, called subgroup membership problems. Cramer and Shoup [10] designed a chosen-ciphertextsecure cryptosystem based on a general subgroup membership problem (generalising their previous work [9]), and provided two new instances. Yamamura and Saito [41] defined a general subgroup membership problem, catalogued several known subgroup membership problems, and designed a private information retrieval system based on a subgroup membership problem. Nieto, Boyd and Dawson [31] designed a cryptosystem based on essentially a symmetric subgroup membership problem (see Section 4.4 and Section 6.1). Chapter 2 and 3 contain certain preliminary discussions necessary for the later work. In Chapter 4, we discuss subgroup membership problems, both abstractly and concrete families. For all of the concrete examples, there is a related problem called the splitting problem. We discuss various elementary reductions, both abstract and for concrete families. In cryptographic applications, a third related problem, called the subgroup discrete logarithm problem, is also interesting, and we discuss this in some detail. We also discuss a variant of the subgroup membership problem where there are two subgroups that are simultaneously hard to distinguish. We prove a useful reduction (Theorem 4.11) for this case. The technique used in the proof is reused throughout the thesis. In Chapter 5, we discuss two homomorphic cryptosystems, based on trapdoor splitting problems. This gives us a uniform description of a number of homomorphic cryptosystems, and allows us to apply the theory and results of Chapter 4 to the security of those cryptosystems. Using the technique of Theorem 4.11, we develop a homomorphic cryptosystem that is not based on a trapdoor problem. This gives us a fairly efficient cryptosystem, with potentially useful properties. We also discuss the security of a homomorphic cryptosystem under a nonstandard assumption. While these results are very weak, they are stronger than results obtained in the generic model. In Chapter 6, we develop two key encapsulation methods. The first can be proven secure against passive attacks, using the same technique as in the proof of Theorem 4.11. The second method can be proven secure against active attacks in the random oracle model, but to do this, we need a certain non-standard assumption. Finally, in Chapter 7 we discuss a small extension to the framework developed by Cramer and Shoup [10], again by essentially reusing the technique used to prove Theorem 4.11. This gives us a cryptosystem that is secure against chosen ciphertext attacks, without recourse to the random oracle model or nonstandard assumptions. The cryptosystem is quite practical, and performs quite well compared to other variants of the Cramer-Shoup cryptosystem.

In the first part of the thesis we show black-box separations in public and private-key cryptography. Our main result answers in the negative the question of whether we can base Identity Based Encryption (IBE) on Trapdoor Permutations. Furthermore, we make progress towards the black-box separation of IBE from the Decisional Diffie-Hellman assumption. We also show the necessity of adaptivity when querying one-way permutations to construct pseudorandom generators a' la Goldreich-Levin; an issue related to streaming models for cryptography. In the second part we introduce streaming techniques in understanding randomness in efficient computation, proving lower bounds for efficiently computable problems, and in computing cryptographic primitives. We observe [Coo71] that logarithmic space-bounded Turing Machines, equipped with an unbounded stack, henceforth called Stack Machines, together with an external random tape of polynomial length characterize RP,BPP an so on. By parametrizing on the number of passes over the random tape we provide a technical perspective bringing together Streaming, Derandomization, and older works in Stack Machines. Our technical developments relate this new model with previous works in derandomization. For example, we show that to derandomize parts of BPP it is in some sense sufficient to derandomize BPNC (a class believed to be much lower than P \subseteq BPP). We also obtain a number of results for variants of the main model, regarding e.g. the fooling power of Nisan's pseudorandom generator (PRG) [N92] for the derandomization of BPNC^1, and the relation of parametrized access to NP-witnesses with width-parametrizations of SAT. A substantial contribution regards a streaming approach to lower bounds for problems in the NC-hierarchy (and above). We apply Communication Complexity to show a streaming lower bound for a model with an unbounded (free-to-access) pushdown storage. In particular, we obtain a $n^{\Omega(1)}$ lower bound simultaneously in the space and in the number of passes over the input, for a variant of inner product. This is the first lower bound for machines that correspond to poly-size circuits, can do Parity, Barrington's language, and decide problems in P-NC assuming EXP \neq PSPACE. Finally, we initiate the study of log-space streaming computation of cryptographic primitives. We observe that the work on Cryptography in NC^0 [AIK08] yields a non-black-box construction of a one-way function computable in an O(log n)-space bounded streaming model.Also, we show that relying on this work is in some sense necessary.

We study several basic problems in cryptography: Leakage resilient cryptography: cryptographic schemes are often broken through side-channel attacks on the devices that run them. Such attacks typically involve an adversary that is within short distance from the device, and is able to measure various physical characteristics of the device such as power consumption, timing, heat, and sound emanation. We show how to immunize any cryptographic functionality against arbitrary side-channel attacks using the recently achieved fully homomorphic encryption, and a single piece of secure hardware that samples from a public distribution. Our secure hardware never touches any secret information (such as a private key) and is testable in the sense that its inputs are not influenced by user or adversarial inputs. Credential-free key exchange and sessions: One of the most basic tasks in cryptography is to allow two parties that are connected by a completely insecure channel to communicate securely. Typically, the first step towards achieving this is an exchange of a session key. Such an exchange normally requires an infrastructure, where, for example, public keys of users are stored, and can be securely retrieved. However, often such an infrastructure does not exist, or is too costly to maintain. In such a setting an adversary can always be the Man-In-The-Middle and intercept all communications. However, we argue that a meaningful level of security can still be achieved. We present a definition of secure key exchange in a setting without any infrastructure, and describe a protocol that achieves that type of security. The idea is that an adversary should either know nothing about the session key produced by the protocol, or be forced to participate in two independent instances of the protocol Black-box separations: A complementary aspect of cryptographic research is the study of the limits of cryptographic assumptions. Basing constructions on weaker assumptions gives us more confidence in their security. We therefore wish to find, for each standard cryptographic assumption, what tasks cannot be solved based solely on that assumption. In this thesis we study the limits of a very basic public key primitive: trapdoor permutations (TDPs). We show that TDPs cannot be used to construct Identity Based Encryption or a stronger type of TDPs called correlation secure TDPs. Correlation secure TDPs have been used to build chosen-ciphertext secure public key encryption scheme -- a primitive with a wide range of theoretical and practical applications.

In the first part of the thesis we show black-box separations in public and private-key cryptography. Our main result answers in the negative the question of whether we can base Identity Based Encryption (IBE) on Trapdoor Permutations. Furthermore, we make progress towards the black-box separation of IBE from the Decisional Diffie-Hellman assumption. We also show the necessity of adaptivity when querying one-way permutations to construct pseudorandom generators a' la Goldreich-Levin; an issue related to streaming models for cryptography. In the second part we introduce streaming techniques in understanding randomness in efficient computation, proving lower bounds for efficiently computable problems, and in computing cryptographic primitives. We observe [Coo71] that logarithmic space-bounded Turing Machines, equipped with an unbounded stack, henceforth called Stack Machines, together with an external random tape of polynomial length characterize RP,BPP an so on. By parametrizing on the number of passes over the random tape we provide a technical perspective bringing together Streaming, Derandomization, and older works in Stack Machines. Our technical developments relate this new model with previous works in derandomization. For example, we show that to derandomize parts of BPP it is in some sense sufficient to derandomize BPNC (a class believed to be much lower than P \subseteq BPP). We also obtain a number of results for variants of the main model, regarding e.g. the fooling power of Nisan's pseudorandom generator (PRG) [N92] for the derandomization of BPNC^1, and the relation of parametrized access to NP-witnesses with width-parametrizations of SAT. A substantial contribution regards a streaming approach to lower bounds for problems in the NC-hierarchy (and above). We apply Communication Complexity to show a streaming lower bound for a model with an unbounded (free-to-access) pushdown storage. In particular, we obtain a $n^{\Omega(1)}$ lower bound simultaneously in the space and in the number of passes over the input, for a variant of inner product. This is the first lower bound for machines that correspond to poly-size circuits, can do Parity, Barrington's language, and decide problems in P-NC assuming EXP \neq PSPACE. Finally, we initiate the study of log-space streaming computation of cryptographic primitives. We observe that the work on Cryptography in NC^0 [AIK08] yields a non-black-box construction of a one-way function computable in an O(log n)-space bounded streaming model.Also, we show that relying on this work is in some sense necessary.

We study several basic problems in cryptography: Leakage resilient cryptography: cryptographic schemes are often broken through side-channel attacks on the devices that run them. Such attacks typically involve an adversary that is within short distance from the device, and is able to measure various physical characteristics of the device such as power consumption, timing, heat, and sound emanation. We show how to immunize any cryptographic functionality against arbitrary side-channel attacks using the recently achieved fully homomorphic encryption, and a single piece of secure hardware that samples from a public distribution. Our secure hardware never touches any secret information (such as a private key) and is testable in the sense that its inputs are not influenced by user or adversarial inputs. Credential-free key exchange and sessions: One of the most basic tasks in cryptography is to allow two parties that are connected by a completely insecure channel to communicate securely. Typically, the first step towards achieving this is an exchange of a session key. Such an exchange normally requires an infrastructure, where, for example, public keys of users are stored, and can be securely retrieved. However, often such an infrastructure does not exist, or is too costly to maintain. In such a setting an adversary can always be the Man-In-The-Middle and intercept all communications. However, we argue that a meaningful level of security can still be achieved. We present a definition of secure key exchange in a setting without any infrastructure, and describe a protocol that achieves that type of security. The idea is that an adversary should either know nothing about the session key produced by the protocol, or be forced to participate in two independent instances of the protocol Black-box separations: A complementary aspect of cryptographic research is the study of the limits of cryptographic assumptions. Basing constructions on weaker assumptions gives us more confidence in their security. We therefore wish to find, for each standard cryptographic assumption, what tasks cannot be solved based solely on that assumption. In this thesis we study the limits of a very basic public key primitive: trapdoor permutations (TDPs). We show that TDPs cannot be used to construct Identity Based Encryption or a stronger type of TDPs called correlation secure TDPs. Correlation secure TDPs have been used to build chosen-ciphertext secure public key encryption scheme -- a primitive with a wide range of theoretical and practical applications.

This thesis includes my research on efficient cryptographic protocols, sensor network key management, and radio frequency identification (RFID) authentication protocols. Key exchange, identification, and public key encryption are among the fundamental protocols studied in cryptography. There are two important requirements for these protocols: efficiency and security. Efficiency is evaluated using the computational overhead to execute a protocol. In modern cryptography, one way to ensure the security of a protocol is by means of provable security. Provable security consists of a security model that specifies the capabilities and the goals of an adversary against the protocol, one or more cryptographic assumptions, and a reduction showing that breaking the protocol within the security model leads to breaking the assumptions. Often, efficiency and provable security are not easy to achieve simultaneously. The design of efficient protocols in a strict security model with a tight reduction is challenging. Security requirements raised by emerging applications bring up new research challenges in cryptography. One such application is pervasive communication and computation systems, including sensor networks and radio frequency identification (RFID) systems. Specifically, sensor network key management and RFID authentication protocols have drawn much attention in recent years. In the cryptographic protocol part, we study identification protocols, key exchange protocols, and ElGamal encryption and its variant. A formal security model for challenge-response identification protocols is proposed, and a simple identification protocol is proposed and proved secure in this model. Two authenticated key exchange (AKE) protocols are proposed and proved secure in the extended Canetti-Krawczyk (eCK) model. The proposed AKE protocols achieve tight security reduction and efficient computation. We also study the security of ElGamal encryption and its variant, Damgard’s ElGamal encryption (DEG). Key management is the cornerstone of the security of sensor networks. A commonly recommended key establishment mechanism is based on key predistribution schemes (KPS). Several KPSs have been proposed in the literature. A KPS installs pre-assigned keys to sensor nodes so that two nodes can communicate securely if they share a key. Multi-path key establishment (MPKE) is one component of KPS which enables two nodes without a shared key to establish a key via multiple node-disjoint paths in the network. In this thesis, methods to compute the k-connectivity property of several representative key predistribution schemes are developed. A security model for MPKE and efficient and secure MPKE schemes are proposed. Scalable, privacy-preserving, and efficient authentication protocols are essential for the success of RFID systems. Two such protocols are proposed in this thesis. One protocol uses finite field polynomial operations to solve the scalability challenge. Its security is based on the hardness of the polynomial reconstruction problem. The other protocol improves a randomized Rabin encryption based RFID authentication protocol. It reduces the hardware cost of an RFID tag by using a residue number system in the computation, and it provides provable security by using secure padding schemes.

This thesis includes my research on efficient cryptographic protocols, sensor network key management, and radio frequency identification (RFID) authentication protocols. Key exchange, identification, and public key encryption are among the fundamental protocols studied in cryptography. There are two important requirements for these protocols: efficiency and security. Efficiency is evaluated using the computational overhead to execute a protocol. In modern cryptography, one way to ensure the security of a protocol is by means of provable security. Provable security consists of a security model that specifies the capabilities and the goals of an adversary against the protocol, one or more cryptographic assumptions, and a reduction showing that breaking the protocol within the security model leads to breaking the assumptions. Often, efficiency and provable security are not easy to achieve simultaneously. The design of efficient protocols in a strict security model with a tight reduction is challenging. Security requirements raised by emerging applications bring up new research challenges in cryptography. One such application is pervasive communication and computation systems, including sensor networks and radio frequency identification (RFID) systems. Specifically, sensor network key management and RFID authentication protocols have drawn much attention in recent years. In the cryptographic protocol part, we study identification protocols, key exchange protocols, and ElGamal encryption and its variant. A formal security model for challenge-response identification protocols is proposed, and a simple identification protocol is proposed and proved secure in this model. Two authenticated key exchange (AKE) protocols are proposed and proved secure in the extended Canetti-Krawczyk (eCK) model. The proposed AKE protocols achieve tight security reduction and efficient computation. We also study the security of ElGamal encryption and its variant, Damgard’s ElGamal encryption (DEG). Key management is the cornerstone of the security of sensor networks. A commonly recommended key establishment mechanism is based on key predistribution schemes (KPS). Several KPSs have been proposed in the literature. A KPS installs pre-assigned keys to sensor nodes so that two nodes can communicate securely if they share a key. Multi-path key establishment (MPKE) is one component of KPS which enables two nodes without a shared key to establish a key via multiple node-disjoint paths in the network. In this thesis, methods to compute the k-connectivity property of several representative key predistribution schemes are developed. A security model for MPKE and efficient and secure MPKE schemes are proposed. Scalable, privacy-preserving, and efficient authentication protocols are essential for the success of RFID systems. Two such protocols are proposed in this thesis. One protocol uses finite field polynomial operations to solve the scalability challenge. Its security is based on the hardness of the polynomial reconstruction problem. The other protocol improves a randomized Rabin encryption based RFID authentication protocol. It reduces the hardware cost of an RFID tag by using a residue number system in the computation, and it provides provable security by using secure padding schemes.

In the second chapter, the notion of a social secret sharing (SSS) scheme is introduced in which shares are allocated based on a player's reputation and the way she interacts with other parties. In other words, this scheme renews shares at each cycle without changing the secret, and it allows the trusted parties to gain more authority. Our motivation is that, in real-world applications, components of a secure scheme have different levels of importance (i.e., the number of shares a player has) and reputation (i.e., cooperation with other parties). Therefore, a good construction should balance these two factors accordingly. In the third chapter, a novel socio-rational secret sharing (SRS) scheme is introduced in which rational foresighted players have long-term interactions in a social context, i.e., players run secret sharing while founding and sustaining a public trust network. To motivate this, consider a repeated secret sharing game such as sealed-bid auctions. If we assume each party has a reputation value, we can then penalize (or reward) the players who are selfish (or unselfish) from game to game. This social reinforcement stimulates the players to be cooperative in the secret recovery phase. Unlike the existing protocols in the literature, the proposed solution is stable and it only has a single reconstruction round. In the fourth chapter, a comprehensive analysis of the existing dynamic secret sharing (DSS) schemes is first provided. In a threshold scheme, the sensitivity of the secret and the number of players may fluctuate due to various reasons. Moreover, a common problem with almost all secret sharing schemes is that they are ``one-time'', meaning that the secret and shares are known to everyone after secret recovery. We therefore provide new techniques where the threshold and/or the secret can be changed multiple times to arbitrary values after the initialization. In addition, we introduce a new application of dynamic threshold schemes, named sequential secret sharing (SQS), in which several secrets with increasing thresholds are shared among the players who have different levels of authority. In the fifth chapter, a cryptographic primitive, named multicomponent commitment scheme (MCS) is proposed where we have multiple committers and verifiers. This new scheme is used to construct different sealed-bid auction protocols (SAP) where the auction outcomes are defined without revealing the losing bids. The main reason for constructing secure auctions is the fact that the values of the losing bids can be exploited in future auctions and negotiations if they are not kept private. In our auctioneer-free protocols, bidders first commit to their bids before the auction starts. They then apply a decreasing price mechanism to define the winner and selling price in an unconditionally secure setting.

Pairing-based cryptography has been employed to obtain several advantageous cryptographic protocols. In particular, there exist several identity-based variants of common cryptographic schemes. The computation of a single pairing is a comparatively expensive operation, since it often requires many operations in the underlying elliptic curve. In this thesis, we explore the efficient computation of pairings. Computation of the Tate pairing is done in two steps. First, a Miller function is computed, followed by the final exponentiation. We discuss the state-of-the-art optimizations for Miller function computation under various conditions. We are able to shave off a fixed number of operations in the final exponentiation. We consider methods to effectively parallelize the computation of pairings in a multi-core setting and discover that the Weil pairing may provide some advantage under certain conditions. This work is extended to the 192-bit security level and some unlikely candidate curves for such a setting are discovered. Electronic Toll Pricing (ETP) aims to improve road tolling by collecting toll fares electronically and without the need to slow down vehicles. In most ETP schemes, drivers are charged periodically based on the locations, times, distances or durations travelled. Many ETP schemes are currently deployed and although these systems are efficient, they require a great deal of knowledge regarding driving habits in order to operate correctly. We present an ETP scheme where pairing-based BLS signatures play an important role. Finally, we discuss the security of pairings in the presence of an efficient algorithm to invert the pairing. We generalize previous results to the setting of asymmetric pairings as well as give a simplified proof in the symmetric setting.