Patent ID: 8516261

Claim:
A message sending method for sending a message by a process of a computer including a processor and a memory, the method comprising the steps of: randomizing a signature generation key sk_s with a random number r to calculate a randomized signature generation key sk′_s=SigningKeyRandomize(sk_s, r); encrypting the random number r with a public encryption key pk_e to calculate an encrypted random number R=Enc(pk_e, r); signing a message m with the randomized signature generation key sk′_s to calculate a signed message s′=Sign(sk′_s, m); and sending the signed message s′ and the encrypted random number R to a recipient, where sk_s represents the secret signature generation key of a sender of the message m, pk_e represents the public encryption key of the recipient, r represents the random number, s represents a signature, Sign represents a signature generation function, s=Sign(sk_s, m) represents a signature for the message m, SigningKeyRandomize represents a function for randomizing the secret signature generation key sk_s, and Enc represents an encryption function.