1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
Return-Path: <lloyd.fourn@gmail.com>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136])
by lists.linuxfoundation.org (Postfix) with ESMTP id 002B1C000A
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 5 Apr 2021 00:28:19 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp3.osuosl.org (Postfix) with ESMTP id D99EC60873
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 5 Apr 2021 00:28:19 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: 0.602
X-Spam-Level:
X-Spam-Status: No, score=0.602 tagged_above=-999 required=5
tests=[BAYES_50=0.8, 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_HELO_NONE=0.001,
SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: smtp3.osuosl.org (amavisd-new);
dkim=pass (2048-bit key) header.d=gmail.com
Received: from smtp3.osuosl.org ([127.0.0.1])
by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id gv243icfU7tW
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 5 Apr 2021 00:28:18 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-pf1-x436.google.com (mail-pf1-x436.google.com
[IPv6:2607:f8b0:4864:20::436])
by smtp3.osuosl.org (Postfix) with ESMTPS id BC4AD60872
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 5 Apr 2021 00:28:18 +0000 (UTC)
Received: by mail-pf1-x436.google.com with SMTP id h3so2361323pfr.12
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 04 Apr 2021 17:28:18 -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=PUgbhOJzsNfuLyzAFxYefPRrcG1bR/X7Y2VaKcGaUNM=;
b=bkeLlpd97ly/2GXbRhZ53LenBxaQKUUSnHg7QIWHxFWZ6RM0uarCnLvWJmO2yFXN+/
eZ0GmCc+D218ZaUy0OasRZb7ld39vKa4u22Q7vu2m9aXTztbbCLDFxRuVNPq5a3LFkwW
liHyOh/hnLfOR/V9b/lPRlaWoT1yQ1vBTIiw6AcW9gm5y2U4Vkr9RGemg/A3tkUvSHys
6sRZ9fxTYF0JkOn0tkcKOIKNXjYQ1csLEoHIy5ilM7jAhz03ZVofopyOPtUCfG+aKJSh
s0eOmcopXMJ1sbMNGmrkGYYmehz685zm/OB2vSy3NjXrrdCDRkk+fmL/OD4YFbEiTfNS
gjLg==
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=PUgbhOJzsNfuLyzAFxYefPRrcG1bR/X7Y2VaKcGaUNM=;
b=ThaPIWMUWvGZtSb1PaG+ZrRiVM1vGowm7YTxxB8y2KYFnXhi31WQGYkY1BbZJb+sP1
XxbUk1SzUwhiSZAtyW2BrNH+FyO92uG5jG1vS+LwPxftQ55YKTfHESlSEflK9YWSqwo+
Tw0IhaQdg9s2EybSZJ4nA6LOh8R3QTyUERrUg/kWXZDcAWK398716ZYDBhYgLFr9ZMen
1LybiOnFVRcCtOkAxWF3WwZzWZLMjgdXqb1V/fPTGY7i+raE4e8zDGfC3Uce7jYjkx/G
fXY8D2UTT42nBLYFwpQzfZRfgdjlLImO0pjbOFKvS9g7D0MoqMIFwtGkRm7snt8hsj2+
tIyg==
X-Gm-Message-State: AOAM533plwxGbnzLKsYZ49CHjVD6WIKZLOLCCAeqDhCL3n6oLCgzQQAV
81XIue2yUMCqPb5IHE8k1yr8uTQEGJHk3V+HbWH171h9GlubRg==
X-Google-Smtp-Source: ABdhPJyd5aPSv6P8JKWAi3qU2hirTfIDo8AL99+QILspGflZDLCoC6aP3TIwvkSgezC36dB5MxJ5x09zcpbbRov+ois=
X-Received: by 2002:a65:5c88:: with SMTP id a8mr20365400pgt.130.1617582498074;
Sun, 04 Apr 2021 17:28:18 -0700 (PDT)
MIME-Version: 1.0
References: <202103152148.15477.luke@dashjr.org>
<20210316002401.zlfbc3y2s7vbrh35@ganymede>
In-Reply-To: <20210316002401.zlfbc3y2s7vbrh35@ganymede>
From: Lloyd Fournier <lloyd.fourn@gmail.com>
Date: Mon, 5 Apr 2021 10:27:50 +1000
Message-ID: <CAH5Bsr20n2T7KRTYqycSUx0iEuEApC8NGtPCfN8rYhRyHLE4gA@mail.gmail.com>
To: "David A. Harding" <dave@dtrt.org>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000003151e305bf2ec668"
X-Mailman-Approved-At: Mon, 05 Apr 2021 21:47:48 +0000
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: Mon, 05 Apr 2021 00:28:20 -0000
--0000000000003151e305bf2ec668
Content-Type: text/plain; charset="UTF-8"
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.
[1] https://link.springer.com/content/pdf/10.1007/3-540-44448-3_25.pdf
Cheers,
LL
--0000000000003151e305bf2ec668
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div dir=3D"ltr" class=3D"gmail_attr">On Tue, 16 Mar 2021 =
at 11:25, David A. Harding via bitcoin-dev <<a href=3D"mailto:bitcoin-de=
v@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>> =
wrote:<br></div><div class=3D"gmail_quote"><blockquote class=3D"gmail_quote=
" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);=
padding-left:1ex"><br>I curious about whether anyone informed about ECC and=
QC<br>
knows how to create output scripts with lower difficulty that could be<br>
used to measure the progress of QC-based EC key cracking.=C2=A0 E.g.,<br>
NUMS-based ECDSA- or taproot-compatible scripts with a security strength<br=
>
equivalent to 80, 96, and 112 bit security.</blockquote><div><br></div><div=
>Hi Dave,</div><div><br></div><div>This is actually relatively easy if you =
are willing to use a trusted setup. The trusted party takes a secp256k1 sec=
ret key and verifiably encrypt it under a NUMS public key from the weaker g=
roup. Therefore if you can crack the weaker group's public key you get =
the secp256k1 secret key. Camenisch-Damgard[1] cut-and-choose verifiable en=
cryption works here.</div><div>People then pay the secp256k1 public key fun=
ds to create the bounty. As long as the trusted party deletes the secret ke=
y afterwards the scheme is secure.<br></div><div><br></div><div>Splitting t=
he trusted setup among several parties where only one of them needs to be h=
onest looks doable but would take some engineering and analysis work.<br></=
div><div><br></div><div>[1] <a href=3D"https://link.springer.com/content/pd=
f/10.1007/3-540-44448-3_25.pdf">https://link.springer.com/content/pdf/10.10=
07/3-540-44448-3_25.pdf</a></div><div><br></div><div>Cheers,</div><div><br>=
</div><div>LL<br></div><div>=C2=A0<br></div></div></div>
--0000000000003151e305bf2ec668--
|