Paper 2004/119

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

Masayuki Abe and Serge Fehr

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.