Covert ECDH over secp256k1

covert_ecdh.md

The algorithm that used to be described here is broken.

A better alternative is described here: https://github.com/sipa/writeups/tree/main/elligator-square-for-bn

do this about 10 times:

- generate random 33 bytes, converting the first to 0x2 or 0x3 and then call secp256k1_ec_pubkey_parse on the compressed form
- keep the one that succeeds

seems to work ok... depending on your protocol and the security guarantee you need. in our case the only guarantee we need is on a remote observer operating on aggregate sets of thousands of keys ... which is a lot less worrisome than a local unprivileged observer!

Nice -- I was looking around to see if a covert ephemeral ECDH was possible and found this. It's unfortunate that such contortions need to be done to get a covert diffie hellman on secp256k1, and I guess that in the end, most protocol designers won't want to use such a scheme. Still, thanks very much for writing it up!