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

Cool stuff @sipa!

I'm sure I could be missing something here, but I hadn't heard of Elligator-style encodings before reading this text, and while searching for papers on it I came across Tibouchi's "Elligator Squared" paper:

• https://eprint.iacr.org/2014/043.pdf

They mention the restriction that Elligator "cannot be used with prime-order curves" and that their paper "propose[s] an approach to overcome all of these limitations" for the cost that "bit string representation is somewhat less compact (about twice as long as Elligator)".

I can't claim to follow the details, but thought I'd drop the link in case it could be useful!

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!