Accelerated verification of digital signatures and public keys

A non-transitory computer-readable medium storing instructions that, when executed by one or more processors, perform operations comprising:

• receiving, from a signer, a signature on a message M, wherein the signature includes a first signature component r and a second signature component s;
• obtaining an elliptic curve point associated with the first signature component r;
• and
• generating a public key of the signer based on the elliptic curve point and a hash value e computed from the message M;
• wherein the elliptic curve point comprises a first elliptic curve point R, the public key of the signer comprises a second elliptic curve point Q, generating the public key of the signer comprises computing Q=r−1 (sR−eG), and G comprises a generator of an elliptic curve group that includes the first elliptic curve point R and the second elliptic curve point Q.

A computing device comprising:

• a cryptographic module operable to:
• receive, from a signer, a signature on a message M, wherein the signature includes a first signature component r and a second signature component s;
• obtain an elliptic curve point associated with the first signature component r;
• and
• generate a public key of the signer based on the elliptic curve point and a hash value e computed from the message M;
• wherein the elliptic curve point comprises a first elliptic curve point R, the public key of the signer comprises a second elliptic curve point Q, generating the public key of the signer comprises computing Q=r−1 (sR−eG), and G comprises a generator of an elliptic curve group that includes the first elliptic curve point R and the second elliptic curve point Q.