## Cryptology ePrint Archive: Report 2004/124

**Universally Composable DKG with Linear Number of Exponentiations**

*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.

**Category / Keywords: **public-key cryptography / threshold cryptography

**Date: **received 26 May 2004

**Contact author: **dog at nada kth se

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Note: **Preliminary version.

**Version: **20040526:212327 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]