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
Last active
January 4, 2023 10:31
-
-
Save sipa/29118d3fcfac69f9930d57433316c039 to your computer and use it in GitHub Desktop.
Covert ECDH over secp256k1
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!
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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:
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!