Patent ID: 8467535

Claim:
A method, performed by a data processing apparatus, of generating a signature on a message, the method comprising: accessing a long-term private key of a long-term private-public key pair; dividing the message into a first message portion and a second message portion; generating an ephemeral key pair that comprises an ephemeral private key and an ephemeral public key, the ephemeral public key being derived from the ephemeral private key and a base point on an elliptic curve; encrypting the first message portion to obtain a first signature component using an encryption key, the encryption key derived from the ephemeral public key; applying a first mathematical function to a combination of the first signature component and the second message portion to obtain an intermediate component e; using the intermediate component e to generate a first value e 1 and a second value e 2 such that a second mathematical function applied to the first value e 1 and the second value e 2 obtains the intermediate component e; using the first value e 1 , the second value e 2 , the long-term private key, and the ephemeral private key to generate a second signature component; and outputting the signature, wherein the signature comprises the first signature component, the second signature component, and the second message portion.