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)?
If $l&lt;k$, 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.