Claim
A signature verification apparatus comprising:
a signature acquisition unit configured to acquire a digital signature
5 including first information generated based on a pair of multi-order multivariate
polynomials F = (fi, ..., fm) defined in a ring K and a signature key s which is an
element of a set K", and a plurality of pieces of second information necessary 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 =
10 (f,(s),..., f„(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
15 keys,
wherein the signature acquisition unit acquires a predetermined number of
the pieces of second information, and
wherein the signature verification unit restores the first information
sequentially using the acquired predetermined number of pieces of second
20 information and erases the second information unnecessary in a restoring process in
an unnecessary stage at which the second information becomes unnecessary.
Claim 2
The signature verification apparatus according to claim 1,
25 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, and
wherein the signature verification unit restores the first information by
repeatedly executing a process of generating an intermediate value output by the
30 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.
Claim 3
5 The signature verification apparatus according to claim 2, wherein the
predetermined number of pieces of second information are erased in a stage at which
generation of the intermediate value is completed.
Claim 4
10 The signature verification apparatus according to claim 2.
wherein the predetermined number is 1, and
wherein a size of information included in the second information and used
in generation of the intermediate value from the unidirectional function is equal to or
greater than a data size of the units of blocks.
15
Claim 5 (amended)
A signature verification method comprising:
a step of acquiring a digital signature including first information generated
based on a pair of multi-order multivariate polynomials F = (fi fm) defined in a
20 ring K and a signature key s which is an element of a set K", and a plurality of pieces
of second information necessary 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 = (fi(s),..., fm(s)); and
a step of verifying legitimacy of the document M by confirming whether or
25 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, in the step of acquiring the digital signature, a predetermined
30 number of the pieces of second information are acquired, and
wherein, in the step of verifying the legitimacy, the first information is restored sequentially using the acquired predetermined number of pieces of second information and the second information unnecessary in a restoring process is erased
in an unnecessary stage at which the second information becomes unnecessary.
5 Claim 6 (amended)
A program causing a computer to realize:
a signature acquisition function of acquiring a digital signature including
first information generated based on a pair of multi-order multivariate polynomials F
= (fi,..., fm) defined in a ring K and a signature key s which is an element of a set K",
10 and a plurality of pieces of second information necessary 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 = (fi(s), ..., fn(s)); and
a signature verification function of verifying legitimacy of the document M
by confirming whether or not the first information is restorable using the plurality of
15 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 function acquires a predetermined number
of the pieces of second information, and
20 wherein the signature verification function 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.
25 Claim 7 (amended)
A computer-readable recording medium having a program recorded thereon,
the program causing a computer to realize:
a signature acquisition function of acquiring a digital signature including
first information generated based on a pair of multi-order multivariate polynomials F
30 = (fi,..., fm) defined in a ring K and a signature key s which is an element of a set K",
and a plurality of pieces of second information necessary 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 = (fi(s),..., fm(s)); and
a signature verification function of verifying 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 function acquires a predetermined number
of the pieces of second information, and
wherein the signature verification function 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.