A signature verification apparatus including a signature acquisition unit configured to acquire a digital signature including first information generated based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) defined in a ring K, a signature key s which is an element of a set Kn, and a document M and a plurality of pieces of second information for verifying that the first information is generated using the signature key s based on the data M, the pair of multi-order multivariate polynomials F, and vectors y=(f1(s), . . . , fm(s)), and a signature verification unit configured to verify legitimacy of the document M by confirming whether or not the first information is restorable using the plurality of pieces of second information included in the digital signature. The pair of multivariate polynomials F and the vectors y are public keys.