Paper 2009/432

Practical Distributed Key Generation Scheme

Chen Huiyan, Li Zichen, and Fang Yong

Abstract

Generating a distributed key, where a constant fraction of the players can reconstruct the key, is an essential component of thresh- old cryptography. Previous solutions are based on univariate polynomi als. We present a new distributed key generation (DKG) protocol. The key idea of our scheme is to use bivariate symmetric polynomial. Compared with other solutions, our construction is efficient in computation and simple and flexible in applications. In addition, our construction admits a rigorous proof of security. We also study the new-member-joining problem which often occurs in some applications: Players P1, ..., Pn, who make up a group G, have jointly generated a pair of private and public keys based on some DKG, when a new player hope to join in G, how does he get a share of private key? We present a new-member-joining protocol which is based on our DKG scheme and which completely solve this problem. we also give a proof of the security of this new-member-joining protocol in terms of correctness and secrecy.