Paper 2004/119

Adaptively Secure Feldman VSS and Applications to Universally-Composable Threshold Cryptography

Masayuki Abe and Serge Fehr


We propose the first distributed discrete-log key generation (DLKG) protocol from scratch which is adaptively-secure in the non-erasure model, and at the same time completely avoids the use of interactive zero-knowledge proofs. As a consequence, the protocol can be proven secure in a universally-composable (UC) like framework which prohibits rewinding. We prove the security in what we call the single-inconsistent-player (SIP) UC model, which guarantees arbitrary composition as long as all protocols are executed by the same players. As applications, we propose a fully UC threshold Schnorr signature scheme, a fully UC threshold DSS signature scheme, and a SIP UC threshold Cramer-Shoup cryptosystem. Our results are based on a new adaptively-secure Feldman VSS scheme. Although adaptive security was already addressed by Feldman in the original paper, the scheme requires secure communication, secure erasure, and either a linear number of rounds or digital signatures to resolve disputes. Our scheme overcomes all of these shortcomings, but on the other hand requires some restriction on the corruption behavior of the adversary, which however disappears in some applications including our new DLKG protocol. We also propose several new adaptively-secure protocols, which may find other applications, like a distributed trapdoor-key generation protocol for Pedersen's commitment scheme, an adaptively-secure Pedersen VSS scheme (as a {\em committed} VSS), or distributed-verifier proofs for proving relations among commitments or even any NP relations in general.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. This is the full version of a CRYPTO 04 paper.
threshold cryptographyuniversal composability
Contact author(s)
sfehr @ ics mq edu au
2004-07-20: revised
2004-05-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Masayuki Abe and Serge Fehr},
      title = {Adaptively Secure Feldman {VSS} and Applications to Universally-Composable Threshold Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2004/119},
      year = {2004},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.