I'm a newbie at cryptography. Here is my question:

  1. Alice makes a list of people: Bob, Carol and Dan;
  2. Alice gives a unique secret key to every member on the list, so they can uniquely sign messages;
  3. Each member has no right to sign more than 1 message;
  4. Grace, an observer, needs to be able to check whether a certain message was signed by a member of Alice's list, but she must not know who signed it.

Here's an example:

  1. Alice owns a movie-reviewing forum, where famous reviewers (that are also rivals) can post their movie analysis;
  2. Right before the release date of a polemic movie directed by actual Yakuza members, Alice decides to hide the identity of users on her forum.
  3. Grace, however, a fan of Alice's website, is kind of annoyed by that decision. There has been dozens of anonymous reviews being posted on the forum, with authors claiming to be Alice's Certified Trusted Reviewers™. Grace understands why the identity of the actual curators cannot be revealed, but how could she check wether the author of a specific post is part of the original trusted reviewers list?
  • 2
    $\begingroup$ The only two ways I know to effectively prevent Dan from signing more than one message are (A) threat of physical/legal/economic retaliation (which are off-topic) should he do otherwise, and (B) Alice giving Dan a physical device (e.g. a Smart Card) designed to sign only once. Is it possible requirement 3 really means each member won't sign more than one message? Independently, in 2: "Alice gives a private key" is unusual. The more standard procedure is that participants generate their own private keys, and publish the matching public key (perhaps thru Alice), or/and get it certified by Alice. $\endgroup$
    – fgrieu
    Aug 5, 2021 at 6:04
  • 1
    $\begingroup$ I mean, Dan could publish his public key and if it's connected to his name in Alice's list, that would prove his relation with Alice (which is exactly what's intended), but then Grace would know that he is the author of that message. I've edited the question with a silly example, for clarification. About people only being able to sign once, imagine that there's an algorithm that process their messages. If a signed message is sent, then that signature is wasted: it couldn't be used to sign any other messages. $\endgroup$
    – thzoid
    Aug 5, 2021 at 6:12
  • 1
    $\begingroup$ Perhaps you want a ring signature with the additional feature that it can be recognized by an observer with the public keys if, in a collection of signed messages, there are two signed with the same private key? [addition: I neither know such cryptosystem, nor see a reason that it would be impossible] $\endgroup$
    – fgrieu
    Aug 5, 2021 at 6:32
  • 1
    $\begingroup$ Well, I can see that working in my scenario, because it wouldn't allow duplicate signing and if Alice listed the public keys used in the ring, that would prove the signers' relation with her. How does that work? Is there any paper on that? $\endgroup$
    – thzoid
    Aug 5, 2021 at 6:40
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – fgrieu
    Aug 5, 2021 at 13:09

1 Answer 1

  1. Each member has no right to sign more than 1 message;

As pointed out in the comments, any mechanism to prevent a group member from generating two signatures would require either trusted hardware or an interaction during the signing process with the group controller Alice (to prevent the signer from resetting his state after generating the first signature and then going ahead with a second signature).

So, what I'll translate this into "it is detectable if a member attempts to signs two messages", that is, given the two signatures, we can verify whether the same group member signed both of them.

With that translation, it is possible; here is one approach:

  • Alice generates a stateful hash based signature system (e.g. LMS or XMSS), with the various one-time signature keys being independent (that is, you can't reconstruct one from another one)

  • For each group member Bob, Carol and Dan, Alice selects a random leaf (one time signature), and gives that group member the index, the private key for the one time signature and the authentication path.

  • When Bob wants to sign his one message, he signs it with his private key, and outputs that signature (along with the index and the authentication path), generating a valid LMS or XMSS signature

  • The verifier performs the standard LMS/XMSS validity checking against the public key

If the signature verifies, the verifier knows that whoever generated the signature had a valid one-time signature key, and so it must have been a valid group member (or the group controller). And, since the indices were randomly assigned, he has no idea which one it was).

And, if Bob decides to sign two different messages, he has to include the same leaf index in both signatures (that index is the only one she knows how to sign with) - it is obvious that the two signatures have the same index. This remains true even if we had Bob and Carol (and possibly others) mutually cooperating - they can only generate signatures that has an index that one of those group members have.

This approach does have the cavaet that if Bob does sign two different messages, then someone else could possibly sign a third message (based on Bob's two signatures); the forged signature would look like it also came from Bob.

As written, this approach relies on the fact that a group member is allowed to sign only one message - it can be extended if a group member is allowed to sign N messages (by assigning each group member N consecutive leaf indicies and private keys).

  • $\begingroup$ That would work in the context I'm looking for. This logic is supposed to run on a blockchain, so if two transactions are signed by the same person, only the first one should be processed. The second one would become invalid within the chain context. Is there some specific paper or tutorial that you recommend for understanding LMS/XMSS? Thanks @poncho and everybody else for helping me to understand this. $\endgroup$
    – thzoid
    Aug 5, 2021 at 18:21
  • 1
    $\begingroup$ @thzoid: for LMS, there's datatracker.ietf.org/doc/rfc8554 and for XMSS, there's datatracker.ietf.org/doc/rfc8391 . $\endgroup$
    – poncho
    Aug 5, 2021 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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