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

Note: Preliminary version.

Metadata
Available format(s)
PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
threshold cryptography
Contact author(s)
dog @ nada kth se
History
2004-05-26: received
Short URL
https://ia.cr/2004/124
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/124,
      author = {Douglas Wikström},
      title = {Universally Composable {DKG} with Linear Number of Exponentiations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2004/124},
      year = {2004},
      url = {https://eprint.iacr.org/2004/124}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.