Methods, systems, and computer programs for verifying a digital signature are disclosed. The verifier accesses an implicit certificate and a digital signature provided by the signer. The implicit certificate includes a first elliptic curve point representing a public key reconstruction value of the signer. The verifier accesses a second elliptic curve point representing a pre-computed multiple of the certificate authority's public key. The verifier uses the first elliptic curve point and the second elliptic curve point to verify the digital signature. The verifier may also use a third elliptic curve point representing a pre-computed multiple of a generator point. Verifying the digital signature may provide verification that the implicit certificate is valid.