Patent ID: 7739504

Claim:
A signature generation apparatus which generates signature data for message data, using a signature scheme, wherein the signature scheme includes: a key generation step of generating elements f and g of a ring R and 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 which indicates 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 which is derived as a result of multiplying the element f and the element Fq, generating elements F and G so as to satisfy f×G−g×F=q, where “×” denotes multiplication of the ring R, and generating, as a private key, a set {f, g, F, G} which includes the four elements of 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 said signature generation apparatus comprises: a signature generation unit operable to generate the signature data for the message data using the private key, the signature data being the element of the ring R; and a signature conversion unit operable to convert a format of the signature data without changing a norm of the signature data, so that a target sub-element indicates a predetermined value, the target sub-element being one of N sub-elements included in the signature data, and a hash value generation unit operable to generate two N-dimensional arrays indicating a hash value for the message data, wherein said signature conversion unit is operable to convert the format of the signature data so that the target sub-element indicates a value which is one of 2·N sub-elements included in the two N-dimensional arrays indicating the hash value, where “·” denotes multiplication of integers.