Abstract
Distributed protocols allow a cryptographic scheme to distribute its operation among a group of participants (servers). This new concept of cryptosystems was introduced by Desmedt [56]. We consider two different flavours of distributed protocols. One of them considers a distributed model with n parties where all of these parties are honest. The other allows up to t − 1 parties to be faulty. Such cryptosystems are called threshold cryptosystems. The distribution of cryptographic process is based on secret sharing techniques and is usually applicable to public-key cryptosystems. In this thesis we consider distributed protocols for digital signatures and public key encryption schemes. First we consider two flavours of digital signatures - aggregate signatures and multisignatures - and explore the uniqueness property of these constructions. We show that it gives rise to generic constructions of distributed verifiable unpredictable functions (DVUF), whose outputs can be made pseudorandom in the shared random string model using the techniques from [120]. This gives us the first generic construction of distributed verifiable random functions (DVRF) that do not impose assumptions on trusted generation of secret keys and whose outputs remain pseudorandom even in a presence of up to n − 1 corrupted servers. We provide a DVRF construction which follows immediately from the proof of uniqueness for the multisignature scheme [26]. Then we consider blind signatures as another flavour of digital signatures, and propose the first standard-model construction of (re-randomizable) threshold blind signatures (TBS), where signatures can be obtained in a blind way through interaction with n signers of which t are required to provide their signature shares. The stronger security notions for TBS schemes formalized in our work extend the definitions from [144] to the threshold setting. We further show how our TBS construction can be used to realize a distributed e-voting protocol following the template from [158] that guarantees privacy, anonymity, democracy, conjectured soundness and individual verifiability in the presence of distributed voting authorities. The important applications of distributed digital signatures - threshold e-voting and distributed e-cash - motivated us to consider the nowadays meaningful and crucial cloud data storage techniques. We realize the idea of distributed cloud data storage, which becomes possible as an application of threshold public key encryption with keyword search. First, we model the concept of Threshold Public Key Encryption with Keyword Search (TPEKS) and define its security properties - indistinguishability and consistency under chosen-ciphertext attacks. Our definition of indistinguishability includes protection against keyword guessing attacks, to which all single-server-based PEKS constructions were shown to be vulnerable. We provide a transformation for obtaining secure TPEKS constructions from an anonymous Identity-Based Threshold Decryption (IBTD) scheme, following the conceptual idea behind the transformation from [2] for building PEKS from anonymous IBE. A concrete instantiation of a secure TPEKS scheme can be obtained from our direct anonymous IBTD construction, based on the classical Boneh-Franklin IBE [31], for which we prove the security under the BDH assumption in the random oracle model. Finally we highlight the use of TPEKS schemes for better privacy and availability in distributed cloud storage and provide a comparison with the dual-server PEKS (DS-PEKS)[50] regarding the functionalities of the both schemes, PEKS and DS-PEKS.