Crossposted from LessWrong. None of this post was generated by an AI, I wrote all of it myself except where otherwise indicated.
I’ll start with a quick refresher on asymmetric key cryptography. (Alternatively, here is a 6-minute Rob Miles video covering the same basics.)
You generate a random number out of a very large range of possible numbers, and that’s your private key (AKA your secret key). A cryptographic function is run on your private key to produce another number, which will be your public key (AKA shared key). It is supposed to be impossible or at least impractical for adversaries to reverse-engineer your private key from your public key.
You take your private key and a message you want to sign, run the signing function on both of them together, and the result is that same message plus a long string of random-looking characters. That’s the signed message, and anyone who knows your public key can mathematically prove that the message must have been signed by the secret key corresponding to your public key. Your secret key is not revealed at any point. (Separately, someone can also encrypt a message using your public key, and it can only be decrypted with your secret key.)
There are other types of signing schemes that serve different use cases. The one I want to tell you about is called a ring signature and it was first described in a 2001 cryptography paper by Rivest, Shamir, and Tauman, called “How to Leak a Secret.”
The paper begins:
The general notion of a group signature scheme was introduced in 1991 by Chaum and van Heyst. In such a scheme, a trusted group manager predefines certain groups of users and distributes specially designed keys to their members. Individual members can then use these keys to anonymously sign messages on behalf of their group. The signatures produced by different group members look indistinguishable to their verifiers, but not to the group manager who can revoke the anonymity of misbehaving signers. In this paper we formalize the related notion of ring signature schemes. These are simplified group signature schemes which have only users and no managers (we call such signatures “ring signatures” instead of “group signatures” since rings are geometric regions with uniform periphery and no center). Group signatures are useful when the members want to cooperate, while ring signatures are useful when the members do not want to cooperate.
[Emphasis added. Let emphasize further: if you take nothing else from this post, at least understand this major difference between group signatures and ring signatures. Unlike group signatures, ring signatures are imposed unilaterally and irrevocably on unconsenting peers by an unknown author. Even security professionals that I’ve talked to lose track of this distinction.]
In the paper, the authors give a vignette about Bob, a member of the cabinet of Lower Kryptonia, who alleges to a journalist that the prime minister has committed some kind of misconduct. If Bob sends the allegations as an anonymous tip, the journalist may have no reason to find the allegations credible. Whereas if Bob signs the allegation with a normal digital signature, the allegation carries his full authority...but then allies of the Prime Minister might use bribes, hacks, or threats to get Bob’s name from the journalist in order to retaliate.
Instead, Bob ring-signs the allegations, using his own private key plus the public keys of several other cabinet members, and then gives that ring-signed message to the journalist via some anonymous channel. The journalist then has good reason to believe that the information did come from a cabinet member, but it's anyone's guess which one it was, there is no known way to cryptographically prove it. To summarize the benefit in a single sentence, I would say that ring signatures allow a user to make fine-grained trades between their anonymity and their credibility, instead of settling for all of one or all of the other.
The reason Bob’s exact scenario hasn’t played out in the real world is that we all ended up relying on services like Gmail and Facebook to manage our account security for us instead of handling our own keys. That’s why you can usually just click “Forgot password?” if you lock yourself out of one of your accounts. This paradigm is safe and convenient in a narrow sense, but it has plenty of downsides, including, in my opinion, closing the door on clever arrangements like ring signatures.
(Adapted from the paper)
Q: Why would I want to join someone’s ring? What’s in it for me?
A: Remember, rings are created unilaterally. You cannot join someone else’s ring. Every non-signer's signature is forged, only the true signer's is contributed voluntarily. The only way to guarantee that you won’t be implicated in a ring signature someday is to refrain from using services that require you to share a public key.
Q: Can't a reader infer the true signer based on the content of the message?
A: Yes. If Bob has been complaining too often about the prime minister’s secret malfeasance, and then he anonymously makes allegations inside a ring-signed message, then the PM will identify Bob as the top suspect and may retaliate accordingly. (Of course, the PM may instead suspect that a different cabinet member is trying to frame Bob. It’s hard to contrive a truly straightforward threat model even in a thought experiment, but hopefully you get the point.) Also, the true signer may potentially be inferred by subtle quirks of writing style.
Q: Can’t this be used to start petty interpersonal drama?
A: Yes. But it can also be used to prevent or resolve interpersonal drama. Importantly, people do not always agree on which interpersonal conflicts are petty drama and which are serious problems.
Q: Didn’t Bostrom, Douglas, and Sandberg curse unilateral actions? And since creating a ring is done without permission, won’t it be subject to that curse?
A: Presumably yes, but the scheme tends to promote transparency and honesty, so it should cause net counterfactual harms only in situations where both (1) increased transparency and honesty are harmful, and (2) fully anonymous messages cannot already cause those same harms. The worst I can think of is a rogue employee deciding to leak secrets that are costly to verify. For example, a complex and expensive secret formula that, if posted fully anonymously, would not be worth the ingredient cost for a competitor to test out. (I can imagine ways employers could mitigate this risk without also undercutting whistleblowers, but that gets even more speculative, so I’ll omit them here.)
Q: Can I make a ring signature that has more than one true signer?
A: Theoretically yes, that is called a k-of-n threshold ring signature. Those would be very useful if there was a safe and convenient way to create them. Unfortunately, it seems that they intrinsically carry additional risks unless the true signers all coordinate. I’m not aware of threshold ring signatures being used for any real-world application.
Q: Is there a way to make it so that readers know that two different messages signed with the same ring came from the same person in that ring?
A: Yes, there are at least two ways. The easier option is to have the message itself contain an endorsement of a pseudonymous social media account and then just send subsequent messages from that account. The harder option is to read up on “linked ring signature” schemes and try to implement it without risking your anonymity, which is nontrivial. Linked ring signatures can also be used for secret ballots, but the setup requirements for that strike me as inelegant and risky. For example, I think an attacker could force you to send them a message ring-linked to your vote in order to find out how you voted. This is related to why threshold ring signatures require coordination. I’ll be surprised if there’s not a better scheme out there for secret ballots.
Q: What else are ring signatures good for?
A: An obscure application is deniable private messages. Alice wants to send messages to Bob, and she wants Bob to know for sure that she is the author, but she wants Bob to be unable to prove her authorship to third parties. Maybe they're doing sensitive negotiations, or maybe she just doesn't want to keep prepending the "This is Not Investment Advice" disclaimer. So she sends the message from an anonymous account and signs it with a ring comprising herself and Bob.
In the next post I’ll explain the current state of ring signatures, and what tools are available now for those who are interested.
