1
$\begingroup$

Let's say there are 3 people A, B, C. Everybody knows their public keys. They sign documents/messages and normally we can know who signed which by checking with their public keys.

Is there any way to check these signatures without knowing who signed which? I just want to know these messages is signed with one of these people.

This method may involve making them sign known messages or making some preparation before the signing process. I am just trying to be sure, if the message is sent one of these people with electronic signature without knowing the identity of the sender.

$\endgroup$
  • $\begingroup$ Are you looking for Anonymous Signature Schemes? Does this Anonymous trust/reputation system help you $\endgroup$ – kelalaka Jan 13 at 11:12
  • $\begingroup$ You can use threshold signatures as M-of-N, i.e. M out of N parties have to sign and M <= N. In your case M will be 1 and N will be 3. One such scheme is BLS signature, $\endgroup$ – lovesh Jan 13 at 11:23
  • $\begingroup$ Thanks for answer @kelalaka, but if I am not wrong, I guess in Anonymous trust, organization would be able to know whom credential belong when it is served as a public proof. That's why I think this is not I am looking for. $\endgroup$ – Bilal Gultekin Jan 13 at 12:06
1
$\begingroup$

There is more than 1 way to do it. You can use Group signatures or Ring signature which allow anyone in a predefined collection to sign a message on behalf of a group. Group signatures require a group manager who creates the group and can de-anonymise the signer. Ring signatures do not have such an entity and the signer cannot be de-anonymised. There are variations of ring signatures like the linkable ring signature where the signer cannot be de-anonymised but signatures by a signer can be linked, i.e looking at 2 signatures $s1$ and $s2$, it can be determined if the same signer created them or not. More in the wikipedia article.

You can also use threshold signatures as M-of-N, i.e. M out of N parties have to sign and M <= N. In your case M will be 1 and N will be 3. One such scheme is BLS signature, section 5.3

$\endgroup$
  • $\begingroup$ I think Ring Signature works for what I want, thanks! $\endgroup$ – Bilal Gultekin Jan 15 at 19:17
  • $\begingroup$ @BilalGultekin You are welcome $\endgroup$ – lovesh Jan 16 at 7:24
1
$\begingroup$

It is possible with a group signature scheme. The idea of group signature was proposed by David Chaum and Eugene van Heyst exactly for the scenario you described.

Citing from the abstract:

In this paper we present a new type of signature for a group of persons, called a group signature, which has the following properties:

  • only members of the group can sign messages;
  • the receiver can verify that it is a valid group signature, but cannot discover which group member made it;
  • if necessary, the signature can be “opened”, so that the person who signed the message is revealed.

In Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions (Mihir Bellare, Daniele Micciancio, Bogdan Warinschi, Eurocrypt 03), a model was proposed with formal definitions of full anonymity and full traceability. Full anonymity means that signatures should not leak the identities of their signers, whereas full traceability means that no collusion of malicious users can produce a valid signature that cannot be traced to one of them. Later a formal model for dynamic group signature was defined in Foundations of Group Signatures: The Case of Dynamic Groups (Mihir Bellare, Haixia Shi, Chong Zhang, CT-RSA 05).

There are schemes based on random oracle model (e.g. Short Group Signatures, Dan Boneh, Xavier Boyen, Hovav Shacham, Crypto 2004) and in the standard model (e.g. Fully Anonymous Group Signatures without Random Oracles, Jens Groth, Asiacrypt 2007). Another desirable property is compactness, i.e. the signature size should be small with regard to the group size (logarithm or even constant) e.g. as in Groth's scheme.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.