Asymmetric cipher with multiple public keys

Question

Asymmetric cryptography is well known. You generate a private key. Using the private key you generate a public key. Then you can sign a message with the private key and check signatures using the public key.

I have different process which is as follows

On the one side are a lot of people that create messages (senders). Each sender has only one private key which used to sign his messages. Each sender knows only his own private key. Each sender makes many signed messages. Each message contains public key which can be used to check signature of that message. Message can be verified only by the key that inside in the message.

On the other side are o lot of people that read messages (readers). Each reader can read all messages of all senders.

Our goal - no one among readers should be able to conclude for any two messages whether they created by the same sender or by different senders.

So generally we need an asymmetric cipher which allow to generate many public keys for one private key.

Do you know such asymmetric ciphers? Maybe we can use combination of known ciphers to achieve this result?

Answer 1

Merely receiving a message and seeing that it has a valid signature does not provide any useful information. You also need to know who made the signature, or at least to have some information about them. If you don't know anything about who made the signature, then an adversary can generate their own message using whatever key they like.

In your scenario, there is apparently a group of trusted people. You want these people to be able to sign messages such that:

• a recipient can verify that the message is a genuine message from a member of the group (as opposed to a message modified crafted by someone outside the group);
• ordinary recipients do not know which member of the group produced a given message.

With just these conditions, you could make all senders use the same private key. However this would usually be a bad idea because it precludes many desirable properties, such as the ability for certain participants to tell who produced a given message, the ability to revoke the credentials of a participant who's defected, etc.

A common, relatively simple way to build such a system is to allow each participant to generate as many private keys as they like (possibly one for each message), and send the corresponding public keys to a certification authority (CA). The CA can choose what information it puts in the certificate. CAs for websites put the website name in the certificate, because that's what website certificates are for. A CA in your scenario would not put any identification in the certificates. The CA is thus an anonymity broker: it knows who is who but doesn't tell.

This scenario occurs with TPM: a TPM needs to be able to generate keys which cannot be tied to a specific TPM, but can be used to identify it with a particular service. What I described above is how multiple identities for TPM version 1 works. TPM 2 adds another method: direct anonymous attestations (DAA). I'm afraid that explaining the mathematics of DAA is beyond me. DAA may be a solution for you.