Score:3

Is it theoretically possible to delegate public key generation?

in flag

Imagine the following scenario:

In a given cryptocurrency, privacy should be as high as possible.
For this purpose, a new account with a new address is created for every incoming transaction (the address is the public key of a private/public key pair). However, users are not always online to generate new accounts with new addresses as soon as someone wants to send them money. Therefore, all users should be able to create new accounts with new addresses for other users when they want to send money to someone. Of course, only the recipient should be able to spend money transferred to accounts created for him by other people.

All of this is supposed to be based on ECC, i.e. an extension of the ECDSA algorithm, so to speak.
But as just described in the cryptocurrency example, only the person for whom a public key was generated is allowed to sign messages for this public key or decrypt data that was encrypted with this public key.

Since the security of the used cryptographic algorithm is crucial for a cryptocurrency, only by NIST and SECG pre-made and standardized curve parameters which are known to be secure and efficient will be used.

The only technical changes to be considered are as follows:

Note: Since the address of an account will be the corresponding public key of a key pair, the term "address" and "public key" will be used interchangeably in the following.

Parameters from the ECDSA algorithm:

  • $d$ = randomly generated private key
  • $G$ = base point of the elliptic curve

Changes:

  • The available interval for private keys is reduced from $[1, n - 1]$ to $[1, \frac{n}{2} - 1]$
  • As with public key generation, a point $P$ is calculated as follows: $P = d \times G$. This point $P$ forms the so-called delegated address generation key (DAG Key).
  • To generate an address (public key) for another person, a random so-called address randomization key (AR Key) ($i$) with the same interval as that of the private key ($[1, \frac{n}{2} - 1]$) must be generated
  • To generate an address for an arbitrary person, the DAG key ($P$) of this person is added with the multiplication of the AR key ($i$) and the base point ($G$): $Q = P + i \times G$. Since $P$ is $d \times G$, the following must hold: $Q = P + i \times G = (d + i) \times G$. This point $Q$ forms the new address for the person whose DAG key was used for the calculation.

Example:

  1. Alice creates a randomly generated private key ($d$).
  2. Alice uses her private key to generate the DAG key ($P$)
  3. Alice makes the DAG key publicly available
  4. Bob wants to generate an address (a public key) for Alice and gets the DAG key from Alice to do so
  5. Bob creates a randomly generated AR key
  6. Bob generates a new address for Alice using Alice's DAG key and the AR key generated in the previous step
  7. Bob sends an amount to the newly created address
  8. Bob sends the AR key to Alice
  9. Only Alice can send money from this address, because she is the only one who can create valid signatures for the newly created address (the public key). To do this, she simply needs to calculate the private key to this address as follows: $d + i$ (addition of her private key $d$ and the AR key $i$ created by Bob).

Questions:

Is it even theoretically possible to delegate public key generation?

If so, would such a change to the standard ECDSA algorithm be feasible? In other words, to create public keys for other people without knowing or revealing the private key to that public key?

Or is there a better approach to solve this problem?

meshcollider avatar
gb flag
BIP-32 and other hierarchical deterministic address generation schemes allow public key generation delegation.
in flag
Thanks @meshcollider I'll have a look into it. Do you know if it works similar to how I proposed it?
meshcollider avatar
gb flag
Kind of similar, yes. Main differences would be that it's deterministic (uses a hash function to choose what you call AR so Alice can generate it alone), and you don't need to restrict the range of the private keys (the group is cyclic so if you add large keys it will "wrap around" modulo the group order)
in flag
Makes total sense! That's really cool. Thank you so much @meshcollider, that helps me a lot! And yes, I had no clue how I should name these "keys".
Score:3
es flag

If I understand your scheme correctly, then Alice needs a separate secure channel to communicate $i$ to Bob.

Monero solves this problem by creating a one-time destination public key every time funds are sent to someone. Those funds are spent with a signature using the corresponding one-time private key which can only be determined by the recipient.

The recipient has two key pairs: $(a, A=aG)$ and $(b, B=bG)$, where $G$ is a well-known base point.

The sender creates an ephemeral key pair $(r, R=rG)$ and publishes $R$.

The one-time destination public key is $H(rA)G+B$, where $H$ is a cryptographically secure hash that returns a scalar value.

The corresponding private key is recoverable only by the recipient as $H(aR)+b$.

The reason for the recipient having two key pairs is to require only the private key $a$ to be necessary for scanning for incoming funds, and to only additionally require the second private key $b$ when the funds need to be spent. However, if you did not need this distinction, the recipient could just have one key pair $(a,A)$ and then the one-time destination public key would be $H(rA)G+A$ and the corresponding private key would be $H(aR)+a$.

You can read about Monero's implementation of one-time addresses in section 4.2 here and page 7 of the original CryptoNote whitepaper here.

kelalaka avatar
in flag
The irony is that once the incoming fund has arrived at $A$ you need to transfer it to your spending $B$.
knaccc avatar
es flag
@kelalaka In Monero, nothing is transferred from $A$ to $B$. A single wallet address is the concatenation of the public keys $A$ and $B$. The funds are spent directly by referencing the one-time public key in a ring signature. I just meant to indicate that you only need $a$ and $B$ to scan for incoming funds, and only at the time of spending do you need to additionally know $b$. This allows access to $b$ to be tightly restricted, as it only needs to be known when funds need to be spent.
kelalaka avatar
in flag
Yes, I'm aware of your indication. Can you provide the link to read it from Monero?
knaccc avatar
es flag
@kelalaka Sure, it's Section "4.2 One-time addresses" here: https://www.getmonero.org/library/Zero-to-Monero-2-0-0.pdf In my notation, $a$ is the private view key, and $b$ is the private spend key
knaccc avatar
es flag
@kelalaka thanks, added
knaccc avatar
es flag
@kelalaka I've added a link to a copy of that paper, since the cryptonote.org link fails when I try to click it. Note that the CryptoNote paper has an error in it, since it defines $H_s()$ as producing a field element, when it should instead produce a scalar less than the group size of the base point.
in flag
@knaccc Wow, that is brilliant! Exactly what I was looking for and much better than what I came up with. Thanks a lot! The only thing I haven't understood yet: Why do I need to include (the cryptographically secure hash) when generating the keys? And what needs to be hashed to get ?
knaccc avatar
es flag
@E.Bramtergan $H(rA)$ means to do elliptic curve point scalar multiplication of $r$ with $A$, treat the result as a byte sequence and apply a hash (such as SHA-512/256) in the regular way, and then do $mod\ \ell$ to the result, where $\ell$ is the order of the base point and will depend on the curve you choose. The reason you need $H()$ is to convert the Diffie-Hellman shared secret $rA==aR$ into a scalar, so it can be used as a private key in the equation. The Monero papers I've linked explains all of this in much more detail.
in flag
@knaccc I see. Really nice, love it. Thanks again!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.