A signature generation apparatus and a signature verification which can surely prevent occurrence of inappropriate signature verification error are providedA signature generation apparatus (110) includes a signature generation unit (114) which calculates a signature vector (s, t) for a message m using a private key, and generates signature data S indicating polynomials sl and sh that can specify the polynomial s and a polynomial th which is a quotient when the polynomial t is divided by q.