# Check if two anonymously signed messages have the same author

I need digital signature scheme with following rules:

1. Signature is "anonymous" which means it doesn't expose author identity (See papers in this answer. Anonymous RSA version or Boneh-Boyen algorithm satisfy this clause).
2. Author can create some anonymous signed message and then create another anonymous signed messages "related" to any previous signed message.
3. "Relation" means third party can make sure this second message have same author as its "related message".

For example:

1. Alice write message and sign it. For example it is volume of the book. Bob cannot determine this message belong to Alice even he has Alice's public key.
2. Alice write another message, which are for example second volume of her book and sign it. Bob also cannot determine this message belongs to Alice, but he can make sure this message have same author.
3. Alice write third message and sign it. This message is not related to previous, so Bob cannot determine nor author neither relationship with previous messages.

It uses two signature methods; the first one (the "inner signature") is conventional; the second one (the "outer signature") is anonymized.

When Alice generates a message $m$, she either generates a public/private key pair $Pub_a, Priv_a$ for the inner one, or reuses a $Pub_a, Priv_a$ pair that she previously generated. She then signs the message with the private key, generating $Sig_a(m)$, and forms the tuple $(Pub_a, Sig_a(m))$. When then interacts with server to anonymously generate the public signature of this tuple $Sig_s(Pub_a, Sig_a(m))$, and generate as a signature the tuple:

$$Sig_s(Pub_a, Sig_a(m)), Pub_a, Sig_a(m)$$

To validate this signature, one would verify that $Sig_s(Pub_a, Sig_a(m))$ is a valid signature for $Pub_a, Sig_a(m)$ (based on the Server's public key), and if $Sig_a(m)$ is a valid signature of the message (based on the public key $Pub_a$).

• It is anonymous; $Pub_a$ is a random public key, and so there's nothing to link it with Alice
• It is linkable; Alice can use the same $Pub_a, Priv_a$ to sign two related messages; anyone can see that those two signatures use the same $Pub_a$ value (and hence must be signed by the same person)
• Links are trustable; as no one else knows the value $Priv_a$, no one other than Alice can sign a message using $Pub_a$
• Looks suitable, so +1. But I can't get why we need $Sig_s. Jan 18 '17 at 16:45 • @marmalmad: I assumed that one of the requirements was that the server had to be involved; that (for example) we knew that the original signer was one of a set of people (that the server knew about), even if we do not know which one actually signed it. If that's not a requirement (that is, absolutely anyone can sign), then we can simplify this to$Pub_a, Sig_a(m)$(that is, pick a random signature key and sign away...) Jan 18 '17 at 16:55 • If someone want to prove authorship, he may sign message with text like "I am an author of$m$" with his personal (public key identify this person) key$Pub_p$,$Priv_p$, then sign$Sig_p(m)$with$Priv_a\$. Is there any pitfalls? Jan 18 '17 at 17:43