Can randomness protect a list of signatures against forgery attacks?
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.