Yes, you need a guess for a subset of transactions carrying the gring signal. I think it’s possible to design schemes that permit a smallish subset of incorrect values at the cost of more correct values and more complex decoding algorithm, but if you’re talking a huge set of signatures, this won’t help you find ones carrying the signal efficiently.
But yes, it’s dangerous to assume the attacker cannot infer or at least make good guesses about which transactions might carry the relevant signatures.