I did not understand how badges would help here.

I'm pretty sure there is some fancy crypto way to generate a signature with one out of 1000 keys such that the verifier cannot know which of the 1000 did the signature. I'm not so sure if that would work without the participation of the other 999 private keys.