SIGNATURE GENERATING APPARATUS, SIGNATURE VERIFYING APPARATUS AND METHODS THEREFOR

摘要

A signature is generated by a scheme in which x denotes a secret key of a signature generating apparatus, m rec ~ {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 g k ~ G, H1 represents a hash function H1: {0, 1}* .fwdarw. {0, 1}L, H2 represents a hash function H2 : {0, 1}* .fwdarw. {0, 1}M that has a variable output length, H3 represents a hash function H3: {0,1}* .fwdarw. Z q, r = H1(R, m rec)¦m rec(+)H2(R, H1(R, m rec)), where (+) represents an exclusive-OR operator, t is defined for .gamma., which depends on r, as t = H3(.gamma.), s is defined as s = k-t.cndot.x ~ Z, and a signature is .sigma.=(r, s).