Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 3E37AC77 for ; Fri, 20 Jul 2018 20:18:51 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wm0-f53.google.com (mail-wm0-f53.google.com [74.125.82.53]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 20A864FA for ; Fri, 20 Jul 2018 20:18:50 +0000 (UTC) Received: by mail-wm0-f53.google.com with SMTP id o11-v6so10502088wmh.2 for ; Fri, 20 Jul 2018 13:18:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to; bh=QerNuAPlXmedDTjuePUSh3MdEHW3elJzbN/t4fu/PUc=; b=t3JqOyP1yRiA4WMdPH8r9+G6d+gAxp348BWU1jaak9PBnpY2afCKwK33Hohk2oYfB2 eCkiWgN5s463cmlQVa4H2Dze+wdjb9SjgGWcB+JljH6/e3KXwCw8GjzDleTBEttbjauY 5aIZZn7lGphzMIZsfD0nyQ8ZV2AT9+6Qh8KcGJzkqimnFIhSOJLIQN1l+mEpv3XFpkxr EFISLythoSmvRjjYyNDTVQjbs52a05GQ+ODh3SnjCsLfRdqG/rrh4VTJdDYgVyNFl6Oh GORhZI+WLaS+OKhnCyKUPhhclTAQOWirbL+094ItXDGHukKFmEyW3XUFDeOvA8xewrbM a0bQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=q32-com.20150623.gappssmtp.com; s=20150623; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to; bh=QerNuAPlXmedDTjuePUSh3MdEHW3elJzbN/t4fu/PUc=; b=IWyh1j7pRhoWD7BojJWTZmI3W3IWvX5RzxLl5CuIHzRM8DmHis2iz2BUyXUZSRRecI 7Pfy53x1AqXY1quNHJTTgy7htMkN3GMb66LH+oyICN2O/FUFhCbDkfXdA5KUmezn3KRP 97o/KlyY2lmnzNVolhqyYnueWYol32zQGJYvkA1KOpUXCvpmGsQKUHkYA5GWRJg6upAb QTJjdq5zVmsJUr35Wgb1MnuM5W5rQp1ArFfYruO+BVOKTQd1VJEWTY5ymwDN4GRHFQpZ 4aQwYcCBHQXOA4AG8lb1CNTRqtoJA2pN9KxXqAE9YS4w8RYa/ODHDO7XngTirhS03x4W 2/+g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to; bh=QerNuAPlXmedDTjuePUSh3MdEHW3elJzbN/t4fu/PUc=; b=ovImbB7iagz/s52IvWkrTNq0GV/RaIrkoBc26VxkMj8k7mQHWvzKPMPb0BriAxsrhM YfLL+o4lDMG1RTPqgQUUkLN2smlDUbNhxqcCbFm/E+XxTygjYJ5mexwdGb3U+iSQ9A7a ybWKSxpnvcKKOYjDlpCUBlr0WI1Y1ozAdrvvY+B1UPTnEGub7fljsvrbKz6s2XQPuIzO b9inSxv9Enbg9IvlDBJBW24qwfYLuTyCWsjV6PW0cWjQOWnbNmHAXMhS0V+Aeg9aZ1cw RAaNagVUxQPlikqervtIxookykfZX1BvKlYgzjqSRx2p/tqWoYZAfvZI7fcHHGWPUBUK 9ffw== X-Gm-Message-State: AOUpUlFrmInqZ3sHRtBkEhQ3RCnzvaVdQGnGCaECxebTWxk5ZpVnjq4A Mmx+Y5sWALNh0Uxspb2vUoM9FpsND5+rvKKIcTtbmCIOx/tJ X-Google-Smtp-Source: AAOMgpfDpuhq11JVk6lnoi1I8WB0gGTT5xQuYD31GLiBR1IxuOxJfG1COJ9yW7hgomEETpuvH2ajT2lGDLH+9AgJsv4= X-Received: by 2002:a1c:c019:: with SMTP id q25-v6mr2310904wmf.148.1532117928301; Fri, 20 Jul 2018 13:18:48 -0700 (PDT) MIME-Version: 1.0 Sender: earonesty@gmail.com Received: by 2002:a1c:b786:0:0:0:0:0 with HTTP; Fri, 20 Jul 2018 13:18:47 -0700 (PDT) In-Reply-To: References: <08201f2292587821e6d23f6cc201d95e6e5ad2cd.camel@timruffing.de> From: Erik Aronesty Date: Fri, 20 Jul 2018 16:18:47 -0400 X-Google-Sender-Auth: mpqCRoOux2jiH-ZCrOhoF7ZYCXE Message-ID: To: Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000dedb5505717400eb" 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: Sun, 22 Jul 2018 12:50:59 +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: Fri, 20 Jul 2018 20:18:51 -0000 --000000000000dedb5505717400eb Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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-signatures.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, 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 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, an= d 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" extensio= n > 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-signatures.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 of > 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 i= s > the private data > 8. Publishes (si, e, G*Xi) > > Any party can then derive s from m of n shares, by interpolating, not > adding. > > > > --000000000000dedb5505717400eb Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
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- MuSig https://blockstream.com/2= 018/01/23/musig-key-aggregation-schnorr-signatures.html
=C2=A0- HomPrf http://crypto.stanford.edu/~d= abo/papers/homprf.pdf (sections 7.1 and 7.4)

<= /div>
Each party:

1. Publishes public key G*xi, G*ki, wh= ere 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= =C2=A0HomPrf)
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
<= div style=3D"font-size:small;text-decoration-style:initial;text-decoration-= color:initial">7. Computes si =3D ki *e+ xi * e ... where si is a "sha= re" of the sig, and xi is the private data, and e is the blinding fact= or
8. Publishes (si, e) as the share sig
=

If an attacker has multiple devices, e is sa= fe, because of the musig construction.

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">erik@q32.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.stan= ford.edu/~dabo/papers/homprf.pdf (sections 7.1 and 7.4)

Each party:

<= /div>
1. Publishes public key G*xi
3. X= i =3D H(G*xi) ... Xi is the parties x coordinate, for the purposes of inter= polation
3. r =3D G*x =3D via interpolation of Gx1, Gx= 2... (see=C2=A0HomPrf)
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 sha= re
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.




--000000000000dedb5505717400eb--