The authors present a multiparty signature generation (MSG) scheme of the Digital Signature Algorithm (FIPS 186-1). The scheme is based on a simple idea, however, it is much more convenient in usability in the real world than existing MSGs. The scheme has the following properties: (1) valid signatures are generated with odd n split private keys, (2) broadcast messages between the key holders are hidden from them, so that the n key holders do not need to process signature generation simultaneously, (3) even if up to t (= ) split keys are stolen, the adversary can get no information on the private key, (4) the scheme is as secure as the original signature algorithm against chosen message attack, and (5) the scheme is efficient in the sense that an implementation on smart card has demonstrated practical performance for interactive use with human user.

This paper describes User Attribute with Validity Period extension field of public key certificate and Certificate Verification Service with Time Stamp. The field and service solve the problems of unavailability of the latest revoked certificate information, large size of the revocation information and lack of non-repudiation mechanism of the X. 509 Authentication Framework. The proposed extension field is useful to reduce the revoked certificate information sent from CA of an organization where there are periodical personnel changes. The Certificate Verification Service with Time Stamp is an on-line service providing certificate status and non-repudiation service. The paper shows how the combination of the field and service solves the problems and that the server can serve hundreds of thousands of messaging system users, and the security of the service is also discussed.