Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Using $n$-bit ECDSA, a signature has a size of $2·n$. It is possible to recover the public key from this signature, which shows that there is a publicly visible redundancy in the signature.

Is it possible to exploit this redundancy to reduce the signature size to $n$ bits, sacrificing key recovery?

I suspect it's not possible, but I don't know enough about elliptic curves to be sure.

share|improve this question
2  
It's a very interesting question, but unfortunately I also think it is not possible. I may be out of my league here, let me know if I have misunderstood something. The signature is the pair (r, s). r contains information about the selected random integer (n bits), and random data cannot be compressed. s makes the signature dependent on the private key, and also on the message. Since the private key should also be random, this is also non-compressible. So the way ECDSA is constructed, it is impossible to make the signatures shorter than 2n bits. –  MartinSuecia Apr 16 '12 at 12:25
    
Have a look at Implicit certificates. While this doesn't save signature size, it saves the space of the message (this one being a public key). –  Paŭlo Ebermann Apr 16 '12 at 19:48

2 Answers 2

up vote 7 down vote accepted

ECDSA is actually a kind-of computational zero-knowledge protocol, played by the signer, with a "reduction function" as impartial verifier. For that matter, ECDSA is not very different from plain DSA.

Things basically go this way. There is a known public group $\mathbb{G}$ which I will denote additively, with $G$ as generator, and of size $q$ (a known prime integer). For DSA, $\mathbb{G}$ is the group of integers or order $q$ modulo a prime $p$ ($p$ is a bigger prime, such that $p-1$ is a multiple of $q$) with the multiplication as group law; for ECDSA, $\mathbb{G}$ is an elliptic curve (or a subgroup of an elliptic curve).

The signer knows a secret value $x$, an integer modulo $q$. The public key is $Q = xG$ (for DSA, with the multiplicative notation, public key is $g^x \mod p$). The underlying computational zero-knowledge proof protocol works like this:

  • Prover wants to prove to the verifier that he knows $x$, but without revealing $x$.
  • There is a known parameter $h$, a non-zero value modulo $q$.
  • Prover (aka, the signer) selects a random $k$ modulo $q$, and computes $A = kG$. He sends $A$ to the verifier; this is a commitment (by sending $A$, the prover marks that he has chosen some value $k$, which he will not be able to change later on in the protocol; but he does not actually reveal $k$).
  • Verifier chooses a challenge $r$ (supposedly random value modulo $q$) and sends it to the Prover. The cornerstone of the protocol is that $r$ is chosen after the commitment (the Prover cannot compute a specific value of $k$ which depends on the value of $r$).
  • Prover sends back $s = (h+rx)/k \mod q$ where $h$ is a non-zero. The verifier checks that this value matches the commitment and challenge by computing $(h/s)G+(r/s)Q$ which must be equal to $A$.

What goes on here is that the Prover commits to a random value $k$ and then proves that he knows $x/k$ (this is quite similar to the Schnorr identification protocol).

To turn this interactive protocol into a non-interactive signature scheme, we must replace the bit about the random challenge by something which can be computed by the signer alone, yet still be convincing enough about its "randomness" (as I said above, the protocol is good as long as the value $k$ cannot be chosen with a specific challenge $r$ as target); we also need to "inject" the signed message somewhere. So we do the two following things:

  • We say that the parameter $h$ will be the hash of the signed message.
  • We define the challenge $r$ to be the result of the evaluation of a given known function $f$ over $A$. The function $f$ can be quite arbitrary as long as it is deterministic and "somewhat uniform" over a big enough range of output value. For instance, if $\mathbb{G}$ is an elliptic curve, we can choose $f(A)$ to be "the $X$ coordinate of the curve point $A$, converted to an integer and reduced modulo $q$".

And, voila! you have DSA (or ECDSA).

The important point here is that the identification protocol is "computationally zero-knowledge" (i.e. yields no usable information on $x$, at least for a computationally bounded adversary) only because $k$ is chosen randomly and uniformly modulo $q$ every time the protocol is executed (i.e. for every signature). Indeed, the protocol does reveal quite a lot of information on $x/k$ (modulo $q$). But, as long as a fresh $k$ is used every time, the attacker is still short of information. In entropy parlance, we could say that $x$ is $n$ bits of entropy, the random $k$ injects $n$ extra bits of entropy, and the protocol reveals $n$ bits; so, if we run the protocol $z$ times, the total entropy is $n+zn$, and $zn$ bits have been revealed, to there still are $n$ bits of entropy unknown to the attacker -- precisely the private key $x$.

The seemingly redundant nature of (EC)DSA signatures comes from that point. We need to inject some entropy in the system, of a size similar to that of $x$. So, for instance, if we use a 160-bit private key $x$, there must be close to $2^{160}$ possible signature values for a given message $h(m)$, and since a signature on a message must not be valid for any other message, we still need $2^{160}$ distincts sets of signatures. Hence $2^{320}$ possible signature values altogether, for a 160-bit private key.

This extra size is consubstantial to the use of an underlying challenge-response identification protocol as the basis for the signature scheme, so we find it also for all kinds of derivative of the Schnorr identification scheme (including Schnorr signatures, ElGamal signatures, KCDSA...).

share|improve this answer
    
I believe your second to last paragraph is wrong. There is no reason a signature for one message cann't be valid for many other messages, if an attacker cann't determine which other messages it's valid for. For example, any signature that uses a fixed-length hash is valid for many, many messages. This is not a problem because an attacker can't find any others. One could also imagine a signature scheme that signed an n-bit hash with an n-bit signature. So long as you need the private key to go from hash to signature (and only the public key to check a paid), the method could be secure. –  David Schwartz Apr 19 '12 at 11:09
    
@DavidSchwartz: if you aim at 80-bit security, you still need 2^80 distinct signatures (i.e. valid for distinct messages), otherwise exhaustive search on the signature value is a break. So a signature length cannot be less than 80 bits. Algorithms which work on discrete logarithm tend to double that figure (you need a 160-bit group to achieve 2^80 resistance), so 160-bit signatures (that's what you get with BLS). Then, (EC)DSA adds its extra 160 bits, hence the 320-bit DSA signatures. –  Thomas Pornin Apr 22 '12 at 22:51
1  
I agree, but that makes this part false: "since a signature on a message must not be valid for any other message, we still need 2^160 distincts sets of signatures". There is no reason a signature cannot be valid for more than one message so long as someone without the private key can't easily find any such other messages. And there is no reason every possible signature can't be valid for some message, again assuming you can't find the message from the signature without the private key. –  David Schwartz Apr 22 '12 at 22:54
    
"the Prover commits to a random value $k$ and then proves that he knows $x/k$" - This is a nifty insight. Thank you! It seems like it can't be exactly correct: it doesn't seem like it's the Schnorr protocol adapted to prove knowledge of $x/k$, due to the presence of $h$. Intuitively I see why this reasoning makes a connection plausible, though. Is there any way to make this more formal/precise/accurate? –  D.W. Feb 13 '13 at 23:50
    
@D.W.: as far as I know, DSA was designed that way specifically to be sufficiently "different" from Schnorr's signature scheme, to avoid patent issues: see this. So chances are that there is no immediate formal connection between the two. –  Thomas Pornin Feb 14 '13 at 0:06

I don't think there exists an algorithm that could exploit the public key recovery feature in order to compress digital signatures, but even if such an algorithm existed, you would typically not want to use it. If you remove the information that determines the public key $Q$ from the signature $(r,s)$, it would seem plausible to assume that it would become a lot easier to forge such compressed signatures.

  • Sign message $m$ using any public key $Q'$. Compress the signature by removing the information that determines the public key $Q'$. Now claim that the resulting compressed signature is the signature of $m$ using Alice's public key $Q$. Bob takes the compressed signature, expands it using $Q$, and finds that it verifies OK using $Q$.
  • In addition, the $s$ part of the signature depends on both the public key and the hash $H(m)$ of $m$, which is typically also of the same bit size as $Q$. The compression would consequently have to remove information about $H(m)$ from the signature as well.

The details and number of different public keys $Q'$ you would have to try before the attack succeeds would of course depend on the compression algorithm, but like Martin Suecia noteted, since $r$ is random, there can't be many bits in the rest of the signature if the compression works at all, so the odds are high it would verify with a very large number of different public keys. If you got a compressed $n$-bit signature that depends on a $n$-bit random $r$, $n$-bit $H(m)$ and an $n$-bit private key, it doesn't contain enough information to guarantee that adding back the information from the public key will give you something that depends on both the right $r$ and the right $H(m)$. You can't store $2n$ bits of entropy in $n$ bits of data.

Hence, if we assume ECDSA signature forgery is completely out reach, this implies the compression algorithm is impossible.

share|improve this answer
1  
The claim that compressing signatures may make forgeries more likely doesn't sound right (at least, if someone can recover the full ECDSA signature using only the public key). After all, someone could generate their own key $Q'$, sign a message with it, compress it, and then attempt to decompress it with someone else's public key $Q$. If that decompresses into a signature that verifies, they've just generated a forgery. –  poncho Apr 16 '12 at 13:30
    
@Poncho: Sorry, I don't quite get what you are saying. In the first sentence you say that I am wrong, but the second and third directly implies I am right. –  Henrick Hellström Apr 16 '12 at 13:36
2  
What I'm trying to say is that in compressing ECDSA keys can lead to a forgery, then you can use that to generate forgeries in an unmodified ECDSA system (by having the attacker compress and decompress the signatures himself). Because ECDSA is not believed to have such a weakness, then such a compression scheme (at least, with the limitations I specified) also cannot have such a weakness. I do not believe that such a compression scheme exists (because r is random and you need all the information in s), but if it did, it wouldn't be weak. –  poncho Apr 16 '12 at 13:46
    
@Poncho: Well, my initial claim was that such a compression algorithm can't exist, so we clearly agree on that. Secondly, I don't see anything inherently illogical about assuming that (the completely imaginary) compression could only be carried out if you have the private key, while decompression would only require the public key. –  Henrick Hellström Apr 16 '12 at 13:52
1  
@Poncho: It's a bit pointless to argue about which one of two reasons for something being impossible is the "right" reason why it is impossible. :) However, a significantly compressed signature must contain at least n bits from the random $r$ component. Hence, if it exists, the correct conclusion from your observation would actually be that the compression algorithm constitutes a break of ECDSA. –  Henrick Hellström Apr 16 '12 at 14:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.