Disclosed herein are methods, systems, and apparatus, including computer programs encoded on computer storage media, for recovering and verifying a public key. One of the methods includes accepting information encoding parameters of an elliptic curve, a published public key, a hash value of a message, a digital signature, and an identification parameter; generating a recovered public key based on the parameters of the elliptic curve, the hash value of the message, the digital signature, and the identification parameter; comparing the published public key and the recovered public key to verify the published public key.