Minimizing size of signed message with discrete-log scheme

Question

How can we sign a small message with a discrete-log scheme so as to minimize the size of the whole signed message?

---

Detailed objectives, notation:

1. It is of paramount importance to minimize the total bit size $c$ of the cryptogram $C$ carrying the whole signed message $M$, e.g. because $C$ will be keyed-in (appropriately transformed to characters). $M$ is an arbitrary bitstring of $m$ bits, for some parameter $m$ with $32\le m\le256$.
2. We restrict to asymmetric signature algorithms loosely based on the discrete logarithm problem in some group (we note $q$ its order), e.g. because some directive only allows that or integer factorization which is inappropriate given 1; schemes using pairing-based cryptography are out. We have unrestricted choice of symmetric primitives likes hashes.
3. It must be arguable that a competent adversary using public knowledge and classical computers is unlikely to exhibit a forged signature (in a chosen-messages setup) with $2^w$ work for some parameter $w\approx80$, in a sense such that $w=67$ represents the work reported for the factorization of RSA-768:

   ^{Our computation required more than 1020 operations. With the equivalent of almost 2000 years of computing on a single core 2.2GHz AMD Opteron, on the order of 267 instructions were carried out.}

4. Each signature generation and verification must be feasible with $2^{32}$ work, but performance is otherwise non-critical, as well as key size (public and private).

Questions:

• Are there better schemes than DSA and ECDSA variants with message recovery (see bibliography in this question), and which one(s) can we choose? What is the corresponding maximum capacity (that is, the largest $m$ such that we have full message recovery, and larger messages start to require increasing $c$)?
• Are we better using group $\mathbb Z_p^*$ with $q$ a prime factor of $p-1$ as in plain DSA, or an Elliptic-Curve group, or..?
• What parameters is it reasonable to use (for DSA variants: size of $p$ and $q$; for ECDSA variants: curve..), and what's the $c$ achieved?

Update: I now realize that the Schnorr signature scheme of 1989 yields $c=m+3w$-bit (for at most $2^{w/2}$ signatures). That's a candidate (related question).

---

Extras:

• In (EC)DSA, we can trim a few bits from $C$ (reducing $c$ by $z_s+z_v$), by having the signer iterate signing until $z_s$ prescribed bits are (say) all set; and the verifier iterates verification with incremental values of $z_v$ other prescribed bits, until finding a signature that verifies. We can increase $z_s$ and $z_v$ within the limits set by requirement 4, with almost no reduction of security. Can we better leverage that leeway? E.g. by increasing $p$ in DSA, or somewhat using an entropy-stretching KDF (PBKDF2, Argon2..)? [for the DSA aspect of that, see this question]
• Does things appreciably change, allowing lower $c$, if we relax security requirement 3 to distinguish between total breaks that allow the adversary to recover the private key or otherwise sign any $M$ at low cost, and those that would be unprofitable to an adversary if each forgery requires $2^{w'}$ work with $w'\approx w-16$?

Answer 1

This only answers part of the question, but here goes:

Classical Schnorr signatures start (in my notation, which I think will be helpful here) with a field $\mathbb F$, a linear map $f: \mathcal W \to \mathcal V$ over $\mathbb F$-vector spaces and a hash $H$ with codomain in $\mathbb F$. For simplicity let's take $\mathcal W = \mathbb F$. I'll use capital letters for elements of $\mathcal V$ and small ones for field elements. Intuitively, elements of $\mathcal V$ take more bits to represent than field elements.

The finite field implementation is to take primes $p, q = (p-1)/2$ and set $\mathbb F = \mathbb Z_q$, $\mathcal V$ is an order-$q$ subgroup of $\mathbb Z_p$ generated by some $g$, vector addition is $v \oplus w := v \cdot w \pmod{p}$ and scalar multiplication (that makes the whole thing into a vector space) is $(x, V) \mapsto V^x \pmod{p}$. The linear function is $f(x) := g^x \pmod{p}$ for vanilla Schnorr.

For elliptic curve implementations (DSA, ECDSA, EdDSA) $\mathbb F$ is a finite field and $\mathcal V$ is a group defined over an appropriate elliptic curve, with point addition serving as vector addition and scalar multiplication of $x$ with $V$ is point-adding $V$ to itself $x$ times.

In both cases,

• A keypair is a pair $(x, Y = f(x)) \in \mathbb F \times \mathcal V$.
• To sign $M$ (which can be any bitstring), you pick a random $r \in \mathbb F$, set $A = f(r)$, $c = H(Y, A, M)$ and $s = r + cx$.
• The "$4w$" version of the signature is $(A, s) \in \mathcal V \times \mathbb F$ whereas the "hash compressed" or "$3w$" version is $(c, s) \in \mathbb F \times \mathbb F$, since field elements are smaller than $\mathcal V$ elements.
• The verification equations in both cases are $c = H(Y, A, M)$ and $f(s) = A + c \cdot Y$.

Which brings me to two recommendations.

1. In the hash-compressed version, the signature consists only of field elements, so it should not matter for signature size if you choose a finite-field or EC implementation: the size of keys (field elements) is the same for both at the same security level on keylength.com. What EC buys you is shorter $\mathcal V$ elements, which is irrelevant here. I'd personally go with Ed25519 just because I like it.

2. The probability of forging a proof is commonly given as $1/|\mathbb F|$ but really it's the inverse of the size of the codomain of the hash. While $s$ has to be a full field element, you can truncate the hash value $c$ to any smaller number $k$ of bits as long as you're happy with a lower soundness factor of $2^{-k}$.

EDIT: You can also do the $z_s + z_v$ bits thing here of course, but it seems like it doesn't buy you much. I thought for a bit how I'd prove the security of the version where the verifier iterates over $z_v$ "omitted" bits and the best I could come up with is a union bound, so by omitting $z_v$ bits you lose $z_v$ bits of security and force the verifier to do $2^{z_v}$ times the work, in exchange for transmitting $z_v$ fewer bits. Shortening the hash output by $z$ bits also loses you $z$ bits of security, but doesn't cause anyone more work. (If you can prove that you can fix or omit some bits without losing that many bits of security, then of course this option becomes attractive again.)