Is there an asymmetric encryption protocol which provides arbitrarily many seemingly unrelated public keys for a single private key?

Question

I am looking for an encryption protocol with the following properties.

• Alice has a private key $x$. Using this private key, she chooses public key $p$ corresponding to this private key. She let's Bob know about this public key. Bob then uses this public key to encrypt a message to Alice.
• Later Alice wants to receive a message again. She creates public key $q$ using the same private key $x$. Bob then uses this public key to encrypt a message for Alice.
• Bob should not be able to deduce from $p$ & $q$ that the two public keys $p$ and $q$ were generated using the same private key $x$.
• Alice should not need to have more than 1 private key.
• The protocol should enable Alice to produce arbitrarily many public keys, if they are allowed to be arbitrarily long.

Does such a protocol exists?

Answer 1

Such a scheme can be created generically, as follows. Let $(Gen,Enc,Dec)$ be a public-key encryption scheme, and let $F$ be a pseudorandom function. Then, the "master" private key of the scheme is a symmetric key $k$ for the PRF. In order to generate a new public key, choose a random $\rho$ (or if you have state then use a counter) and compute randomness $r \leftarrow F_k(\rho)$. Then, use $r$ (and an appropriate pseudorandom generator, if needed) to generate a new key pair $(pk,sk) \leftarrow Gen(r)$. In order to ensure that it's possible to decrypt, you do need to know $r$ or $\rho$, so yo can make $\rho$ part of the public key. Alternatively, if you keep state, the decryptor can store all of the $\rho$'s or $r$'s, and then just try them all (using a method of redundancy and a CCA secure scheme in order to know when you succeed).

Answer 2

To supplement the generic answer, here's a concrete construction based on ElGamal.

ElGamal based on a group $G$ of order $p$ with generator $g$ has a public key $y = g^a$, where $a$ is the private key.

To create a new public key, choose a random number $s$ and compute $(u,v)$ as $u=g^s$ and $v=y^s$.

To encrypt $m$ with $(u,v)$, choose a random number $r$ and compute $(x,w)$ as $x=u^r$ and $w = v^r m$.

To decrypt $(x,w)$, compute $wx^{-a}$.

Under the DDH assumption, $(u,v)$ is indistinguishable from a random pair, so that is good. It is easy to show that the scheme is secure under DDH.

Exercise for the reader: It is useful to figure out why this scheme is essentially just ElGamal.

Extensions to more useful messages spaces is trivial using standard techniques.

This scheme (with some extra tricks) has been used to build theoretically better malware. (As far as I know, it has never been used to build actual malware.)