0
$\begingroup$

The background:

  • We assume that coin ownership and payments are recorded on a public ledger.
  • Suppose Alice wants to publish some information to let her receive coins from anyone.
  • But she does not want to receive coins at a publicly known fixed address.
  • Instead, she wants the payer to generate a unique destination address each time.
  • The payer must not know the private key for the address; only Alice will know it.

I want to know if the following algorithm will achieve these goals. This combines Diffie-Hellman key exchange plus any digital signature algorithm. Are there subtle flaws that I am missing?

  1. Suppose we use an elliptic curve for Diffie-Hellman, and $G$ is a publicly agreed base point.
  2. Alice chooses a secret integer $a$.
  3. Alice computes the public point. $A = a×G$
  4. Alice publishes the statement "Alice will receive payments derived from the number $A$".
  5. Alice will not change this statement for a long time (years, many payments).
  6. Bob wants to pay Alice, so he retrieves Alice's value $A$ and will derive a new public key.
  7. Bob chooses a secret integer $b$.
  8. Bob computes the public point $B = b×G$.
  9. Bob computes the shared secret integer $s = \text{hash}(b × A) = \text{hash}(b × a × G)$.
  10. Bob computes the public key $K = A + s×G = a×G + s×G = (a + s) × G$.
  11. Bob sends his payment to the address $K$, and also mentions the point $B$ within the payment message (recorded on the public ledger).
  12. Bob tells Alice out of band, without using the public ledger, about the payment info $(K, B)$. This step doesn't need to be secure, but should be kept off the permanent public record.
  13. Alice computes the shared secret integer $s = \text{hash}(a × B) = \text{hash}(a × b × G)$.
  14. Alice computes the private key $k = a + s$, which corresponds to the public key $K$.
  15. Now Alice can spend the payment she received from Bob, by creating a signature using $k$.
$\endgroup$

1 Answer 1

2
$\begingroup$

Your algorithm should be secure since it's basicly the same as the "one-time-address"-algorithm in the CryptoNote protocol, which is described as following:

  1. Alice generates two secret keys $a$ and $b$ and publishes $A = aG$ and $B=bG$.
  2. Bob, who wants to send a coin to Alice generates a random $r$ and publishes $R = rG$ and $P = H(rA)G+B$.
  3. Alice (or any party knowing $a$) can check weather a payment belongs to Alice by checking whether $H(aR)G+B = P$. Note that this does not require $b$, so Alice can let any other party check for payment by sharing $a$ without risking them to spend her coins.
  4. When Alice want's to spend the coin, she calculates $x = H(rA)+b$, which is the private key for $P$ since $P = xG = (H(rA)+b)G=H(rA)G+bG=H(rA)G+B$.

Your scheme is a variation of this algorithm with $a = b$ so that $A = B$. This leads to Bob calculation $P = H(rA)G + A$, a check can be performed with $H(aR)G+A = P$ and the secret key being $x = H(aR)+a$, so you can assume it being as secure as the CryptoNote's algorithm (which is pretty secure AFAIK), however you lose the ability to share a view key to let others search for transaction for Alice.

$\endgroup$
2
  • 2
    $\begingroup$ Note that the CryptoNote algorithm is basically a DH key exchange ($rA$=$Ra$) that derives a commonly known public key ($H(aR)+A$). Note that thus publishing $R$ is considered secure, and that no off-chain communication is needed for Alice to receive the payment. $\endgroup$ Apr 2, 2018 at 11:44
  • $\begingroup$ I haven't heard of CryptoNote before. Thanks for citing the relevant existing work/literature, and for mentioning that I discovered a special case of a more general algorithm! $\endgroup$
    – Nayuki
    Apr 2, 2018 at 15:17

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