BTC Quatntum Bounty for smaller curves

[LLFourn]

An idea that came up on bitcoin-dev was to provide a trustless BTC bounty for smaller curves as a bounty for breaking the security of those curves: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-April/018730.html

There are schemes to do this but what remains is to choose one and to reduce the trust placed in any trusted setup.

I feel like this is a fun topic and deserves a problem page. This QC problem deserves a higher priority though: #4

[earonesty]

Easy enough to implement with a federation, proof-of-secret-key, and a multipart key that's encrypted with the smaller curve. No need for anything special, although proving that the final result is an encryption of the private can might also be done with elgamal.

Generating a multiparty private key isn't hard. Requires a commitment round, etc.

Some trust that the federation wont destroy the key, but a public ritual, like the one used for zcash should be enough for most people to be comfortable sending sats to the bounty address.

Seems like the hard part would really be getting enough trusted names in the space to participate in the ritual, and then publicising and hosting a webpage showing the bitcoin address to donate to in order to claim the bounty.

I would be happy to code this up as a simple script - if enough people cared about it.

[LLFourn]

Maybe you're right that this doesn't need a problem page because the answer seems pretty obvious?

No need for anything special, although proving that the final result is an encryption of the private can might also be done with elgamal.

This is at least a little bit special. You need each participant to do the cross curve DLEQ proof for their share of the key. We implemented this for ed25519 <-> secp256k1 here: https://github.com/LLFourn/secp256kfun/blob/master/sigma_fun/src/ext/dl_secp256k1_ed25519_eq.rs

I think this proof is sufficient. There is a question about whether you could do it as single proof with each providing their share or just do n individual proofs. I'd just do the latter.

[earonesty]

yeah, seems easier and has more clarity to just do n proofs.

i think it's ok to have a problem page until someone bothers to code-up a command-line solution to the key generation ritual that everyone can inspect. i know how to do the dkg right, but you seem like you've got a handle on the DLEQ stuff. staring at the code isn't helping me.

also it will be super fun to get high-trust & well known individuals to be filmed / publicly commit to building, running the software on a pi, generating the shares and destroying the private keys in a bin of fire and lye. a mini 5 minute documentary reminiscent of the zcash ritual

[LLFourn]

yeah, seems easier and has more clarity to just do n proofs.

i think it's ok to have a problem page until someone bothers to code-up a command-line solution to the key generation ritual that everyone can inspect. i know how to do the dkg right, but you seem like you've got a handle on the DLEQ stuff. staring at the code isn't helping me.

Well volunteered! Indeed I volunteer to implement another DLEQ proof between whatever low security curves are chosen and secp256k1.