path: root/30/2d7c854c024a95eed35923f46ec658f963af4b

Return-Path: <lloyd.fourn@gmail.com>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id AC194C000A
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 16 Apr 2021 05:00:38 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp4.osuosl.org (Postfix) with ESMTP id 809CC4185D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 16 Apr 2021 05:00:38 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Level: 
X-Spam-Status: No, score=-2.099 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001]
 autolearn=ham autolearn_force=no
Authentication-Results: smtp4.osuosl.org (amavisd-new);
 dkim=pass (2048-bit key) header.d=gmail.com
Received: from smtp4.osuosl.org ([127.0.0.1])
 by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id QOX2ncse3cAU
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 16 Apr 2021 05:00:36 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-lj1-x22a.google.com (mail-lj1-x22a.google.com
 [IPv6:2a00:1450:4864:20::22a])
 by smtp4.osuosl.org (Postfix) with ESMTPS id 07DFB40E66
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 16 Apr 2021 05:00:35 +0000 (UTC)
Received: by mail-lj1-x22a.google.com with SMTP id p23so25973196ljn.0
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 15 Apr 2021 22:00:35 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=ct6OYS1ubXfKagYwITRvZb9SUCW41BbqjsCfdagGolM=;
 b=JUDrDAnmR0Zx4TUcVpe2l8Zht+7YRTIqVaiByJ+ul/OvPd2jM15MSn7nrcHLZoByPU
 n2r59gVmO3+MdGl3FHTGH7enFd9DcM4gJ7qf0pb8/X+vO4lvrH1U1aOix2jvftm7DprZ
 RnWauaBjvqHGO+7sB647d5IfVNH559xQBdlQUTPayBKlfT0ukLIWVmn/9Qs8YkC25DFU
 OSlCiMkCTtv/bBSSS3Y2Gt8vsNWHhdBQ95JEOvp0oCPT2lI7og/4L22CFEDa1DIwTB5L
 Du25Su1BOL5SpDiXD70RCx3UvSn+sOY0vg/ElrWfQEFa8EXXsq1HW+GwBXA381z5vxAi
 GDrA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=ct6OYS1ubXfKagYwITRvZb9SUCW41BbqjsCfdagGolM=;
 b=XoHoAWjI2G1D6nyZiAbA7IqpM3W9U5K5abg/jfDklLG0mUXbblZyRJywzHhJi/LkI2
 ptHKEGiVMpsnEkj20D9O1ZgVjqhbyQKHc5U3LxGihyjF2Ag90tYdfHiqcKpiRj9SVfED
 cAiDKGMNLDgy4I9hdjH2CELIKzkZyWQx8BFF6cuPPHmjM4lCKxVhEc7sr92F3rDFhWDD
 44YOehzGzS17ng9Wns10/L2l3qA9AHt0dzDEuDQQEwlotd1+ptb3iVTS9IR+/ABTo4Kh
 H9ErqrSL9GI4HgbTzBbW0JiuLkw4ypCz2T9dKX2gosccP2DBKwbAjVOYMqPwZKeckjWX
 BW+A==
X-Gm-Message-State: AOAM530dcnRvKLdDPv7c6ECOzVpnWGG50K5H/Y1ehFe8wc+M2KeagX67
 f/K3DTcEVGASp0gnV/puQIUfYt8YZGtUDDxaHUE=
X-Google-Smtp-Source: ABdhPJzHCO8h9BZzukJ8luC7vzDNRoZNDDNkcQEeWwJNA6LFfzJygVDkmGW+3aDlAu15l+PWyUDGIk9qXA5d24eqoo8=
X-Received: by 2002:a2e:8881:: with SMTP id k1mr1485458lji.441.1618549233694; 
 Thu, 15 Apr 2021 22:00:33 -0700 (PDT)
MIME-Version: 1.0
References: <202103152148.15477.luke@dashjr.org>
 <20210316002401.zlfbc3y2s7vbrh35@ganymede>
 <CAH5Bsr20n2T7KRTYqycSUx0iEuEApC8NGtPCfN8rYhRyHLE4gA@mail.gmail.com>
 <aRiFFJKz5wyHFDi2dXcGbNEHZD2nIwDRk7gaXIte-N1BoOEOQ-ySYRnk0P70S5igANSr2iqF2ZKV1dWvipaQHK4fJSv9A61-uH7w4pzxKRE=@protonmail.com>
In-Reply-To: <aRiFFJKz5wyHFDi2dXcGbNEHZD2nIwDRk7gaXIte-N1BoOEOQ-ySYRnk0P70S5igANSr2iqF2ZKV1dWvipaQHK4fJSv9A61-uH7w4pzxKRE=@protonmail.com>
From: Lloyd Fournier <lloyd.fourn@gmail.com>
Date: Fri, 16 Apr 2021 15:00:07 +1000
Message-ID: <CAH5Bsr39kw08ki76aezJ1EM9e7mdLFLUmtKwJJNYcyuMpR_Cuw@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: multipart/alternative; boundary="000000000000203bc505c00fdc4f"
X-Mailman-Approved-At: Fri, 16 Apr 2021 13:32:16 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] PSA: Taproot loss of quantum protections
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Fri, 16 Apr 2021 05:00:38 -0000

--000000000000203bc505c00fdc4f
Content-Type: text/plain; charset="UTF-8"

On Fri, 16 Apr 2021 at 13:47, ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> 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

--000000000000203bc505c00fdc4f
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr"><br></div><br><div class=3D"gmail_quote">=
<div dir=3D"ltr" class=3D"gmail_attr">On Fri, 16 Apr 2021 at 13:47, ZmnSCPx=
j &lt;<a href=3D"mailto:ZmnSCPxj@protonmail.com">ZmnSCPxj@protonmail.com</a=
>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px=
 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Goo=
d morning LL,<br>
<br>
&gt; On Tue, 16 Mar 2021 at 11:25, David A. Harding via bitcoin-dev &lt;<a =
href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bit=
coin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br>
&gt;<br>
&gt; &gt; I curious about whether anyone informed about ECC and QC<br>
&gt; &gt; knows how to create output scripts with lower difficulty that cou=
ld be<br>
&gt; &gt; used to measure the progress of QC-based EC key cracking.=C2=A0 E=
.g.,<br>
&gt; &gt; NUMS-based ECDSA- or taproot-compatible scripts with a security s=
trength<br>
&gt; &gt; equivalent to 80, 96, and 112 bit security.<br>
&gt;<br>
&gt; Hi Dave,<br>
&gt;<br>
&gt; This is actually relatively easy if you are willing to use a trusted s=
etup. 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 cra=
ck the weaker group&#39;s public key you get the secp256k1 secret key. Came=
nisch-Damgard[1] cut-and-choose verifiable encryption works here.<br>
&gt; People then pay the secp256k1 public key funds to create the bounty. A=
s long as the trusted party deletes the secret key afterwards the scheme is=
 secure.<br>
&gt;<br>
&gt; Splitting the trusted setup among several parties where only one of th=
em needs to be honest looks doable but would take some engineering and anal=
ysis work.<br>
<br>
To simplify this, perhaps `OP_CHECKMULTISIG` is sufficient?<br>
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.<br>
Then a single honest participant is enough to ensure security of the bounty=
.<br>
<br>
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.</bloc=
kquote><div><br></div><div>Yes! Nice idea.<br></div><div><br></div><div>Ano=
ther idea that came to mind is that you could also just prove equality betw=
een the weak group&#39;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 equal=
ity between them and give funds to the secp256k1 key. I implemented a proof=
 between ed25519 and secp256k1 a little while ago for example: <a href=3D"h=
ttps://docs.rs/sigma_fun/0.3.0/sigma_fun/ext/dl_secp256k1_ed25519_eq/index.=
html">https://docs.rs/sigma_fun/0.3.0/sigma_fun/ext/dl_secp256k1_ed25519_eq=
/index.html</a></div><div><br></div><div>This would come with the extra ass=
umption that it&#39;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. Intuitive=
ly I think this is the case but I would want to study that further before t=
aking this approach.</div><div><br></div><div>LL<br></div></div></div>

--000000000000203bc505c00fdc4f--