Is there a cryptographic primitive that allows "signature chaining"? 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) &lt; 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&lt;\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 &gt; 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
Assuming that the number $i$ of signature operations that an attacker can perform is bounded to $i&lt;\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?


It would appear that we can do better than that, assuming a bound on the number of valid signatures that can be generated.

Here's is one possible approach; we apply a randomized hash that converts the message into 5 different 64 bit values (perhaps the signer selects a random value and then hashes that value along with the message using SHAKE-256, squeezing out $5\cdot 64$ bits); then, you sign each 64 bit value using the asymmetric function.  Then, for the signature, you publish the random value and the 5 signatures.

To generate a forgery (assuming that the attacker cannot attack the 64 bit signature operation directly), the attacker would need to find a different randomizer/message pair that hashed to values that has already been signed (and so he can put together the signature using values he has already seen).

If we assume that the valid signer will sign no more than $2^{32}$ messages, that means that the attacker has (at most) $5 \cdot 2^{32} &lt; 2^{35}$ 64-bits values for which he has the signature.  Then, for any randomizer/message pair he selects, he hashes it; if we treat the hash as a random Oracle, then that produces 5 random 64 bit values, without the attacker having any control of those values before he hashes them.  Each value has, at most, a probability of $&lt;2^{35-64} = 2^{-29}$ of being a value he has a signature for.  To create a valid forgery, all 5 values need to be values he has signatures for, and so the total probability of success (for each trial) is no more that $2^{-145}$.  Hence, the expected number of trials the attacker needs to do before he is successful is $2^{145}$, which is considerably better than what you asked.