International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Masayuki Abe
Serge Fehr
Search ePrint
Search Google
Abstract: 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.
  title={Adaptively Secure Feldman VSS and Applications to Universally-Composable Threshold Cryptography},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / threshold cryptography, universal composability},
  note={This is the full version of a CRYPTO 04 paper. 12619 received 25 May 2004, last revised 20 Jul 2004},
  author={Masayuki Abe and Serge Fehr},