Patent ID: 7664260

Claim:
A signature generation apparatus for generating signature data for message data, the signature generation apparatus comprising: a private key acquisition unit operable to acquire, according to a predetermined acquisition method, a private key from among a plurality of private keys generated using a key generation method of a signature scheme in which the plurality of private keys correspond to a single public key, the acquired private key being different from a private key used in a previous digital signature operation; and a signature generation unit operable to perform, using the acquired private key, a digital signature operation on the message data according to a signature method of the signature scheme to generate the signature data, wherein the private key acquisition unit stores therein the plurality of private keys, wherein the signature scheme is a lattice-based signature scheme, wherein the plurality of private keys stored in the private key acquisition unit are generated using the key generation method of the lattice-based signature scheme, wherein the signature scheme is an NTRU signature scheme, including: a public key generation step of (i) generating, for a ring R which is a set of N-dimensional arrays where addition, subtraction, multiplication, and a norm indicating a size of an element are defined, and for an ideal of the ring R, elements f and g of the ring R and an element Fq that is an inverse of f(mod q), and (ii) generating, as the public key, an element h that is congruent to a product of the element g and the element Fq mod q; a private key generation step of (i) generating a plurality of solutions (F, G)=(F — 1, G — 1), (F — 2, G — 2), . . . , and (F_u, G_u), each of which is a pair of elements of the ring R, satisfies f×G−g×F=q, and has a norm that is smaller than a predetermined value, u being a positive integer that is larger than 1, and (ii) generating, as the plurality of private keys, a plurality of four-element sets (f, g, F — 1, G — 1), (f, g, F — 2, G — 2), and (f, g, F_u, G_u), each of which is a different one of the plurality of private keys; and a signature generation step of using one of the generated private keys to generate the signature data, wherein the plurality of private keys stored in the private key acquisition unit are generated in the private key generation step, and wherein the signature generation unit generates the signature data in the signature generation step.