English to French Tech/Engineering Computers: Software COMPRESSED ECDSA SIGNATURES

A cryptographic scheme known as the Digital Signature Algorithm (DSA) is based on the well known and often discussed intractability of the discrete logarithm problem. The DSA was proposed by the U.S. National Institute of Standards and Technology (NIST) in 1991 and has become a U.S. Federal Information Processing Standard (FIPS 186) called the Digital Signature Standard (DSS). The algorithm is a variant of the well known ElGamal signature scheme, and can be classified as a digital signature with appendix (i.e. one that relies on cryptographic hash functions rather than customized redundancy functions).

To verify the signature (r, c), the vérifier 14 first computes W = eP + rQ which can be done using public information available to the recipient. As discussed above, e is generally computed as a hash of the message m, e.g. e = H(m). The verifier then attempts to compute d = og,y (cR), using knowledge that d is smaller than a predetermined bound agree d by the signer and verifier for purposes of signature compression. If no such d can be found within the bound, then the compressed signature (r, c) is rejected as being invalid. Similarly, if a value of d is obtained that meets the bounds agreed, the signature may be
considered verified. Such discrete logarithm algorithms generally take time proportional to 4d. if -Jd is small enough, then it is quite practical for the verifier 14 to use such an algorithm. Once (and if) d is obtained by the verifier 14, the full signature (/% s) can be recovered by computing s = c/d mod n, allowing the verifier 14 to also use or verify the full signature if he wishes.

Although the invention has been described with reference to certain specific embodiments, various modifications thereof will be apparent to those skilled in the art without departing from the scope of the invention as outlined in the claims appended hereto. For example, the technique may be used with other discrete log signature algorithms where an ephemeral private key is used to generate a first signature component that is then bound to the message and the long term private key of the signer to produce a second signature component.

A method of compressing a digital signature of a message m (m), said signature generated using a discrete log signature algorithm, said signature comprising a pair of signature components r, s (r,s), said signature component r generated from an ephemeral private key and said signature component s generated from a long term private key, the message (m) and the signature component r, said method comprising:
obtaining a pair of values c, d (c,d) related mathematically to s (s), one of said values being smaller than s;
generating a compressed signature by substituting said one of said values for the signature component s in said digital signature; and
forwarding said compressed signature to a recipient.