Patent ID: 7152158

Claim:
A public key certificate issuing system comprising: a certificate authority for issuing a public key certificate of an entity which uses said public key certificate; and a registration authority for sending a public key certificate issuing request received from an entity under control to said certificate authority; said certificate authority being constituted by a plurality of certificate authorities each executing a different signature algorithm, transferring a public key certificate between said plurality of certificate authorities in response to said public key certificate issuing request received from said registration authority, attaching a digital signature on message data constituting said public key certificate in accordance with said different signature algorithm at each certificate authority, and issuing a multi-signed public key certificate storing a plurality of signatures based on different signature algorithms, wherein said multi-signed public key certificate includes at least a basic area and an extended area, the basic area storing information identifying a first different signature algorithm executed by a first of the plurality of certificate authorities, and the extended area storing information identifying a second different signature algorithm executed by a second of the plurality of certificate authorities, and wherein first and second signatures are generated by respectively applying the first and second different signature algorithms to information in both the basic area and the extended area.