What are the implications of limiting the private key space with elliptic curve Schnorr signatures?

Question

Given a curve, I am trying to limit the private key space to ultimately cut down the Schnorr signature size as follows:

Assume an elliptic curve $E$ over a field $F$ with generator point $G$ and the main subgroup's order being $\ell$. Field $F$ can be assumed to be secure. (For the sake of an example, it may be assumed that the parameters are those for Curve25519, but I am looking for a generic, canonical answer.)

I am looking at Schnorr signatures in particular, but the answer to my question will likely extend to EdDSA and its variants as well. Summarizing the signing process for private key $k$ (scalar) and message $M$ (sequence of bytes)

1. Randomly select a scalar value $r$ (nonce) as ephemeral random scalar in the range $0 < r < \ell$.
2. Generate the ephemeral curve point $R = [r]G$.
3. Generate the hash value $c = H(\underline{R} || M)$, where $H$ is a cryptographic hash function, $\underline{R}$ denotes the serialized form of the point $R$ as a sequence of bytes and $||$ denotes concatenation. Interpret the sequence of bytes $c$ as a scalar integer.
4. Compute the scalar value $S = r + ck \mod \ell$.
5. The signature is now the tuple $(c, S)$.

Note how $S$ is the result of an addition and a multiplication taken modulo $\ell$. By limiting the private key space (i.e. the artificially reducing the possible range of $k$), it is therefore also possible to limit the size of the resulting $S$.

Assume now that the upper limit for $k$ is reduced from $\ell$ to $2^n$; within this reduced space, $k$ is still picked uniformly at random. The nonce value $r$ is picked in the normal space $0 < r < \ell$ in any case.

Given this background, my questions are:

1. How does reducing the upper limit for $k$ improve an attacker's chances to learn $k$ other than the obvious reduction in brute force search space for any given $n \le \log_2 \ell$?
2. How does reducing the upper limit for $k$ from $\ell$ to $2^n$ interact with short Schnorr signatures? I take “short Schnorr signatures” to mean trimming the hash value $c$ is trimmed to $b$, where $b$ is the strength of an elliptic curve in bits (e.g. for Curve25519, that would mean using a 128-bit hash value for $c$; see also Schnorr's original paper on p. 242 in particular as well as the subsequent analysis by Gregory Neven, Nigel P. Smart, Bogdan Warinschi. Hash Function Requirements for Schnorr Signatures, Journal of Mathematical Cryptology 3(1), 2009, pp. 69–87, which ends with an uncomfortably loose security reduction, but should be assumed safe for the purpose of this question).
3. Assuming a curve over a prime field $F_q$, where $q$ is a 256-bit number, how much could the space for $k$ be reduced and still meet a target security level of 80-bit symmetric equivalent strength?

---

This is interesting for efficiency reasons: If the space for $k$ can be lowered significantly, the final computation $\mod \ell$ can be either skipped entirely or at least simplified, yielding speed increases at signing time.

I am aware that BLS signatures exist and yield short signatures (e.g. BLS12-381 gives 48-byte signatures), but they are significantly more complex to implement and compute. Similarly, I am aware that some multivariate cryptography schemes yield very short signatures (Gui comes to mind, though patented). If I just wanted very short signatures, I would look into schemes that are not Schnorr signatures.

A similar question has been posted before; “64 bit Elliptic Curve Key”. However, the answers there generally assumed either creation of a new curve over a 64-bit field or truncating the public key, neither of which apply here, as I am reducing the range for the private key, leaving the public key and the field as-is.

Answer 1

How does reducing the upper limit for $k$ (to $2^n$) improve an attacker's chances to learn $k$

Security becomes at most $n/2$-bit. Baby step - giant step finds $k$ given the public key $\underline{[k]G}$ with computational cost $\mathcal O(2^{n/2})$. Pollard's Rho can be adapted to the same asymptotic cost, with feasibly little memory and efficient parallelisation. In order to keep the security level $\mathcal O(\sqrt\ell)$ of normal EC-Schnorr, we can't have $n$ sizably below $\log_2\ell$.

How does reducing the upper limit for $k$ from $\ell$ to $2^n$ interact with short Schnorr signatures?

For the reason above, it reduces security.

Also, I fail to see how it reduces signature size in the signature scheme of the question if we keep $r$ random in $[0,\ell)$ with $\ell$ unchanged, because then $S$ also is random in $[0,\ell)$, thus we need to transmit $\left\lceil\log_2\ell\right\rceil$ bit for $S$.

---

For $n$-bit symmetric security (80-bit in the question), and as small a Schnorr signature as possible, we can

1. Use an Elliptic Curve group of reduced size $\ell\approx 2^{2n}$. That's precisely why we have secp192r1 and secp192k1 in sec2-v2, which are expected to give 96-bit security. However these use a base field $\Bbb F_q$ of roughly the same size as $\ell$, and I do not know if, much less how, we could construct a secure Elliptic Curve group based on $\Bbb F_q$ of much larger size (e.g. $\log_2 q\approx256$ as asked).
2. Reduce the hash width from the usual/modern $2n$ to the original $n$, for a $3n$-bit signature when combined with 1. The original Schnorr signature scheme works that way, with heuristic arguments of security that withstood at least the test of time.
3. As an alternative to 2., and when signing messages of bit size $m\ge n$, use a variant of Schnorr's scheme giving signature scheme with message recovery (see list there), which can embed $n$ bits of message into a $4n$-bit signature, thus achieve an effective $3n$-bit overhead just like the original Schnorr signature scheme in applications where the message is sent along the signature and is at least $n$-bit. The main advantage is a slightly more positive argument of security. The drawbacks are that the signature is no longer separate from the message, that some of the best schemes are patent-encumbered, and that (therefore) this is seldom used.

Note: if only signature size (but not public key size nor performance) is an issue, there is no reason to use an Elliptic Curve group. The original Schnorr signature scheme uses Schnoor groups over a subgroup of prime order $\ell$ constructed as a subgroup of $\Bbb Z_p^*$ for prime $p=2\,r\,\ell+1$, and the signature size is not impacted by the large $p$ (which needs to be in the thousands bits for modern security).

---

If one is (like me) prudently cautious about the heuristic security arguments (and complex modern proofs in some limited models) of the original Schnoor signature scheme, one can venture into improvements:

• De-randomize the choice of $r$ by making it a deterministic PRF, keyed by the $2n$-bit private key, of a (wide, secure) primary hash of the message: $r=\operatorname{PRF}_k(H_\text{wide}(M))$. It removes the requirement for an unpredictable RNG (which is notoriously hard to get), and could only harm thru a side channel. That's used by EdDSA.
• Construct the $n$-bit (thus uncomfortably narrow) hash $c$ part of the signature using a purposely-slow hash (like Argon2) in order to increase it's second-preimage resistance, which is one of (and arguably, the main) limiting factor of security in Schnorr signature. It can not harm. Even with parametrization yielding negligible impact on overall performance, it can increase resistance to that particular attack by at least 8 bits, which is nice to have.
• Make the public key part of the input of said $n$-bit hash $c$. This is a belt-and-suspenders approach against multi-target attacks. It has negligible cost, and can not harm. Combined with the above, that makes the $c$ part of the signature $c=H_{n\text{-bit, slow}}(\underline{R}\mathbin\|H_\text{wide}(M)\mathbin\|K_\text{pub})$
• [my personal fad] Rather than directly using the $n$-bit $c$ part of the signature $(c,S)$ in the computation of $S=r+c\,k\bmod\ell$, we can beef it back to the full $2n$-bit of $\ell$ (as used in modern variants of Schnorr signature having the strongest security arguments) by using a public transformation, e.g. a hash. With maximum belts-and-suspenders, that's $S=r+c'\,k\bmod\ell$ with $c'=H_{2n\text{-bit, slow}}(c\mathbin\|H_\text{wide}(M)\mathbin\|K_\text{pub})$. Arguably, it can't harm, and adds hurdles to various conceivable attacks.

The above leaves the signature size at $3n$-bit, needs only trivial adaptations to signature verification, and marginally slows down signature generation or verification. For large messages, $H_\text{wide}$ is the limiting speed factor, and we can use e.g. SHA-512 for that. Parametrization of the slow hash can be set for cost lower than one scalar multiplication, with perhaps 3/4 of that in the slow hash that builds $c$, and the rest for $c'$.