Patent ID: 8280039

Claim:
A signature generation apparatus for generating a digital signature for a message by applying a power operation, the power operation being a basic operation performed a plurality of times with respect to a basic element P in a group G and a basic element Pa in a group Ga, and security of the digital signature being based on a discrete logarithm problem of the group G and the group Ga, the signature generation apparatus comprising: a split value storage unit storing a plurality of split groups, the plurality of split groups corresponding to a plurality of numbers, such that (i) each split group, of the plurality of split groups, includes a plurality of split pairs, (ii) each split pair, of the plurality of split pairs of each respective split group of the plurality of split groups, includes a first split value and a second split value, (iii) each first split value of the plurality of split groups is an element that belongs to the group G and is calculated by applying, to the basic element P, a power operation in which a power is an arbitrary positive integer, and (iv) each second split value of the plurality of split groups is an element that belongs to the group Ga, wherein each respective second split value is calculated by applying, to the basic element Pa, a power operation in which a power is the arbitrary positive integer used to calculate the first split value of the split pair including the respective second split value; a selection unit selecting a number u randomly from among the plurality of numbers, and selecting a split group, of the plurality of split groups, corresponding to the selected number u; a generation unit (i) applying a basic operation of the group G to two or more of the first split values in the selected split group, so as to generate a first exponential element, and (ii) applying a basic operation of the group Ga to the second split values in the selected split group that correspond to the two or more first split values in the selected split group, so as to generate a second exponential element; and a signature unit (i) transforming each of (a) the generated first exponential element and (b) the message into an element in the group Ga, (ii) applying an operation of the group Ga to the transformed first exponential element, the transformed message and the second exponential element, so as to calculate a first discrete logarithm and a second discrete logarithm, and (iii) generating the digital signature for the message with use of the calculated first and second discrete logarithms.