Signature generation apparatus and signature verification apparatus

摘要

A signature generation apparatus and a signature verification which can surely prevent occurrence of inappropriate signature verification error are provided A 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.