Patent ID: 8458478

Claim:
A signature generating apparatus, comprising: an arbitrary value generator that generates an arbitrary value k which is an integer; a group calculator configured to calculate R=g k ∈G, where G is a cyclic group of order q having a generator g, to generate a calculation result R; a first hash calculator configured to apply a hash function H 1 : {0, 1}*→{0, 1} L to a value α, to generate an L-bit hash value h=H 1 (α)∈{0, 1} L , where the hash function H 1 outputs an L-bit value in response to an input value, L is a positive integer shared with a signature verifying apparatus, and the value α depends on the calculation result R and an M-bit recovery message m rec ∈{0,1} M ; a second hash calculator configured to apply a hash function H 2 : {0, 1}*→{0, 1} M to a value β, to generate an M-bit hash value u=H 2 (β)∈{0, 1} M , where an output bit length M of the hash function H 2 is determined according to the bit length M of the recovery message m rec , and the value β depends on the calculation result R and the hash value h; an r value calculator configured to calculate a value r that depends on an L+M-bit bit connection value h|w∈{0, 1} L+M in which the hash value h∈{0, 1} L is placed at a first bit position and an exclusive-OR value w ∈ {0, 1} M is placed at a second bit position, and from which the hash value h and the exclusive-OR value w are capable of being recovered, wherein the exclusive OR value w is obtained by exclusive OR calculation of the recovery message m rec and the hash value u according to w=m rec (+)u∈{0,1} M , where (+) represents an exclusive-OR operator; a third hash calculator configured to apply a hash function H 3 : {0, 1}*→Z to a value γ which depends on the value r, to generate a hash value t=H 3 (γ) ∈Z, where Z is an integer, and the hash function H 3 outputs an integer in response to an input value; an integer calculator that calculates s=k−t·x∈Z to generate a calculation result s, where x is a secret key which is an integer; and a signature output unit configured to output a signature σ=(r, s).