Asymmetric algorithm with indefinite number of public keys

So RSA algorithm uses pre-generated set of public and private key, and public key is usually included in private key. So public key stays always the same.

Is it theoretically possible to have some algorithm that has one private key and indefinite number of public keys that can be generated on-demand?

Assume we have goals

1. Decrypt/verify data signed with single private key by using any of public keys
2. Encrypt data using any of public keys and decrypt with single private key
3. Probably also same stuff vice versa (multiple private keys, single public key)

Can any of these goals can be achieved theoretically? PGP and RSA just generates constant set of keys from what I seen just now.

CA is also not an answer to my question because CA equals having single public key of root certificate, not indefinite amount.

• Related question Nov 14 '19 at 16:22
• A certificate chain is a solution. Nov 14 '19 at 17:37
• What security properties would you have? If an RSA private key is $(n, d)$, then we could invent a cryptosystem called RSA* and from an RSA private key $(n, d)$ generate arbitrarily many RSA* private keys $(n, d, 0),$ $(n, d, 1),$ $(n, d, 2),$ etc.; then we use them just like RSA private keys by ignoring the extra number. But maybe you were looking for something that does more than that? Nov 14 '19 at 20:52
• If you just create one key pair and one signed certificate per message then I don't see why the normal PKI doesn't work. Signature generation requires a trusted public key, so having any public key performing the verification doesn't work. Not having any identifiable information at the verifier is probably not possible, if that's your question. As for including (3), that makes the question both badly defined (when it comes to goals & requirements) and too broad. Nov 14 '19 at 22:44
• Asymmetric key derivation schemes like in Bitcoin hierarchical deterministic wallets can be used, wherein you can mix arbitary numbers into existing elliptic curve public keys to derive new ones, for which the private key owner can also derive the corresponding new private key for that keypair by mixing this number into their own private key in a similar manner (elliptic curve point addition / multiplication). This scheme still has different private keys for each public key, but this isn't a problem since you can derive the correct new keypairs from the original one. Nov 14 '19 at 22:59

Using tricks

As said by Natanael in his comment to your question: this is maybe possible when using elliptic curve cryptography, and is actually kind of used in Bitcoin to have the so-called "hierarchical deterministic wallets". If you want a rough idea of how this kind of child key derivation works, I refer you to this answer.

While it might also be possible to tweak RSA in order to do it, RSA is considered relatively brittle and I'll avoid venturing into modifying it today. (Maybe another day ;))

The same idea as the one used for ECDSA signatures should be easy to transpose to ECIES. But please, notice that having multiple public keys might not necessarily help you achieve whatever security goals you have, and without knowing these, my answer might be misleading you! So, please think hard about what kind of security guarantees you'd like to have and double check you're actually going to reach them using any derivation scheme one might present you.

Also, notice the caveat: in the child-key derivation discussed in the linked answer, knowledge of $$r$$ allows one to compute the "main" public key $$P_k$$... And when Alice is sending Bob her encrypted message, if she wants Bob to derive the right private key, she needs to send him $$r$$ along with her ciphertext.

Using an established scheme

There is actually a scheme which is doing almost what you're asking already, and that's namely ECIES, because when using ECIES, Alice is computing a "shared secret key" from Bob's public key $$P = g^x$$ by picking a random $$y$$ and computing $$P^y = g^{xy}$$, but Alice only needs to send Bob $$g^y$$ along with the ciphertext encrypted using $$g^{xy}$$.

Notice that ECIES is just kind of using Diffie-Hellman to agree on a shared secret key to encrypt stuff. But it works.

You want to:

1. Decrypt/verify data signed with single private key by using any of public keys

For the "verification" part, this is entirely covered by BIP-32, and it definitively possible and used in practice in Bitcoin and many cryptocurrencies. For the "decryption" part, it depends really on what you really want to be able to do. You might simply use ECIES, and then you'll be using "fresh keys" only Bob and Alice can recompute to encrypt your data. You might try to do other things...

1. Encrypt data using any of public keys and decrypt with single private key

This seems difficult, without having some kind of "hidden key negotiation" à la ECIES, because for most "straight forward" schemes it might mean one would have a mean to decrypt stuff sent to any public key... Which is obviously not the goal.

1. Probably also same stuff vice versa (multiple private keys, single public key)

Well, that sounds more like a key sharing. You could achieve this using Shamir's Secret Sharing, for example... But then if you want any of the private key to be able to decrypt the stuff, it means having a polynomial of degree 1, which is equivalent to just sending the main secret key to everybody, so not really a desirable feature. I'm not aware of clever tricks to achieve this, I'm afraid.

I'm not sure to understand your question.

If you're asking about unbounded number of public keys, you have to notice that it implies unbounded size for public keys (by a cardinality argument).

If you are speaking about exponential number of public keys: you can do it artificially achieve this by adding to your standard and unique public key, a long string (let say of size $$\lambda$$ the security parameter) completely usefulness and ignored in the encryption. Then if you don't require any stronger property, it's trivially achieve.

• what do you mean by unbounded size for public keys? As for second proposal it does not change situation at all, it just changes key a bit visually for humans. Nov 14 '19 at 16:48
• It means that necessarily for any $l$, it exists a public key of size at least $l$. Nov 14 '19 at 16:51
• @crypt2orsaq How do you define formally if two public key are the same? Nov 14 '19 at 16:52
• @levgeni in this case can such keys be generated from private key with some algorithm? I mean if I understand correctly every next private key will be bigger size than private key Nov 14 '19 at 16:55
• @levgeni if speaking about RSA, then Modulus and Exponent, if they are same then two public keys are identical. If any of both are different but they act with private key just fine then thats what I am asking. Nov 14 '19 at 16:56