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)?