Method of elliptic curve digital signature using expansion in joint sparse form

Abstract

A method of generating and verifying a cryptographic digital signature using joint sparse expansion by a signer first selecting a field, an elliptic curve over the field, a point P of order q on the elliptic curve, w, k. Next, generating W=wP and K=kP. Next, transforming K to K*. Next, combining K*, W, and a message M to produce h. Next, combining K*, W, and M to produce c. Next, generating, s by either s=hw+ck (mod q), s=(hw+c)/k (mod q), or s=(hk+c)/w (mod q). Next, forming the digital signature as (K*,s). Next, a verifier acquires the field, the elliptic curve, P, W, M, and (K*,s). Next, computing h and c. Next, selecting (n, n) as either (sc(mod q), −hc(mod q)), (cs(mod q), hs(mod q)) or (−ch(mod q), sh(mod q)). Next, generating binary expansions of nand nin joint sparse form. Next, computing, Q=nP+nW via twin multiplication and a double-add-subtract method with the binary expansions in joint sparse form. Next, transforming, Q to Q*. Lastly, verifying, the digital signature if Q*=K*.