The present invention provides a signature generation device and a signature verification device capable of countering a transcript attack that seeks a private key by analyzing a plurality of signed documents (pairs of a message and a signature) signed using the NTRUSign signature scheme. The signature generation device calculates a hash value vector H of message data, adds a vector based on a private distribution to the hash value vector H to calculate a converted hash value vector H′, and seeks, as a signature vector S, the closest lattice point to the converted hash value vector H′ in a lattice defined by private key basis vectors. The signature verification device determines whether the distance between the hash value vector H of the message data and the signature vector S is equal to or less than L′ and, if so, recognizes the message data as valid.