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
|
Return-Path: <adam.back@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 09A61D28
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 11 Jul 2018 10:35:22 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-oi0-f44.google.com (mail-oi0-f44.google.com
[209.85.218.44])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 9BEAF334
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 11 Jul 2018 10:35:21 +0000 (UTC)
Received: by mail-oi0-f44.google.com with SMTP id k81-v6so48333027oib.4
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 11 Jul 2018 03:35:21 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:references:in-reply-to:reply-to:from:date:message-id
:subject:to:cc;
bh=UnyKHb/7T1e9sbllKsd+Ur8a340qDrZUM22k8luAqs0=;
b=aTbP8CtdYJPFH1Zh9y7a8YPY9WfGo2f7grEupaWzj3EnslXlaXFgOqkfpoRLr+qDSt
qyqjRLCZRrSW/YIQdSix8Z0Q4oElPMk3viqhXxF6lr0K6OEoFB58eaBymfQMi9HvrC3I
p/5pWflwSwNu/BkE098K6wx+YOZi9vo6qoV+rL6jNQLjfS1xSJjnDJ+OtGxbrmF2VFcu
XzyyZ4D9dFktwKTCb9t6aXlc63nOTF9LndScAu5D+4e1d2PDDM8fMtI9JeenChrKqQ8/
aOsGjXXYW0O3QrUqtb5GuK+jsRTysVhK+giAFpxRhBQQSO9AEEWaqiVSDfwLxGS5N4wZ
AvdA==
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:reply-to
:from:date:message-id:subject:to:cc;
bh=UnyKHb/7T1e9sbllKsd+Ur8a340qDrZUM22k8luAqs0=;
b=G72OuJBHuZTy/3VFhUos1xsjuBtY9zpHIcdigSKprtqO0HPdmUCM+ttjB7MrVkC/oz
bqB6QSinqF/PgAbYMbG4gR0NFqMWHALHHPCA9qAJaBIOBtDjmTg5gDcxTxxlVgmnaQ23
+V9+wAQ/x6kh1vCUdKOL2UV1HGgAKSODaxfVqR1DsPds5F3I01DazZXmeHPGt+d/j5Nr
JeHVrDDIVBcpVTYRho25feLN/iOnJXX30Rl3EPuqlaC9171YxMMazrFIo4nP+1HXeOLd
8eI7iC6O/W6KK+frsOaDIvFATy/GLAhNeiBmJlVMeqIS8+VohS6/VRQ0Q27XwqLIHauk
cx1Q==
X-Gm-Message-State: APt69E0oK9SwmEm5xruKMWWg5L34fHRFUQI34QBBLdjfWwkxycyOQWCm
akr8P6Tr8RN51is8PJLpCpllHDlW55BCFuB4WG8=
X-Google-Smtp-Source: AAOMgpe/dEfJJKSZfwvDf0xI1gczh0RpRCVHZghK/am6IuSdMHY3Y3/m7ww7O7rMYo37g0sH/U/NVOANbXJX80ii39g=
X-Received: by 2002:aca:a982:: with SMTP id
s124-v6mr32154717oie.80.1531305320844;
Wed, 11 Jul 2018 03:35:20 -0700 (PDT)
MIME-Version: 1.0
References: <CAJowKgLrSe77sqO2iB7mYboo_HW=YjO4=AFdv7L5FUi2vygMiQ@mail.gmail.com>
<08201f2292587821e6d23f6cc201d95e6e5ad2cd.camel@timruffing.de>
<CAAS2fgSPUc7xRq36rZ9BVLjUTdd152Fgho4sjJXLhfrc71vPMw@mail.gmail.com>
<CAJowKgL-nRcruXhWdGWrT4x+oV7i3jYST2Wa3bF5m6iT_mOyMw@mail.gmail.com>
<CAPg+sBjdu4mnda-P0y7Ddu-rN7a1GiUt0hY_wYGsy_bJLKOYMA@mail.gmail.com>
<CAJowKgLSQZ1LrZayDi7EFc-NSfK_AD+zBdyaF7jBeQRP7tOwYQ@mail.gmail.com>
<CAPg+sBizrx20XShpeZRvZd4bfq1=E+MFUDmSC9X-xK1CSbV5kQ@mail.gmail.com>
<CAJowKg+=7nS4gNmtc8a4-2cu1uCOPqxjfchFwDVqUciKNMUYWQ@mail.gmail.com>
<CAJowKgJ3K=wmCEtoZXJZhrnnA8XJcHYg788KP+7MCeP4Mxf-0w@mail.gmail.com>
<CAAS2fgSmA02s6Vdk_FYv6NJ4smLBgxnuT4jRYU44G7=bbzv2MA@mail.gmail.com>
<CAJowKgJjQ8EGgbCurOSjTh8ij42_BVeD6dE0y67tzN0Zop3pyg@mail.gmail.com>
<CAAS2fgRrkzq6Fa5T_-YDwLDkwi30LpDtMObMEBE+Fmmj0LJpBw@mail.gmail.com>
<CAJowKgL0b3RT7XwRTF+ohoJCyZAW-ZJ+-8Lijj_s1rqqxgU7VQ@mail.gmail.com>
<CAJowKg+UaMsY_nL6SBfb20Ltki+LdhXOwwvG_mAsUq_ww3Tesg@mail.gmail.com>
In-Reply-To: <CAJowKg+UaMsY_nL6SBfb20Ltki+LdhXOwwvG_mAsUq_ww3Tesg@mail.gmail.com>
Reply-To: adam@cypherspace.org
From: Adam Back <adam.back@gmail.com>
Date: Wed, 11 Jul 2018 11:35:08 +0100
Message-ID: <CALqxMTHYaspkn8JupaHBeLDxLOfZbnwcne2AVeFZe2ADOefktA@mail.gmail.com>
To: Erik Aronesty <erik@q32.com>,
Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000b1147a0570b6cd6b"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] Multiparty signatures
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
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: Wed, 11 Jul 2018 10:35:22 -0000
--000000000000b1147a0570b6cd6b
Content-Type: text/plain; charset="UTF-8"
On Wed, Jul 11, 2018, 02:42 Erik Aronesty via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> Basically you're just replacing addition with interpolation everywhere in
the musig construction
Yes, but you can't do that without a delinearization mechanism to prevent
adaptive public key choice being used to break the scheme using Wagner's
attack. It is not specific to addition, it is a generalized birthday attack.
Look at the delinearization mechanism for an intuition, all public keys are
hashed along with per value hash, so that pre-commits and forces the public
keys to be non-adaptively chosen.
Adaptively chosen public keys are dangerous and simple to exploit for
example pub keys A+B, add party C' he chooses C=C'-A-B, now we can sign for
A+B+C using adaptively chose public key C.
Btw Wagner also breaks this earlier delinearization scheme
S=H(A)*A+H(B)*B+H(C)*C
Adam
--000000000000b1147a0570b6cd6b
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"auto"><div dir=3D"ltr" style=3D"font-family:sans-serif">On Wed,=
Jul 11, 2018, 02:42 Erik Aronesty via bitcoin-dev <<a href=3D"mailto:bi=
tcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org<=
/a>> wrote:<br></div><span style=3D"font-family:sans-serif">> Basical=
ly you're just replacing addition with interpolation everywhere in the =
musig construction</span>=C2=A0<div dir=3D"auto"><br></div><div dir=3D"auto=
">Yes, but you can't do that without a delinearization mechanism to pre=
vent adaptive public key choice being used to break the scheme using Wagner=
's attack. It is not specific to addition, it is a generalized birthday=
attack.</div><div dir=3D"auto"><br></div><div dir=3D"auto">Look at the del=
inearization mechanism for an intuition, all public keys are hashed along w=
ith per value hash, so that pre-commits and forces the public keys to be no=
n-adaptively chosen.=C2=A0</div><div dir=3D"auto"><br></div><div dir=3D"aut=
o">Adaptively chosen public keys are dangerous and simple to exploit for ex=
ample pub keys A+B, add party C' he chooses C=3DC'-A-B, now we can =
sign for A+B+C using adaptively chose public key C.</div><div dir=3D"auto">=
<br></div><div dir=3D"auto">Btw Wagner also breaks this earlier delineariza=
tion scheme S=3DH(A)*A+H(B)*B+H(C)*C</div><div dir=3D"auto"><br></div><div =
dir=3D"auto">Adam</div></div>
--000000000000b1147a0570b6cd6b--
|
