Comment by nullc

You can prove your signature is from a key which is in a member of an acceptable set without revealing which one. These schemes can also prevent excessive reuse, e.g. by you also proving that some linked value is a hashlike function of your private key, the date, and the domain, so if you sign multiple times for the same site in the same day your uses are linked, so someone can't just toss up an oracle that gives endless authentications.

Such systems are deployed in production by privacy preserving cryptocurrencies as its the same problem: Prove you're spending a coin that exists without revealing information about which one, and prove that you're not spending it multiple times.

Less private but easier to implement is just simple blind signing. Site asks you to give them a signature of their domain name, your account name, and date. You blind the data using a random number, go to google and identify yourself (e.g. solve a CAPTCHA, check your mobile device, age verify, whatever) and ask them to sign the blinded value-- they rate limit you and give you a signature. You unblind and provide to the site. Now the site knows you passed the google rate limit but nothing else, but google never learns what site you authenticated to.

The blindsigning approach is kinda lame because it requires active communication with a third party that learns you're online and authenticating to stuff. So I think it's generally less preferred but the cryptography is hardly any more complicated than an ordinary digital signature.