Check if two anonymously signed messages have the same author

Question

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.

Answer 1

Ok, here's a simple method that appears to address your requirements.

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$).

As for your requirements:

• 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$