Is there a cryptographic primitive that allows "signature chaining"?

Question

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

Answer 1

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?

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} < 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 $<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.

Answer 2

1 bit is enough. If you have a signature scheme that can sign 1-bit messages, then you can do everything.

The construction works in two steps:

Step 1: Use the 1-bit signature scheme to construct a one-time signature for messages of arbitrary length.

Let $\kappa$ be the security parameter. The verification key for the new scheme consists of $2\kappa$ verification keys for the 1-bit scheme; call them $vk_1, \ldots, vk_{2\kappa}$.

To sign a message $m$ in the new scheme, first hash $m$ to $h = H(m)$, whose output length is $2\kappa$. Then for each $i$, give out $\textsf{Sign}(sk_i,h[i])$. Hopefully it's reasonably clear why this collection of signatures on single bits is [only] a one-time signature on $m$.

Step 2: Use the 1-time signature to obtain a full-fledged signature. This is the classical authentication-tree idea from Goldwasser-Micali-Rivest. I sketch the main idea here.

Imagine a complete binary tree of height $2\kappa$, where each node $i$ in the tree corresponds to an instance of a one-time signature with keypair $(vk_i, sk_i)$. The $vk_0$ of the root is the overall verification key for the many-time scheme that we are constructing. We will only use the instance at node $i$ to sign the verification keys of its two children, i.e., $\textsf{Sign}(sk_i, vk_{i\|0} \| vk_{i\|1})$. In this way, we fulfill the promise of it being a one-time signature. Now in the overall scheme, to sign a message $m$ (without loss of generality, a $2\kappa$-bit hash) we just interpret $m$ as the name of a leaf and give $\textsf{Sign}(vk_m, 1)$, along with all of the one-time signatures along the path from root to leaf $m$. This "chain of trust" can be verified starting with the root $vk_0$.

What I just described is secure against forgery, but it has exponential-size signing keys. It can be made more efficient by deriving all one-time $sk_i$ keys from a PRF. More specifically, the overall signing key is a PRF key $s$, and whenever we want to access $(sk_i,vk_i)$ of a particular node $i$ in the tree, we just use $sk_i = \textsf{PRF}(s,i)$.