A signature generation apparatus and a signature verification apparatus preventing an occurrence of an inappropriate signature verification error. The signature generation apparatus (110) including a signature generation unit (114) calculating signature vector (s, t) for a message m using a private key, and generating signature data S indicating polynomials sl and sh specifying the polynomial s and a polynomial th which is a quotient when the polynomial t is divided by q.