A signature is generated by a scheme in which x denotes a secret key of a signature generating apparatus, mrec∈{0, 1}M denotes a recovery message, k denotes an arbitrary value, g denotes a generator of a cyclic group G of order q, R represents gk∈G, H1 represents a hash function H1: {0, 1}*→{0, 1}L, H2 represents a hash function H2: {0, 1}*→{0, 1}M that has a variable output length, H3 represents a hash function H3: {0, 1}*→Zq, r=H1(R, mrec)|mrec(+)H2(R, H1(R, mrec)), where (+) represents an exclusive-OR operator, t is defined for γ, which depends on r, as t=H3(γ), s is defined as s=k−t·x∈Z, and a signature is σ=(r, s).