A signature verification apparatus comprising: a signature acquisition unit configured to acquire a digital signature including first information generated based on a pair of multi-order multivariate polynomials F = (f 1,..., f m) defined in a ring K and a signature key s which is an element of a set K n, and a plurality of pieces of second information for verifying that the first information is generated using the signature key s based on the document M, the pair of multi-order multivariate polynomials F, and vectors y = (f 1 (s), f m (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, wherein the pair of multivariate polynomials F and the vectors y are public keys, wherein the signature acquisition unit acquires a predetermined number of the pieces of second information, wherein the first information is generated using a unidirectional function of processing information to be input by grouping the information to be input in units of blocks, wherein the signature verification unit restores the first information by repeatedly executing a process of generating an intermediate value output by the unidirectional function in a process in the units of blocks based on the acquired predetermined number of pieces of second information and a process of generating a subsequent intermediate value based on the generated intermediate value and the predetermined number of pieces of the subsequently acquired second information, and wherein the signature verification unit restores the first information sequentially using the acquired predetermined number of pieces of second information and erases the second information unnecessary in a restoring process in an unnecessary stage at which the second information becomes unnecessary. a signature acquisition unit configured to acquire a digital signature including first information generated based on a pair of multi-order multivariate polynomials F = (f 1,..., f m) defined in a ring K and a signature key s which is an element of a set K n, and a plurality of pieces of second information for verifying that the first information is generated using the signature key s based on the document M, the pair of multi-order multivariate polynomials F, and vectors y = (f 1 (s), f m (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, wherein the pair of multivariate polynomials F and the vectors y are public keys, wherein the signature acquisition unit acquires a predetermined number of the pieces of second information, wherein the first information is generated using a unidirectional function of processing information to be input by grouping the information to be input in units of blocks, wherein the signature verification unit restores the first information by repeatedly executing a process of generating an intermediate value output by the unidirectional function in a process in the units of blocks based on the acquired predetermined number of pieces of second information and a process of generating a subsequent intermediate value based on the generated intermediate value and the predetermined number of pieces of the subsequently acquired second information, and wherein the signature verification unit restores the first information sequentially using the acquired predetermined number of pieces of second information and erases the second information unnecessary in a restoring process in an unnecessary stage at which the second information becomes unnecessary.