Patent ID: 7792286

Claim:
A signature generation apparatus that generates signature data for message data according to a signature scheme, wherein the signature scheme includes: a key generation step of generating elements f and g of a ring R, and generating an element Fq with respect to the ring R and a positive integer q, the ring R being a set of N-dimensional arrays and defining addition, subtraction, multiplication, and a norm indicating a size of an element, the element Fq being an inverse number of f(mod q), which denotes a remainder obtained when f is divided by q, generating, as a public key, an element h, which is congruent, modulo q, to a product derived as a result of multiplying the element g and the element Fq, generating elements F and G so as to satisfy f×G−g×F=q, where “x” denotes multiplication of the ring R, and generating, as a private key, a set {f, g, F, G}, which includes the four elements f, g, F and G; a signature generation step of generating the signature data for the message data using the private key, the signature data being an element of the ring R; and a signature verification step of verifying the signature data using the public key, and wherein said signature generation apparatus comprises: a signature vector generation device operable to calculate, for the message data, a signature vector made up of elements s and t of the ring R, the signature vector being calculated using the private key; and a signature data generation device operable to calculate a first element and a second element of the ring R, and to generate the signature data, which includes the first element and the second element and is obtained and verified by a signature verification apparatus, the first element specifying the element s, and the second element being a quotient of the element t divided by q.