LESSWRONG
LW

[ Question ]

Can preference falsification be reduced with Ring Signatures?

by mike_hawke2 min read29th Nov 202014 comments

13

Computer Security & CryptographyPracticalWorld Optimization
Frontpage

I get tons of emails from people, telling me they agree with me privately, but that they can't say so out loud for fear of retaliation.

-- various writers, podcasters, public thinkers, etc.

 

I know very little about cryptography...but shouldn't ring signatures be helpful for exactly this problem? Are there any issues that make them unsuitable, even in principle?

What practical hurdles are there to something like this working well? Should we expect ring signatures to never catch on, even/especially if preference obscurity gets worse than it is now?
What downsides would there be if it did end up happening?

 

Relevant wikipedia pages:

EDIT: It seems like folks are getting confused about how ring signatures work. The first three paragraphs on wikipedia are informative and should help clarify. At ChristianKI's feedback, I have copied and pasted all three of them. Please read. 

In cryptography, a ring signature is a type of digital signature that can be performed by any member of a group of users that each have keys. Therefore, a message signed with a ring signature is endorsed by someone in a particular group of people. One of the security properties of a ring signature is that it should be computationally infeasible to determine which of the group members' keys was used to produce the signature.
...
Suppose that a group of entities each have public/private key pairs, (P1, S1), (P2, S2), ..., (Pn, Sn). Party i can compute a ring signature σ on a message m, on input (m, Si, P1, ..., Pn). Anyone can check the validity of a ring signature given σ, m, and the public keys involved, P1, ..., Pn. If a ring signature is properly computed, it should pass the check. On the other hand, it should be hard for anyone to create a valid ring signature on any message for any group without knowing any of the private keys for that group.
...
In the original paper, Rivest, Shamir, and Tauman described ring signatures as a way to leak a secret. For instance, a ring signature could be used to provide an anonymous signature from "a high-ranking White House official", without revealing which official signed the message. Ring signatures are right for this application because the anonymity of a ring signature cannot be revoked, and because the group for a ring signature can be improvised.


 

Computer Security & Cryptography2Practical2World Optimization2
Frontpage

13

New Answer
Ask Related Question
New Comment

2 Answers

Viliam

Nov 29, 2020

3

What's missing here is the proposal how specifically you would want to address preference falsification using the ring signatures. I can only guess, and maybe what I guess is not what you had in mind.

If I am afraid that being associated with X may get me fired, I don't want to join a "ring" of people who will once in a while write about X. I might get fired simply for associating with the evil X-ers. Or maybe not fired, just... denied a promotion, or ostracized; punished in a plausibly deniable way. And if the partial anonymity would encourage other ring members to post more taboo topics, that only makes it worse for me.

It might be interesting if you could somehow create involuntary rings. Like, select 10 random people in a country, assigned them to the same ring. Then select 10 more, etc, until everyone is a member of one ring. Then, if someone publishes a horrible opinion using your ring, you can complain about the 9 assholes you don't know and you never met. But at the same time, if e.g. 50% of rings express certain opinion, we know that at least 5% of the population agrees with it.

But I doubt this would work either. First, what is the size of the rings? Too many, e.g. 3 people per ring, make it simple to punish everyone for what their ring publishes. Base probability 33% that they are guilty anyway, and with further clues you can increase it (for example, the other two are too dumb to express the complicated political opinion you wrote). Too much, e.g. 100 people per ring, then even if every ring writes that they endorse X, you can still claim that X is only endorsed by 1% of the population, and can be safely ignored.

Furthermore, most people don't understand technology, so they wouldn't know what to do with the private keys. Some people would publish their key, to protest against this method.

[-]mike_hawke1y 3

What do you mean when you say you don't want to "join a 'ring' of people" who say controversial stuff? That doesn't line up with the (admittedly weak) understanding of the protocol that I'm getting from wikipedia. Someone just assembles a list of public keys at their leisure, and uses all of them plus their own, to sign a message. The only way to not be implicated is to never have a publicly available key, right?

Reply
2Viliam1yUh, maybe I misunderstood it, but reading the Wikipedia article I got an impression that "ring signature" is a signature shared by group of people. Did I miss the point?
1simon1yYou need to have a private key to sign, otherwise it would be useless as a "signature". For signing (in the non-ring case), you encrypt with your private key and they decrypt with your public key, whereas in normal encryption (again, non-ring) you encrypt with their public key and they decrypt with their private key.

ChristianKl

Nov 30, 2020

0

When high-ranking White House officials are quoted in the media they usually aren't named because they aren't authorized to speak on the issue. 

We have laws against unauthorized disclosure and not laws that are designed to make unauthorized disclosure of secrets by White House officials easier. Ring signatures would be a tool that can be used if the powerful would want more unauthorized leaks but they don't. 

The same goes for corporations. No cooperation wants to make it more easy for it's employees to engage in unauthorized disclosure of information. 

That leaves the question what kind of organization might give their members ring signatures. Anonymous organizations can easily give out ring signatures but their signatures are worthless. "A member of XY anonymous said ..." isn't different then "A anonymous person said..." if  XY anonymous hasn't a reputation for selective membership. 

Some academic organizations might have values that are compatible with having their members being able to speak anonymously while being able to identify as members of the organization.

Practically, there's the risk of any member of the organization not being careful with their information security and thus allowing a third party to speak in the name of the organization. The possibility of a hacker from 4chan getting the credentials to speak in the name of Havard is likely enough that it's a tough sell. 

[-]mike_hawke1y 13

That leaves the question what kind of organization might give their members ring signatures.

A ring signature is computed from your own private key and whatever public keys you can find. It's not something your employer gives you. An employer could fire you for having a public key I guess, but that doesn't seem like a hard crux for what I'm asking about here.

 

Some academic organizations might have values that are compatible with having their members being able to speak anonymously while being able to identify as members of the organization.

Well, imagine being a professor at Harvard, and being able to publish a statement that says,

Skub is probably fine. Anti-skub activists are caught up in a moral panic.

Signed:
ChristianKI of Harvard University OR Alice Abramson of Amherst University OR Bob Benson of UC Berkeley OR Carol Cook of Cornell University OR...


Shouldn't this cause a marginal emboldenment of the not-anti-skub contingent at any of those universities? Any skub-tolerator who reads the statement could think, "well clearly I'm not the only one". If they read two such statements with no overlap of names, they could think "well, clearly there are at least three of us". I can immediately see practical issues wit this, but is there some strong theoretical argument for why this can't scale up to the point at which it substantially impacts the level of silence?

Reply
2ChristianKl1yOkay, I got it. It seems like your citation of Wikipedia is obfuscating as it doesn't describe what's required for calculating the ring signature when you suggest that it provides clarification. It seems a key question that's not answered in the Wikipedia page would be whether you can reuse existing private/public keypairs. If you can reuse existing private/public keypairs, this solution should be able to scale in communities that do publish keys for communicating in an encrypted way with each other.
7 comments, sorted by
top scoring
Highlighting new comments since Today at 5:09 AM
[-]Matt Goldenberg1y 17

It seems like there are easier things than ring signatures to test your theory, like creating a social media account and giving the password to 20 of your friends. Might be a fun thing to try and see what you learn

Reply
[-]ejacob1y 3

I've never heard of ring signatures before 60 seconds ago, but it seems like it would require a preexisting agreement among a group of people to create and use some way to 'endorse' messages with their signatures. If this understanding is correct, it doesn't solve the spiral of silence at all, since you'd have to get the same people that all of the emailers are afraid of to agree to it.

Reply
[-]crl8261y 4

Correct. Technology can only solve a problem people want solved. If people are being bullied into silence, the bullies aren't going to let this happen.  

Heck, they already have a way of silencing support for any new plan...

Reply
[-]mike_hawke1y 1

"At all"? Surely you exaggerate. 

What if all those emailers form an anonymity set with one another? Surely that does more than nothing for preference falsification. The more people in the set, and the more overlap among their struggles, the less preference obscurity there will be, right?

Reply
[-]ejacob1y 3

I think a precise way to explain why I felt like adding "at all" is because I had already restricted myself to thinking about the most extreme spiral-of-silence cases. The Evergreen State-Bret Weinstein fiasco is a salient example. These kinds of situations are where a solution to spiral of silence-type phenomena would have the greatest impact, but I suppose there could be cases where the group dynamic is not as hostile, but still unforgiving enough that people will essentially want to test out ideas in front of their peers before publicly endorsing them, as ring signatures allow. I don't know where such a group could be found or created.

I guess I am having difficulty imagining a group that would be heterodox enough to agree to talk about whatever "unpopular" ideas get endorsed on their ring signature, but would still be orthodox enough that individuals would feel the need to use the ring system in the first place - it seems to me like that would require holding contradictory beliefs about how one's peers would react if you expressed support for a "toxic" idea. I've noticed I have an easier time than most being that person though (and if I'm totally honest, it's a part of my personality that I like, and I probably consciously turn it up), so maybe this is a failure of imagination on my part.

Reply
[-]mike_hawke1y 10

I'm not sure I quite understand you, but I think you may be underestimating the protocol.

Wikipedia says:

In the original paper, Rivest, Shamir, and Tauman described ring signatures as a way to leak a secret. For instance, a ring signature could be used to provide an anonymous signature from "a high-ranking White House official", without revealing which official signed the message. Ring signatures are right for this application because the anonymity of a ring signature cannot be revoked, and because the group for a ring signature can be improvised.

It seems to me that this should straightforwardly generalize from the White House staff to Evergreen professors, Megacorp employees, etc. The only requirement is that there are enough public keys available that you can put together a decent crowd to hide in. If you know someone's public key, they cannot stop you from signing their name next to yours (which leaves both of you with plausible deniability).

If you run an organization, you can just require that all employees generate a key pair. Boom. Spiral-proof organization, right? The emperor of such an organization is less likely to end up walking around naked, right?

Reply
[-]crl8261y 0

If you run an organization

 

That's the thing, this is all based on the assumption that the people running an organization want people to express themselves. 

That is a very poor assumption in a lot of organizations. Silence spirals gotta start somewhere.

Reply