A signature generation apparatus and a signature verification apparatus which can prevent the occurrence of norm zero vector forgery attack. The signature generation apparatus (110) includes a signature generation unit (114) which generates signature data (S) for a message (m) using a private key stored in a private key storage unit (112), and converts the format of the signature data (S) so that the first sub-element of the N sub-elements in the signature data (S) indicates 0 without changing the norm of the signature data (S). The signature verification apparatus (120) includes a signature verification unit (124) which judges whether or not the first sub-element of the N sub-elements included in the signature data (S) indicates 0, and determines the signature data (S) as unauthorized data when judging that it is not 0.