Welcome to the resource topic for
**2004/124**

**Title:**

Universally Composable DKG with Linear Number of Exponentiations

**Authors:**
Douglas Wikström

**Abstract:**

Many problems have been solved by protocols using

discrete-logarithm based threshold cryptosystems. Such protocols

require a random joint public key for which the secret key is shared

among the parties.

A multiparty protocol that generates such a key is called a DKG

protocol. Until now no DKG protocol is known to be universally

composable.

We extend Feldman’s original verifiable secret sharing scheme to

construct a DKG protocol, and prove that it is universally

composable. Our result holds in a common random string model under the

Decision Diffie-Hellman assumption. We stress that we do not need any

trapdoor for the common random string.

Our protocol is optimistic. If all parties behave honestly, each party

computes only O(3k) exponentiations, where k is the number of

parties. In the worst case each party computes O(k^2)

exponentiations. This should be contrasted with previous constructions

in which each party computes \Omega(k^2) exponentiations regardless

of if they behave honestly or not. In the optimistic case the number

of bits sent in our protocol is essentially equal to the number of

bits sent in k independent copies of Feldman’s original protocol.

**ePrint:**
https://eprint.iacr.org/2004/124

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .