8

I wonder what the origin of stealth addresses is.

I learned that they were introduced for BitCoin, by Peter Todd. However, I cannot find any literature describing or analysing the specific instantiation in Monero:

P=H_s(rA)G + B

x=H_s(aR) + b

  1. Does this construction differ from what Peter Todd proposed?
  2. Who came up with this construction, is this something described in literature?
  3. Has there been any public cryptanalysis on this construction?

The white paper (CryptoNote 2.0, Nicolas van Saderhagen) does not refer to any source, as far as I can tell.

  • could you please link to what Petter Todd proposed – JollyMort Dec 1 '17 at 16:44
  • Well, actually, I would want to know what he proposed; otherwise I can tell the difference myself. – rubdos Dec 1 '17 at 18:33
  • OK, well, I found this: medium.com/@octskyward/… – JollyMort Dec 1 '17 at 18:41
  • 1
    Perhaps this is the first appearance which is cited in this Bitcoin SE answer? – stoffu Dec 5 '17 at 7:15
  • Yes, that sounds right. That's one that I can cite :-) – rubdos Dec 6 '17 at 8:57
6

"Stealth Address" is really just a fancy name for a neat use of Elliptic Curve Diffie-Hellman key exchange. Its use in Monero is described here in detail, but not under that name. This allows for the sender to effectively salt the output and privately communicate the salt to the recipient. I have no idea who and when coined the term "stealth address" to describe it.

As for cryptanalysis, it's all using existing well-known primitives and should be trivial. There's a nice presentation from UCL going through various set-ups, and looking at the site of origin, I also discovered that a nice paper has been published recently.

Courtois N. and Mercer R. (2017). Stealth Address and Key Management Techniques in Blockchain Systems. In Proceedings of the 3rd International Conference on Information Systems Security and Privacy ISBN 978-989-758-209-7, pages 559-566. DOI: 10.5220/0006270005590566

But let's look at it from another angle, and try to build it from bottom up.

What's the minimum you need to do to be able to transact Monero? All you need is outputs and amounts (post-RCT, commitments take the role of amounts). The network verifies the signature, and the signature is produced by using the individul one-time output's private key.

So, all you really need are keypairs P=xG. You could create the destination key by any means you want.

For example, I (the receiver) could roll some x, communicate the P to you, and you make a TX with output P. You could omit the TX keys entirely because I already know my P and x and can tell my wallet to use them when I want to spend. This is because I (the receiver), have decided what the output will be.

This is practically the same as Bitcoin. I give you a public key (well, hash of it) and you pay to the public key (hash).

With CN we could do it the same way. Network doesn't force you to use ECDH & TX keys. However, due to use of ring signatures, we must be sure to never receive twice to the same key. With this in mind, it would be a big hassle to receive. You'd have to generate a new unique key whenever someone wants to send you something. If someone intercepts the payment request, he could monitor the blockchain for appearance of that P and know when you received something.

So, we want a way for the sender to roll the destination output P, in such a way that he won't know x, but such that I will.

For that, I could have some key B=bG for passive receiving, and the sender could construct outputs like P = R + B where he picks some random R=rG. Problem is, he needs to tell me the r as well in order for me to be able to spend so I could recreate the output's secret key x = r + b, compute the public key P, and use that to check that the output is indeed recorded on the blockchain and later spend it. We could make this work today, between me and you. All it requires is a wallet modification. It's not the best however, as you need to communicate the r via secure channel if I am to keep my privacy.

What about using blockchain for communication? That way I can't lose or forget the r and with that lose access to my funds. Problem is, while blockchain is great for record-keeping it is public so it's insecure communication channel. And what's a good way to privately communicate via insecure channel? ECDH.

We could say, OK, let's have the sender roll the outputs like: P=Hs(rB)G+B. Now he can tell me (write it to the blockchain) the R, and I can re-create the keys with x = Hs(bR)+b. Cool. Now someone intercepting the R can't tell that some P is for me, even if he knows my address B. But now, I can't ever be audited otherwise I have to leak my secret key to the auditor and then he could run off with everything. I can't even reveal selective, already spent, outputs, because someone knowing shared secret (bR) and secret key (x) of an output could work out my secret spend key b.

That's why we make the receiving address use dual keys, and then one is enough to check ownership without risk of revealing x, and the other is required to recover the x. With that we arrive to the current set-up.

  • ECDH does not involve generating a one-time keypair. This "session key" is something I cannot find anywhere in literature. It seems trivially provable in ROM; nonetheless, some kind of security proof would be appreciated. – rubdos Dec 1 '17 at 18:54
  • 1
    Actually, that presentation is related to a paper which I believe holds answers to your questions: doi.org/10.5220/0006270005590566 – JollyMort Dec 1 '17 at 19:05
  • Ahaaaa, that one sounds very interesting. Would you mind incorporating that in your answer? This paper indeed seems be the answer; thank you! – rubdos Dec 1 '17 at 19:25
  • 1
    Sure, I discovered that paper just now, actually =) – JollyMort Dec 1 '17 at 20:09
  • 1
    This indeed is a regular ECDH where the shared secret is used as private key... I didn't recognise it at first... Thanks again! :-) – rubdos Dec 8 '17 at 8:54

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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