Can one reduce the size of ECDSA-like signatures? Using $n$-bit ECDSA, a signature has a size of $2&#183;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.
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...).