Signature generating device, signature verifying device, their methods, and their programs

摘要

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, H 1 represents a hash function H 1 : {0, 1} * †’ {0, 1} L , H 2 represents a hash function H 2 : {0, 1} * †’ {0, 1} M that has a variable output length, H 3 represents a hash function H 3 : {0, 1}* †’ Zq, r = H 1 (R, m rec )lm rec (+)H 2 (R, H 1 (R, m rec )), where (+) represents an exclusive-OR operator, t is defined for ³, which depends on r, as t = H 3 (³), s is defined as s = k-t·x ˆˆ Z, and a signature is à = (r, s).