Is there a cryptographic primitive that allows "signature chaining"?
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.