Can randomness protect a list of signatures against forgery attacks?

Suppose we have a list of signatures $$S = [s_1, .., s_n]$$ for a list of messages $$M = [m_1, .., m_n]$$, and we want to verify that $$S$$ is a valid signature of $$M$$, so each $$s_i$$ should be valid for each $$m_i$$.

If we proceed, instead of verifying all $$n$$ signatures, by verifying a set of $$k \lt n$$ messages chosen randomly and uniformly, for a random $$k$$, we could say that $$S$$ is valid for $$M$$ with a "certain probability" depending on how many messages we verify.

My question is: If an attacker wants to forge a list $$M'$$, say he uses $$l$$ messages from $$M$$ with their valid signatures, and adds $$n - l$$ new messages with invalid signatures, constructing new lists $$M'$$ and $$S'$$, hoping that $$l \geq k$$ and that we would only verify the $$l$$ valid ones, and assume that $$S'$$ is valid for $$M'$$ (which is not the case !).

Will he have a high chance or probability of forging such a list of messages, if he has no information about $$k$$ ($$k$$ chosen randomly on each verification)?

• I believe the answer will depend on the probability distribution that $k$ is chosen from... – poncho May 31 '19 at 15:49

If $$l, then the attack will be detected with a probability 1.
If $$l\ge k$$, the probability of the attack not being detected is $$\frac{l}{n}\cdot \frac{l-1}{n-1}\cdots \frac{l-k+1}{n-k+1}\ge (\frac{l-k+1}{n-k+1})^k$$
Whether this is large enough or not depends on $$n,k,l$$.
If the attacker does not know $$k$$, the best he can do is to choose $$l=n-1$$, which gives him the highest probability of not being detected.