# Asymmetric cipher with multiple public keys

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?

• Why can't all the verifiers receive the same public key? Do you need it to be difficult to tell whether two public keys correspond to the same private key? It would seem that being able to verify the same message would give it away. If you sign a message and then generate more public keys, do the new public keys need to be able to verify the signature? – Gilles 'SO- stop being evil' Apr 24 '15 at 20:24
• I’m very very sorry that I did not make proper description of my task. I fixed post below. – Victor Mezrin Apr 25 '15 at 0:06
• – user991 Apr 25 '15 at 0:16
• So what is the point of the signatures, then? They don't seem to provide any sort of integrity or authenticity; a signature which can only be verified by the accompanying public key is worthless (the point of a signature is to prove that a message was sent by the owner of a known public key). Unless you want to prove that some sender sent the message? – cpast Apr 25 '15 at 0:18
• @cpast that is how signatures usually work, but the OP is wondering if public-key technology can be used to solve a different problem, and that's fine. – Mike Ounsworth Apr 27 '15 at 15:03

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.

• @RickyDemer Why ask me here and not there? Anyway: so what? I only changed the title and the tags. I shrunk the very long title to the main point of the question, which is that it isn't enough to specify the password and “AES” in order to have compatible tools. If the IV was the only variable, all tools would be compatible in practice since they pretty much always prepend the IV to the ciphertext. – Gilles 'SO- stop being evil' May 27 '15 at 23:24
• (I didn't notice that you had also answered there, and) I don't know whether a ping would work for a user who had edited the question but not done anything else on a page. $\;$ – user991 May 28 '15 at 0:29