Good morning LL,
> On Tue, 16 Mar 2021 at 11:25, David A. Harding via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> > I curious about whether anyone informed about ECC and QC
> > knows how to create output scripts with lower difficulty that could be
> > used to measure the progress of QC-based EC key cracking. E.g.,
> > NUMS-based ECDSA- or taproot-compatible scripts with a security strength
> > equivalent to 80, 96, and 112 bit security.
>
> Hi Dave,
>
> This is actually relatively easy if you are willing to use a trusted setup. The trusted party takes a secp256k1 secret key and verifiably encrypt it under a NUMS public key from the weaker group. Therefore if you can crack the weaker group's public key you get the secp256k1 secret key. Camenisch-Damgard[1] cut-and-choose verifiable encryption works here.
> People then pay the secp256k1 public key funds to create the bounty. As long as the trusted party deletes the secret key afterwards the scheme is secure.
>
> Splitting the trusted setup among several parties where only one of them needs to be honest looks doable but would take some engineering and analysis work.
To simplify this, perhaps `OP_CHECKMULTISIG` is sufficient?
Simply have the N parties generate individual private keys, encrypt each of them with the NUMS pubkey from the weaker group, then pay out to an N-of-N `OP_CHECKMULTISIG` address of all the participants.
Then a single honest participant is enough to ensure security of the bounty.
Knowing the privkey from the weaker groups would then be enough to extract all of the SECP256K1 privkeys that would unlock the funds in Bitcoin.
Yes! Nice idea.
Another idea that came to mind is that you could also just prove equality between the weak group's key and the secp256k1 key. e.g. generate a 160-bit key and use it both as a secp256k1 and a 160-bit curve key and prove equality between them and give funds to the secp256k1 key. I implemented a proof between ed25519 and secp256k1 a little while ago for example:
https://docs.rs/sigma_fun/0.3.0/sigma_fun/ext/dl_secp256k1_ed25519_eq/index.html
This would come with the extra assumption that it's easier to break the 160-bit key on the 160-bit curve as opposed to just breaking the 160-bit key on the 256-bit curve. Intuitively I think this is the case but I would want to study that further before taking this approach.
LL