2
$\begingroup$

I'm trying to design a wallet, where any number of public keys can be handed out. Say Alice hands out the public keys to receive messages. She doesn't want others to be able to link all of the public keys to the same person. They should each look random, so that giving out N public keys causes a bystander to believe that there are N different people.

I know that this can be done by having a master private key $p_0$, and generate future private keys with something like $p_{i+1} = \text{Hash}(p_i, p_0)$. However, in order to decrypt the message, Alice would have to try every single private key. I'm doing this in a browser and JS Tests with ECC appear to show that it's a bit slow for a UI once you have a dozen or so keys, but doable if Alice can wait a second (Though not ideal). If you're trying to decrypt dozens of messages at a time, this quickly becomes impossible with too many private keys. And at least in my case, I will have to try to decrypt many messages.

What I really want, is to simply have one private key, and any number of desired public keys. Most cryptosystems have specific key-pairs. And while you can simply concatenate a group's Public Keys to get N Private Keys : 1 Public Key (Decryption requiring every individual), there doesn't appear to be well-known algorithm for 1 Private Key : N Public Keys.

The examples mentioned here did not help, because they are all too slow if decryption requires an ECC multiplication.

==

QA Format: I expected to find a solution on this SE, since it didn't seem like a complicated question, but couldn't. Anyway, I'm posing it here to help others / for those who are interested since I thought it was fairly neat.

Improve this question
$\endgroup$
9
  • $\begingroup$ Why do all the public keys need to be distinct? Wouldn't it be sufficient for it to be infeasible to, given two encrypted messages, determine whether they're encrypted with the same public key or two different ones? Alternatively, if you are worried that people might link the public keys (and hence they must be different), wouldn't it suffice to have the encrypted message just include the public key (and so the decryptor can do a fast lookup on the public key to find the corresponding private key)? $\endgroup$
    – poncho
    Nov 28, 2018 at 19:47
  • $\begingroup$ @poncho Including the public key in plaintext would immediately reveal the receiver. The receiver wishes to be anonymous. A baseline goal is that when Bob sends Alice a message, an eavesdropper can't know who sent the message and to whom. The additional goal that I want to achieve is that Alice can give Bob and Charlie two different public keys, so that Bob and Charlie cannot know they both represent Alice. This way she can browse several websites and give them each a unique public key, and they won't be able to link them together. $\endgroup$
    – Nicholas Pipitone
    Nov 29, 2018 at 0:23
  • $\begingroup$ The idea has been discussed before, but the leading solutions still involved an $O(n)$ lookup, which isn't ideal. In Bitcoin, addresses are public, so you can use a hashmap. But to have the same functionality in Monero, it'd take $n$ ECC multiplications. This solution averts that. $\endgroup$
    – Nicholas Pipitone
    Nov 29, 2018 at 0:29
  • $\begingroup$ A lookup of a table of $n$ items can be done in $O(1)$ expected time (e.g. using a hash table) $\endgroup$
    – poncho
    Nov 29, 2018 at 3:43
  • $\begingroup$ @poncho Yes, I mentioned in my comment that in Bitcoin you can use a hashmap since the addresses are public. In Monero you must compute an ECC multiplication to figure out if a transaction was meant for you, which is too slow to do for every key in your key ring. Verification is done by checking hash(aT), but iterating for all a is slow. The solution is to use a new generator for each public key, but keep the private key the same. Hashmaps dont work on encrypted input, only plaintext (Or, two encrypted values which are the same, but that ruins the point because now you can link them). $\endgroup$
    – Nicholas Pipitone
    Nov 29, 2018 at 19:07

2 Answers 2

Reset to default
5
$\begingroup$

Here's an idea:

  • Alice's private key is an AES key $k$, which Alice picks randomly. Yes, we're using an AES key as a private key; bear with me a moment...

  • To generate a new public key, Alice picks a random value $r$, and generates the pair $(\text{AES}_k(r), rG)$, which she publishes, and which I will refer to as $(b, H)$. Alice can optionally forget the value $r$ she picked. Alice can generate and publish as many public keys as she needs...

  • To encrypt a message $m$ with this public key $(b, H)$, Bob selects a random value $s$, computes the point $sG$ and the AES key $KDF(sH)$, and outputs the triplet $(b, sG, \text{AES}_{KDF(sH)}(m))$

  • To decrypt $(b, sG, \text{AES}_{KDF(sH)}(m))$, Alice first decrypts $\text{AES}_k^{-1}(b) = r$, (and if that decryption fails, the message wasn't meant for her). Then she computes $r(sG) = s(rG) = sH$, computes $KDF(sH)$, and then decrypts $\text{AES}_{KDF(sH)}(m))$, giving her the message $m$.

Two different public keys from Alice are unlinkable, as the only connection is that they contain the encryption of two different values with the same AES key, and that's indistinguishable from random.

And, all operations take time independent of the number of public keys Alice generates...

(Note: you'll use some authenticating encryption mode of AES, such as AES-GCM...)

Improve this answer
$\endgroup$
6
  • $\begingroup$ Hm, this is neat, but it looks like $b$ is being broadcasted by both Alice and Bob here. An eavesdropper could see the $b$'s in common and know the recipient. See "Including the public key in plaintext would immediately reveal the receiver" $\endgroup$
    – Nicholas Pipitone
    Nov 30, 2018 at 23:50
  • $\begingroup$ @NicholasPipitone: so, an additional requirement is that you cannot link the public key and the ciphertext, correct? $\endgroup$
    – poncho
    Nov 30, 2018 at 23:51
  • $\begingroup$ Indeed. An evesdropper should be able to deduce absolutely nothing. Basically imagine you're in an anonymous chat room, and want to have a conversation with someone. If everyone knows who you're talking to, you can use RSA/AES (Which is pretty similar to what your post is, but using ECC instead of RSA). I want a solution where no one knows who you're talking to either (To hide yourself, just keep making new fake accounts. The real-life analog is using a Tor browser). $\endgroup$
    – Nicholas Pipitone
    Nov 30, 2018 at 23:53
  • 1
    $\begingroup$ What is rG here? $\endgroup$
    – the_endian
    Aug 7, 2019 at 20:04
  • 1
    $\begingroup$ @the_endian: $r$ is the random value Alice picks, $G$ is the elliptic curve point which is the agreed-upon generator of the curve, and $rG$ is point multiplication of $r$ and $G$, that is, $\underbrace{G+G+G+...+G}_{r \text{ times}}$ $\endgroup$
    – poncho
    Aug 7, 2019 at 20:09
0
$\begingroup$

Define HashToPoint(Number) -> Point as a function that maps integers to an even distribution of ECC Points (Which is easily done by hashing to get an x coordinate, and incrementing x until you hit a point where $x^3+ax+b$ is a quadratic residue, and gives a Point with the desired order.)

Have Bob generate a master private key $a$.

To generate a new public key, generate a random integer $r$ (64-bit in my case), and calculate $A = a\text{HashToPoint}(r)$. Broadcast $(A, r)$.

To send to Alice's public key $(A, r)$, follow standard DH. Generate a random private key $t$, and calculate $T = t\text{HashToPoint}(r)$. Save $S = tA$ as the shared secret, and broadcast $(T, \text{Hash}(S))$.

Now, Alice can calculate $S = aT$ only once, and have the shared secret. She checks the hash against the broadcasted hash to know that it was sent to her (Or, she can simply notice that the attempted decryption gives random bytes). This formula works no matter what $(A_i, r_i)$ the sender used.

An eavesdropper cannot know who received the message, so the message contents and the receiver identity are secure.

Now the $O(n)$ receiving algorithm is $O(1)$, and sending remains $O(1)$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Note that this idea can be slightly simplified (if made a bit more chatty) by selecting a random point $H$ when you generate a fresh public key, and computing $A = aH$, and publish $(A, H)$. Then, to encrypt, Bob generates a random value $t$ and computes $T = tH$ and uses $S = tA$ as the shared secret. This avoids bolting in the $\text{HashToPoint}$ procedure into the protocol (Alice can still use it to select $H$), but it does make the public key a bit longer... $\endgroup$
    – poncho
    Aug 15, 2019 at 12:19

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.