Can one reduce the size of ECDSA-like signatures?

Question

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.

Answer 1

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...).

Answer 2

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.