Patent Document ID: 8745376
Application ID: 13273503
Patent Status: 1

Claim One:
1. A computer implemented method for verifying a digital signature, the method comprising: accessing a digital signature associated with an entity, wherein the digital signature includes a first signature element r and a second signature element s; accessing a message m associated with the digital signature (r,s); accessing an implicit certificate issued by a certificate authority and associated with the entity, the implicit certificate including a first elliptic curve point P representing a public key reconstruction value of the entity; accessing a second elliptic curve point C 1 representing a pre-computed multiple of a public key C of the certificate authority; accessing a third elliptic curve point G 1 representing a pre-computed multiple of a generator point G, the generator point G representing a generator of an elliptic curve group of order n; obtaining a fourth elliptic curve point R based on the first signature element r; computing a first integer u and a second integer v based on the digital signature, wherein the first integer u and the second integer v are each less than √{square root over (n)}; computing a hash h of the message m; computing a third integer λ 0 and a fourth integer λ 1 such that λ=λ 0 +λ 1 2 ┌t/2┐ , where t=┌log 2 (n+1)┐, λ=hv/s; computing a fifth integer γ 0 and a sixth integer γ 1 such that γ=γ 0 +γ 1 2 ┌t/2┐ , where γ=vr/s; verifying that λ 0 G+λ 1 G 1 +γ 0 C+γ 1 C 1 +uP−vR= to verify the digital signature by data processing apparatus, where represents an identity element of the elliptic curve group.