Let's assume that a digital signature scheme $S$, which is secure against existential forgery under adaptive chosen message attack, can only be used with fairly short signature inputs, i.e. $S(sk, m)$ has a constraint of $len(m) < n$.
Is there a way to use this scheme in a way that gives stronger protection against forged signatures than the naive solution of signing the first $n$ bit of the output of a hash function over a message, i.e.
$S'(sk, m) = H(m)[0..n]$?
The security of $S'$ seems to be limited by the relatively short output of the hash function: Finding a hash that collides only in the first $n$ bits of a message pair $(m, m')$ allows for a forged signature, even though the asymmetric primitive itself might not allow for a forgery.
One way I can think of is to apply the signature function over slices of the hash output and concatenate the results, i.e.
$S''(sk, m) = S(sk, H(m)[0..n]) || S(sk, H(m)[n..2n]) ...)$,
but that would allow for the rearranging of the signed parts, which does not seem good.
When driven to the logical extreme, setting $n = 1$, it becomes obvious that any such scheme will fall apart, given that there are only two possible signature outputs that can be interpreted as logical zeroes and ones, and rearranged to form any desired hash output.
The scheme could be further improved by encoding the "block number" in the signature input, or by somehow chaining the hash output and the signature output with some feedback mechanism similar to some hash function or block cipher modes of operations, but I'm going to stop here since I'm assuming that what I'm trying to do is generally impossible:
Assuming that the number $i$ of signature operations that an attacker can perform is bounded to $i<\sqrt(n)$ (i.e. the birthday bound), is there a way to construct any signature scheme $S'$ that makes an existential forgery harder than $O(n)$ for an attacker, given the constraints on the atomic input into the asymmetric signature function?
And does the situation change if the adversary does not have access to $S$, but only to $S'$ (i.e., can $S'$ then be possibly made secure even for $i > n$)?
(I'm aware that the assumptions in my question might be a logical contradiction with the chosen security properties of the "atomic" signature scheme. In this case, let's assume that it is as secure as possible given the constraints, i.e. an input of only $n$ bit and no other user-controllable randomness, even though it might internally use a random padding scheme etc.9