
A management center 520 determines a public key y.sub.A of a user A 510 using the user A's secret key x.sub.A and announces the public key y.sub.A to a user B 530. The user A 510 repeats generation of a random number k and calculation of r.sub.1 =g.sup.k (mod p) and r.sub.2 =f(r.sub.1,m)=r.sub.1 +m(mod p) until r.sub.2 and q meet a condition r.sub.2 <q. If the condition is met, the user A 510 finds s by calculating sk=(r.sub.2 +S+1)+r.sub.2 x.sub.A (mod q) and sends a ciphertext (r.sub.2,s) t...











