Numerous cryptographic applications require a trusted authority to hold a secret. With a plethora of malicious attacks over the Internet, however, it is difficult to establish and maintain such an authority in online systems. Secret-sharing schemes attempt to solve this problem by distributing the required trust to hold and use the secret over multiple servers; however, they still require a trusted {\em dealer} to choose and share the secret, and have problems related to single points of failure and key escrow. A distributed key generation (DKG) scheme overcomes these hurdles by removing the requirement of a dealer in secret sharing. A (threshold) DKG scheme achieves this using a complete distribution of the trust among a number of servers such that any subset of servers of size greater than a given threshold can reveal or use the shared secret, while any smaller subset cannot. In this thesis, we make contributions to DKG in the computational security setting and describe three applications of it. We first define a constant-size commitment scheme for univariate polynomials over finite fields and use it to reduce the size of broadcasts required for DKG protocols in the synchronous communication model by a linear factor. Further, we observe that the existing (synchronous) DKG protocols do not provide a liveness guarantee over the Internet and design the first DKG protocol for use over the Internet. Observing the necessity of long-term stability, we then present proactive security and group modification protocols for our DKG system. We also demonstrate the practicality of our DKG protocol over the Internet by testing our implementation over PlanetLab. For the applications, we use our DKG protocol to define IND-ID-CCA secure distributed private-key generators (PKGs) for three important identity-based encryption (IBE) schemes: Boneh and Franklin's BF-IBE, Sakai and Kasahara's SK-IBE, and Boneh and Boyen's BB1-IBE. These IBE schemes cover all three important IBE frameworks: full-domain-hash IBEs, exponent-inversion IBEs and commutative-blinding IBEs respectively, and our distributed PKG constructions can easily be modified for other IBE schemes in these frameworks. As the second application, we use our distributed PKG for BF-IBE to define an onion routing circuit construction mechanism in the identity-based setting, which solves the scalability problem in single-pass onion routing circuit construction without hampering forward secrecy. As the final application, we use our DKG implementation to design a threshold signature architecture for quorum-based distributed hash tables and use it to define two robust communication protocols in these peer-to-peer systems.

Numerous cryptographic applications require a trusted authority to hold a secret. With a plethora of malicious attacks over the Internet, however, it is difficult to establish and maintain such an authority in online systems. Secret-sharing schemes attempt to solve this problem by distributing the required trust to hold and use the secret over multiple servers; however, they still require a trusted {\em dealer} to choose and share the secret, and have problems related to single points of failure and key escrow. A distributed key generation (DKG) scheme overcomes these hurdles by removing the requirement of a dealer in secret sharing. A (threshold) DKG scheme achieves this using a complete distribution of the trust among a number of servers such that any subset of servers of size greater than a given threshold can reveal or use the shared secret, while any smaller subset cannot. In this thesis, we make contributions to DKG in the computational security setting and describe three applications of it. We first define a constant-size commitment scheme for univariate polynomials over finite fields and use it to reduce the size of broadcasts required for DKG protocols in the synchronous communication model by a linear factor. Further, we observe that the existing (synchronous) DKG protocols do not provide a liveness guarantee over the Internet and design the first DKG protocol for use over the Internet. Observing the necessity of long-term stability, we then present proactive security and group modification protocols for our DKG system. We also demonstrate the practicality of our DKG protocol over the Internet by testing our implementation over PlanetLab. For the applications, we use our DKG protocol to define IND-ID-CCA secure distributed private-key generators (PKGs) for three important identity-based encryption (IBE) schemes: Boneh and Franklin's BF-IBE, Sakai and Kasahara's SK-IBE, and Boneh and Boyen's BB1-IBE. These IBE schemes cover all three important IBE frameworks: full-domain-hash IBEs, exponent-inversion IBEs and commutative-blinding IBEs respectively, and our distributed PKG constructions can easily be modified for other IBE schemes in these frameworks. As the second application, we use our distributed PKG for BF-IBE to define an onion routing circuit construction mechanism in the identity-based setting, which solves the scalability problem in single-pass onion routing circuit construction without hampering forward secrecy. As the final application, we use our DKG implementation to design a threshold signature architecture for quorum-based distributed hash tables and use it to define two robust communication protocols in these peer-to-peer systems.

Secure communication is critical to many applications. To this end, various security goals can be achieved using elliptic/hyperelliptic curve and pairing based cryptography. Polynomial multiplication is used in the underlying operations of these protocols. Therefore, as part of this thesis different recursive algorithms are studied; these algorithms include Karatsuba, Toom, and Bernstein. In this thesis, we investigate algorithms and implementation techniques to improve the performance of the cryptographic protocols. Common factors present in explicit formulae in elliptic curves operations are utilized such that two multiplications are replaced by a single multiplication in a higher field. Moreover, we utilize the idea based on common factor used in elliptic curves and generate new explicit formulae for hyperelliptic curves and pairing. In the case of hyperelliptic curves, the common factor method is applied to the fastest known even characteristic hyperelliptic curve operations, i.e. divisor addition and divisor doubling. Similarly, in pairing we observe the presence of common factors inside the Miller loop of Eta pairing and the theoretical results show significant improvement when applying the idea based on common factor method. This has a great advantage for applications that require higher speed.