15
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ for an actual implementation, check the Electrum bitcoin client, it create a single private key that can be used to create any number of public bitcoin keys/wallets/addresses $\endgroup$
    – hanshenrik
    Jul 2, 2021 at 13:58
  • 2
    $\begingroup$ BIP32 does this. See also crypto.stackexchange.com/q/22274/21238 $\endgroup$
    – Ajedi32
    Jul 2, 2021 at 15:37

2 Answers 2

15
$\begingroup$

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).

$\endgroup$
6
  • $\begingroup$ $\rho$ may need to be part of the public key for the corresponding private key to be quickly identified. $\endgroup$
    – DannyNiu
    Jul 1, 2021 at 8:49
  • $\begingroup$ @DannyNiu Indeed, I wrote this in the answer. $\endgroup$ Jul 1, 2021 at 9:18
  • $\begingroup$ Incidentally, this scheme works for symmetric encryption, too, subject to the usual differences between symmetric and asymmetric encryption. A and B would need to have pre-shared the base key, but anyone in the middle wouldn't be able to tell whether any two messages used the same base. $\endgroup$
    – Bobson
    Jul 1, 2021 at 19:07
  • $\begingroup$ For common symmetric cryptosystems, it is usually already difficult to distinguish ciphertexts from randomness, so they already satisfy this. $\endgroup$
    – K.G.
    Jul 1, 2021 at 21:39
  • $\begingroup$ Would sharing $r$ in the public-key be safe? Seems like it ought to be $\rho .$ $\endgroup$
    – Nat
    Jul 2, 2021 at 7:32
5
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.