1
$\begingroup$

Ring signatures allow one to prove that you own a private key corresponding to a public key from a set of keys, without revealing which private key you control.

This is useful if you are part of some group of people, and want to publish a message without revealing who are specifically, just that you are a member of the group.

The problem is that you need to have access to public keys corresponding to private keys that members of the group have sole control over. That is, if Alice is in the group, you must have a public key corresponding to a private key that only Alice knows.

The problem comes if Alice has not generated keys at all (say, because they simply do not use cryptography). Indeed, outside of crypto circles, it is actually somewhat rare for people to control their own private keys today.

Of course, you could try to somehow convince the members of the group to generate keys, but that would retroactively be seen as suspicious once you publish a ring signed message.

That being said, most people do have accounts on various websites. For example, most people reading this have a crypto.stackexchange.com.

When you log into a website, the website will return a response that includes the following:

  • Your username somewhere (usually in the HTML page itself.)
  • An authentication cookie (if you can prove it is legitimate (and not expired), it proves that whoever has the request controls the account associated with the username.)
  • A signature signing the request from the website, proving the above legitimate. You can use the website's public certificate to show that it is legitimate, although you may have to provide other requests if keys signed by other keys are involved.

Now for the actual question. Can you make a scheme similar to ring signatures, except, it uses website accounts instead of cryptographic keys?

For example, suppose I want to a signature for a message that proves the signer control either my crypto.stackexchange.com account, Trump's twitter account, or Zuckerberg's account. In particular, it would prove the following statement:

One of the following is true:

  • The signer possesses a request that looks like it is from crypto.stackexchange.com (i.e. matches a certain template). The request states that the currently logged in user is "PyRulez". It also contains a valid authentication cookie. It is also signed by crypto.stackexchange.com.
  • The signer possesses a request that looks like it is from twitter.com (i.e. matches a certain template). The request states that the currently logged in user is "@realDonaldTrump". It also contains a valid authentication cookie. It is also signed by twitter.com.
  • The signer possesses a request that looks like it is from facebook.com (i.e. matches a certain template). The request states that the currently logged in user is "zuck". It also contains a valid authentication cookie. It is also signed by facebook.com.

It would not reveal, however, anything else (except how to prove the above statement to someone else (i.e. by sending the signature to someone else)). In particular, it would not reveal which case is true. It also would not reveal things about log-in time or details of the authentication cookie.

The algorithm would also possess the following properties:

  • Completeness and Soundness: It is feasible to use the signature to prove the statement if it is true and infeasible to create a signature if it is false.
  • Integrity: The signature does not just prove that the person who created it controls one of the web accounts, but that the whoever signed the message does. In particular, if you modify the message, the receiver can tell the signature no longer corresponds to the message. (Messages should also be time-stamped to prevent replay attacks.)
  • Blind: It is infeasible to learn anything not implied by the statement from the signature. The signature can, however, be sent to other people (which would not be true if it was zero-knowledge).
  • Collusion resistant: If crypto.stackexchange.com, twitter.com, facebook.com, Donald Trump and Mark Zuckerberg colluded, and were willing to reveal secret information, they still could not break any of the above properties. In fact, even if they knew who signed it, they could not prove that knowledge to anyone else. (crypto.stackexchange.com could prove the statement, of course (by signing a forged request), but that would not violate soundness since the statement is technically true. More importantly, they could not violate any of the other properties either. For example, they could not tell whether one of their signatures was used as input to the algorithm.)

One possibility to consider is zero-knowledge proofs. The problem is that they are too zero-knowledge; the one receiving the proof could not in turn proof it to someone else.

Even if we weren't worried about that, the problem would still be hard. For example, the implementation would depend on the exact websites involved, and would need to be updated when the websites are updated. It might not even work for all websites (an answer should address what properties a website needs to have for this to work).

Additionally, the signature does not actually prove you are part of a group, just that you have secret knowledge that only someone in the group should have, or you control one the websites involved. As such, it is best used with important accounts (such as bank or email accounts) on secure and reputable websites.

Another problem is that if there is only one cryptographer in the group, it may be obvious who signed it. To solve that, this should not be done by hand, by rather software should be published to do create the signature. It should be as accessible as possible so that it would even be plausible for those with limited computer skills to have signed the message.

$\endgroup$
  • $\begingroup$ The closest thing is probably identity-based ring signature. It is a ring signature scheme and the public keys are arbitrary strings (e.g. website accounts, email addresss etc.). See for example here: eprint.iacr.org/2004/327 . Caveat: there is a master secret key controlled by a trusted third party, who generates user private keys from it for all users, as in (almost) all identity-based cryptosystems. $\endgroup$ – Changyu Dong Jan 15 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.