Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 15F40C7F for ; Thu, 26 Jul 2018 02:05:20 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wm0-f44.google.com (mail-wm0-f44.google.com [74.125.82.44]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id E1D3E709 for ; Thu, 26 Jul 2018 02:05:18 +0000 (UTC) Received: by mail-wm0-f44.google.com with SMTP id f21-v6so339900wmc.5 for ; Wed, 25 Jul 2018 19:05:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=q32-com.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=V6SJygRg16rmxb3UTaZLjCh61OZun12Z/Ii3dSM4EaY=; b=fcvCaduOkTd3d/sakWMRuBHhcQxAPO4Z4nMxnAuiHoi+TSYkJqPyP1r5D7wbFm7Job vGUGdLbCQVZfaxygdh1EOtOjQJw6hVsA1gcV3GnzWEfwXWBadUqRZKMD6w6huyOdLXyj LxGzmwcEW8FCaqT3SBaKMFfxf5PHTVbE5pfXLkmXY398Z8Hs0U+QUVjflnJ+dcSNoeDB hnyG7V+rjjXFdftbU/1e0O4cYwqoppGFlxw29r/Vfqiy82APUghhdnhe6bP5bEL1OJmM Z60QVMUkbYX6TkXOH9+TgM9Udy1MjtiJp4xE5SN7oyexaihmMwGvC1vvE8su/elQS4Ho DbkA== 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; bh=V6SJygRg16rmxb3UTaZLjCh61OZun12Z/Ii3dSM4EaY=; b=YrKr0XK94YjbYwX67TfG1Z0owjnR1alLCrVaU4TFXciSGIc7704B8WG8dupY2rhPVf WFF/imYZ2zjWAhyEKTPM9kcl8K6zUO1XCy++lEwjQiShRK75Aof5+faiNvgONG0Xq7Rk WY5CZcvN3Oa70k8cuYHNOiUjDEh1lsrB7907Y1DcIiPW6jq1YEEExzuoCeKpKukgC3vB Apoi+fH+STBDhKARwudI107qvZ8XFYoT2xpB8PrBsAZbj7Yk1K4jHulZLngEdtB9BHRF MOmGsDEKdnP6+tZPThXgjUKD50A7+MkiEBp/Q2TdxtnV0oqa6dXRiX+AV8F2t8CY/tea Fx8w== X-Gm-Message-State: AOUpUlF5wux+XeeZyudjqtJNpF8WZFdxBxL/nfRyWvK21X2gW8hK9aNv kukIPOVdTaN0N/gtjSEJ3F4q+yCel0+A1jSgs1TDaaF77g== X-Google-Smtp-Source: AAOMgpest23wjwiThO6io8zHIyb1/MkRfjy5HXJ6KjnMn/WeLbMe00taAKvDcO8CjMLl+BWIHQB0f2ESELGAlO9Kef4= X-Received: by 2002:a1c:8952:: with SMTP id l79-v6mr212189wmd.7.1532570717186; Wed, 25 Jul 2018 19:05:17 -0700 (PDT) MIME-Version: 1.0 References: <08201f2292587821e6d23f6cc201d95e6e5ad2cd.camel@timruffing.de> In-Reply-To: From: Erik Aronesty Date: Wed, 25 Jul 2018 22:05:05 -0400 Message-ID: To: Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="00000000000030f1ea0571dd6db5" X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, 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 X-Mailman-Approved-At: Thu, 26 Jul 2018 02:08:07 +0000 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 26 Jul 2018 02:05:20 -0000 --00000000000030f1ea0571dd6db5 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Also we don't need any new opcodes to support this. Done right this could literally go out into clients immediately. On Fri, Jul 20, 2018, 4:18 PM Erik Aronesty wrote: > Sorry there were typos: > > - Using MuSig's solution for the blinding factor (e) > - Using interpolation to enhance MuSig to be M of N instead of M of M > > References: > > - MuSig > https://blockstream.com/2018/01/23/musig-key-aggregation-schnorr-signatur= es.html > - HomPrf http://crypto.stanford.edu/~dabo/papers/homprf.pdf (sections > 7.1 and 7.4) > > Each party: > > 1. Publishes public key G*xi, G*ki, where ki is a random nonce > 3. Xi =3D H(G*xi) ... Xi is the parties x coordinate, for the purposes of > interpolation > 3. R =3D G*k =3D via interpolation of r1=3DGk1, r2=3DGk2... (see HomPrf) > 4. L =3D H(X1,X2,=E2=80=A6) (see MuSig) > 5. X =3D sum of all H(L,Xi)Xi (see MuSig) > 6. Computes e =3D H(R | M | X) .... standard schnorr e... not a share > 7. Computes si =3D ki *e+ xi * e ... where si is a "share" of the sig, an= d > xi is the private data, and e is the blinding factor > 8. Publishes (si, e) as the share sig > > If an attacker has multiple devices, e is safe, because of the musig > construction. > > But what protects k from the same multiparty birthday attack? > > If an attacker has multiple devices, by carefully controlling the > selection of private keys, the attacker can try to solve > the polynomial equation to force the selection of a "known k". > > A "known k" would allow an attacker to sign messages on his own. > > To fix this, we need to somehow "blind k as well". > > Does this work? > > The revision below seems to solve this problem. > > 1. Publishes public key G*xi, G*ki, where ki is a random nonce > 3. Xi =3D H(G*xi) ... Xi is the parties x coordinate, for the purposes of > interpolation > 3. R =3D G*k =3D via interpolation of r1=3DGk1, r2=3DGk2... (see HomPrf) > 4. L =3D H(X1,X2,=E2=80=A6) (see MuSig) > 5. L2 =3D H2(XN,XN-1,=E2=80=A6) (see MuSig... H2 is a "second hash") > 6. X =3D sum of all H(L,Xi)Xi (see MuSig) > 7. Computes e =3D H(R | M | X) .... standard schnorr e... not a share > 8. Computes e2 =3D H(R | M | X2) ... a second blinding factor > 9. Computes si =3D ki *e2 + xi * e ... where si is a "share" of the sig, = and > xi is the private data, and e, e2 are blinding factors > 10. Publishes (si, e, e2) as the share sig > > The final signature is computed via interpolation, and e2 is can be > subtracted to recover a "normal" schnor sig for the set of participants. > > Now there's no mechanism for a birthday attack on k. > > > > On Fri, Jul 20, 2018 at 1:34 PM, Erik Aronesty wrote: > >> Hi, thanks for all the help. I'm going to summarize again, and see if >> we've arrived at the correct solution for an M of N "single sig" extensi= on >> of MuSig, which I think we have. >> >> - Using MuSig's solution for the blinding to solve the Wagner attack >> - Using interpolation to enhance MuSig to be M of N instead of M of M >> >> References: >> >> - MuSig >> https://blockstream.com/2018/01/23/musig-key-aggregation-schnorr-signatu= res.html >> - HomPrf http://crypto.stanford.edu/~dabo/papers/homprf.pdf (sections >> 7.1 and 7.4) >> >> Each party: >> >> 1. Publishes public key G*xi >> 3. Xi =3D H(G*xi) ... Xi is the parties x coordinate, for the purposes o= f >> interpolation >> 3. r =3D G*x =3D via interpolation of Gx1, Gx2... (see HomPrf) >> 4. L =3D H(X1,X2,=E2=80=A6) (see MuSig) >> 5. X =3D sum of all H(L,Xi)Xi (see MuSig) >> 6. Computes e =3D H(r | M | X) .... standard schnorr e... not a share >> 7. Computes si =3D xi - xe ... where si is a "share" of the sig, and xi = is >> the private data >> 8. Publishes (si, e, G*Xi) >> >> Any party can then derive s from m of n shares, by interpolating, not >> adding. >> >> >> >> > --00000000000030f1ea0571dd6db5 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Also we don't need any new opcodes to support this.= =C2=A0 Done right this could literally go out into clients immediately.
On Fri, Jul 20, 2018, 4:1= 8 PM Erik Aronesty <erik@q32.com>= wrote:
Sorry there were typos:

- Using MuSig's solution for the blinding factor (e)<= br>
- Using interpolation to enhance MuSig to be M of = N instead of M of M

References:

=C2=A0- HomPrf http:/= /crypto.stanford.edu/~dabo/papers/homprf.pdf (sections 7.1 and 7.4)

Each party:

1. Publishes public key G*xi, G*ki, where ki is a random nonce
3. Xi =3D H(G*xi) ... Xi is the parties x coordinate, f= or the purposes of interpolation
3. R =3D G*k =3D via = interpolation of r1=3DGk1, r2=3DGk2... (see=C2=A0HomPrf)
4. L= =3D H(X1,X2,=E2=80=A6) (see MuSig)
5. X =3D sum o= f all H(L,Xi)Xi (see MuSig)
6. Computes e =3D H(R | M | X) ..= .. standard schnorr e... not a share
7. Computes si = =3D ki *e+ xi * e ... where si is a "share" of the sig, and xi is= the private data, and e is the blinding factor
8.= Publishes (si, e) as the share sig

If an attacker has multiple devices, e is safe, because of the musig const= ruction.

But what protects k from the same multiparty birthday attac= k?=C2=A0=C2=A0

<= div style=3D"font-size:small;text-decoration-style:initial;text-decoration-= color:initial">
= If an attacker has multiple devices, by carefully controlling the selection= of private keys, the attacker can try to solve
the polynomial eq= uation to force the selection of a "known k".

A &quo= t;known k" would allow an attacker to sign messages on his own.
<= div style=3D"text-decoration-style:initial;text-decoration-color:initial"><= br>
To fix this, we need to somehow "blind k as well".
=
=
Does this work?

The revision below seems to solve = this problem.

1. Publishes public key G*xi, G*ki, where ki is a random no= nce
3. Xi =3D H(G*xi) ... Xi is the parties x coor= dinate, for the purposes of interpolation
3. R =3D G*k= =3D via interpolation of r1=3DGk1, r2=3DGk2... (see=C2=A0HomPrf)
4. L =3D H(X1,X2,=E2=80=A6) (see MuSig)
= 5. L2 =3D H2(XN,XN-1,=E2=80=A6) (see MuSig... H2 is a "second hash&quo= t;)
6. X =3D sum of all H(L,Xi)Xi (see MuSig)
7. Computes e =3D H(R | M | X) ....= standard schnorr e... not a share
= 8. Computes e2 =3D H(R | M | X2) ... a second blinding factor
9. Computes si =3D ki *e2 + xi * e ... where si is a "share" of t= he sig, and xi is the private data, and e, e2 are blinding factors
10. Publishes (si, e, e2) as the share sig

The final signature is computed via int= erpolation, and e2 is can be subtracted to recover a "normal" sch= nor sig for the set of participants.

Now there= 's no mechanism for a birthday attack on k.


On Fri, Jul 20, 2018 at 1:34 PM, Erik Aronesty <<= a href=3D"mailto:erik@q32.com" target=3D"_blank" rel=3D"noreferrer">erik@q3= 2.com> wrote:
Hi, thanks for all the help.=C2=A0 =C2=A0I'm going to s= ummarize again, and see if we've arrived at the correct solution for an= M of N "single sig" extension of MuSig, which I think we have.

- Using MuSig's solution = for the blinding to solve the Wagner attack
- Using in= terpolation to enhance MuSig to be M of N instead of M of M

References:

=
=C2=A0- HomPrf http://crypto.stanford.edu/~dabo/papers/homprf.pdf (sections = 7.1 and 7.4)

Each party:

1. Publishes public key G*xi
3. Xi =3D H(G*xi) ... Xi is the parties x coordinate, fo= r the purposes of interpolation
3. r =3D G*x =3D via i= nterpolation of Gx1, Gx2... (see=C2=A0HomPrf)
4. L =3D H(X1,X= 2,=E2=80=A6) (see MuSig)
5. X =3D sum of all H(L,X= i)Xi (see MuSi= g)
6. Computes e =3D H(r | M | X) .... standard= schnorr e... not a share
7. Computes si =3D xi - xe .= .. where si is a "share" of the sig, and xi is the private data
8. Publishes (si, e, G*Xi)

Any party can then derive s from m of n shares, by inter= polating, not adding.




--00000000000030f1ea0571dd6db5--