In a (k,n) threshold digital signature scheme, k out of n signers must cooperate to issue a signature. In this paper, we show an efncient (k,n) threshold EIGamal type digital signature scheme with no trusted center. We first present a variant of EIGamal type digital signature scheme which requires only a linear combination of two shared secrets when applied to the (k,n)-threshold scenario. More precisely, it is a variant of Digital Signature Standard (DSS) which was recommended by the U.S. National Institute ofStandard and Technology (NIST). We consider that it is meaningful to develop an efficient (k,n)-threshold digital signature scheme for DSS. The proposed (k,n)-threshold digital signature scheme is proved to be as secure as the proposed variant of DSS against chosen message attack.

Mobile communication networks need public key cryptosystems that offer both low computation cost and user authentication. Tatebayashi et al. showed a key distribution protocol for such networks at Crypto'89 based on low exponent RSA. This paper shows that their protocol is not secure. We also present two types of secure and efficient key distribution protocols.