# Multiple private keys for single public key

I am currently working in security in mobile ad-hoc networks.

I have several clusters, and I want to send some data encrypted with its public key, from the cluster head to the cluster members. I assume that each member has its own private key so it can decrypt the data.

I ask about how to get a single public key and multiple private keys for this public key?

What is the solution for this case?

• that is not really how PKC works – Richie Frame Feb 25 '15 at 11:22
• I don't understand your comment,do you mean that what I need is not a public/private key cryptosystem or what? – yomna Feb 25 '15 at 11:34
• more like that you can only have 1 private key per public key – Richie Frame Feb 25 '15 at 11:36
• All private keys corresponding to a single public key would be equivalent anyway (i.e. an attacker could use any one of them to decrypt messages), so why would you bother? – yyyyyyy Feb 25 '15 at 11:47
• I suspect you need to think more about the security goals (and nongoals) of the system. The cluster head sends a message; who must be able to read the message (e.g. the intended recipient)? Who must not be able to read the message (e.g. random third parties)? Who don't you care whether they can or cannot (e.g. the cluster head itself)? Also, this is an ad hoc network; how do nodes join the cluster? Is there some sort of introduction protocol (where keys can be exchanged)? Depending on the answers, a purely symmetric system may be the Right Thing. – poncho Feb 25 '15 at 13:15

Public-key algorithms such as RSA or ECDSA have exactly one private key for each public key and vice versa.

Attribute-based Encryption

Attribute-based encryption works (a little bit) like that. You have only one public key which is used to create all ciphertexts and you select the users that should be able to decrypt the data based on a policy of attributes. The policy can be a boolean formula and the users have secret attribute keys that should satisfy the policy if they must be able to decrypt the ciphertext.

If you use only one attribute for all users and a trivial policy containing that attribute, you've got that system that you wanted, but now the problem becomes that the user attribute secret keys have to be generated by a central server and you will need multi-party computation to get rid of the key escrow.

Conventional

This is almost certainly too complicated for your case. You should use a symmetric algorithm like AES and a public key encryption algorithm like RSA in conjunction. You can simulate your intended system by encrypting the data with AES using a randomly generated key, then encrypt the AES key with all the RSA public keys of the intended recipients. Concatenate everything into one package and send it on its way.

Thoughts

Let's say multiple recipients have (a different) private key and all of them can decrypt data encrypted with the same public key. You should ask yourself, how can the different private keys be generated to arrive at the same public key, but where all the recipients wouldn't know the private key of each other.

• @Artijom B. You are right sir when you ask at the end of your comment. May be I had formulated the problem in a wrong way. Anyway, I just have started to read about ABE, but I don't haven't yet deep understanding for this topic. I will consider you suggestion, thank you for your valuable answer – yomna Feb 25 '15 at 13:57
• I don't think ABE is for you, because there are multiple problems with it. I clarified my answer. – Artjom B. Feb 25 '15 at 14:03
• Sorry, I don't understand "then encrypt the AES key with all the RSA public keys of the intended recipients". Do you mean each intended recipient will have different public key or what – yomna Feb 25 '15 at 14:17
• Yes, that is exactly what I mean. The data is encrypted once, but the key with which the data was encrypted is encrypted with every recipient's public key. – Artjom B. Feb 25 '15 at 14:19
• @IanWarburton Probably not, but that's a big question on its own. It is likely depending on the specifics like RSA padding and AES mode of operation. If you use an adaptively secure ABE scheme this is also highly unlikely. – Artjom B. Oct 24 '19 at 19:26

Fast Multiparty Threshold ECDSA with Fast Trustless Setup

There is a new breakthrough solution for public-key cryptosystems developed by NYU and Princeton University cryptographers (Gennaro et al.) recently announced that could solve the problem described in this question, called multiparty threshold-ECDSA (link is to their paper titled "Fast Multiparty Threshold ECDSA with Fast Trustless Setup").

The key derivation process of this protocol is more complex than its signing stages, using proofs that show pallier keys were generated correctly and that $${C_{key}}$$ is an encryption of $${x_{1}}$$, given $${R_{1}}$$ = $${x_{1}}$$ $${·}{G}$$.

Such a threshold scheme would allow multiple parties to each have a share of a secret (while the secret is not exactly a private key, but information that creates a signature) so that when a minimum number of said signatories come together and each produces their respective signatures, where the combination of those signatures have the same effect that a single ECDSA private key would have to control (decrypt) a public address on an elliptic curve such as SECP256k1 (and without an actual full private key ever being created during this process, supposedly). And although the title above refers to ECDSA, the protocol can be applied to Digital Signature Algorithms (DSA) over any group.

Note: This is not the same as the Shamir Secret Sharing Scheme where the actual private key would be reconstructed by the shares.

Here is an example of an open-source library implementation on Github of multiparty threshold ECDSA.

• You can do this trivially with schnorr sigs, but this doesnt answer the question. – Erik Aronesty Oct 16 at 19:19

Solution:

• N parties have N private keys.

• One party generates a new private key called the master private key, and it encrypts that for each of the other parties. The other parties store that encrypted payload.

• Each one can verifies that the public matches the private, and can sign that verification.
• A new master key can be rolled at any time, if, for example, one party is being removed.
• Conditions can be placed, like unanimity or majority, on the verification.
• Recipients can decrypt this and load it as a "wrapped private key" into their HSM (if that's a concern)
• The sender encrypts the data for the single master public key, and transmits it to the recipients.

• The recipients can, at the time of receipt, use the wrapped master private key to decrypt the sender's messages (this decrypts the master, and then decrypts the message)

In this scheme, there is only one public key. The N private keys are only used to decrypt the master private, which in turn is used to decrypt the messages.

AFAICT: Although this seems trivial, there is no difference between this and the original request.