A signature generation and verification system including a signature generation apparatus and a signature verification apparatus is provided. Based on signer certification information possessed by a signer, the signature generation apparatus generates a digital signature and verification data corresponding to a given electronic document and outputs the set of the digital signature and the verification data as signature data. Upon receipt of the electronic document and the signature data, the signature verification apparatus verifies the digital signature using the verification data to verify the integrity of the electronic document. As needed, the signature verification apparatus performs user identification ex-post facto by authenticating that the signer certification information from which the verification data was generated belongs to a legitimate user without knowledge of the signer certification information.