A signature generation apparatus preventing an transcript attack on
signature data. The signature generation apparatus for generating
signature data for message data (i) acquires, according to a
predetermined acquisition method, a private key, which is different from
a private key used in a previous digital signature operation, from among
a plurality of private keys generated using a key generation method of a
signature scheme in which the plurality of private keys correspond to a
single public key, and (ii) performs, using the acquired private key, a
digital signature operation on the message data according to a signature
method of the signature scheme to generate the signature data.