Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 6624ABD1 for ; Mon, 9 Jul 2018 15:57:20 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-oi0-f43.google.com (mail-oi0-f43.google.com [209.85.218.43]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id AB81A6BA for ; Mon, 9 Jul 2018 15:57:19 +0000 (UTC) Received: by mail-oi0-f43.google.com with SMTP id 13-v6so36825373ois.1 for ; Mon, 09 Jul 2018 08:57:19 -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; bh=+dAcFW3Yq5xrMAzGvaphD0PlSh0/kMNfVNX2HyE/75Q=; b=QK53DOclZGR46gmUQjqwOe+QyR+QMBuTd5JFY5IZepoYP1CrA3sePwtAPC1MjSxrgt 7cXrXYBumzoKcX0bWVQ6V5MCyLOXWWNHcO/SScKvfR+jIRWiw2uaXhCAo9fbUF2kJU0G AOEGO+VjmIUPGBafNK0ZRlyX1Y2vjA4FiR2YifeCXTPyipQoic/AWAMDp1miy2azSG4m TqjA4erH1+iRlDsz5aJwJ1I5gNqN0cITXF/Dzx9y/JzHRtjmhF/NEYT1Q7aIwrk/+8Qc a0su0VWes8MtVVssw6+f8srBvDEgxBhzHw9ozIqZbSivsrWiMrvtDPqYts1/O6LFyhJ/ /1Mg== 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=+dAcFW3Yq5xrMAzGvaphD0PlSh0/kMNfVNX2HyE/75Q=; b=kS55UkAY8KEgT4C7sSEYf6IHkytyUOfqOsgdrERRX40X8MXW6HtL6XE+/qJ1rGP5/V K56QYKDtUz3aX+CeqcOQqZsV1S7hM7+eCy7V/6U3UeDBEh1fW5cWSwUJPAKC0Q1DE989 JzmR0MWLChJyJHo63++ScNykEIxqF2N1ikUrpHf4ejRw2+Piq72k5EWJRb0CDlQa7VWy Y2QxXqvMKFN0Ag1QBOcBCTtrPF2Mou5CceRhueIs7hqudg2kxtV/ln6Df8V7UFOVWvao LDqwjTgzlBWPLIr2bOFQmotb9+hEoLJsJGi9HFlw2UXIQb5GwlTzS4nvcNsS9GD+HKft 7pRQ== X-Gm-Message-State: APt69E2JQMG5Tt5j7XbfmU29aiZK8hX5/GQ7bP4s/diiYiyxqowMnYZw 8efLd7jChE358+V1djOSUSHJgdoP3s+ZtoQaTXc= X-Google-Smtp-Source: AAOMgpeCdenlNu6393i2GzUYpSSphL94ocn6RGOGJn/zqxQgxRqZLs0GH3rMNAIO3tWEXkDjZQVSaS7q/73y1J5CPgc= X-Received: by 2002:aca:efd7:: with SMTP id n206-v6mr25407129oih.70.1531151838757; Mon, 09 Jul 2018 08:57:18 -0700 (PDT) MIME-Version: 1.0 References: <08201f2292587821e6d23f6cc201d95e6e5ad2cd.camel@timruffing.de> In-Reply-To: From: Dan Robinson Date: Mon, 9 Jul 2018 11:57:07 -0400 Message-ID: To: Erik Aronesty , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000724cc30570931147" X-Spam-Status: No, score=-1.7 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM, HTML_MESSAGE,RCVD_IN_DNSWL_NONE autolearn=no version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Mon, 09 Jul 2018 16:34:20 +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: Mon, 09 Jul 2018 15:57:20 -0000 --000000000000724cc30570931147 Content-Type: text/plain; charset="UTF-8" Can you please clarify which terms in that description are elliptic curve points, and which are scalars? On Mon, Jul 9, 2018 at 11:10 AM Erik Aronesty via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Actually, it looks like in order to compute a multiparty signature you > will need to broadcast shares of r first, so it's not offline :( > > It is still seems, to me, to be a simpler mechanism than musig - with > security assumptions that match the original Schnorr construction more > closely, and should therefore be easier to prove secure in a multiparty > context. > > Shamir/Schnorr threshold multi-signature scheme: > > Each party: > > - Has a public key g*x', where x' is their private key, and where H(g*x) > can be considered their public index for the purposes of Shamir polynomial > interpolation > - Rolls a random k' and compute r' = g*k' > - Broadcast r' as a share > - Computes g*k, via lagrange interpolation across shares. At this point > k is not known to any party unless Shamir is vulnerable or DL is not hard > - Computes e' = H(M) * r' > - Computes s' = k'-x*e' > - Share of signature is (s', e') > > Verification is the same as Scnhorr, but only after using interpolation to > get the needed (s, e, g*x) from shares of s', e' and g*x': > > - Using lagrange interpolation, compute the public key g*x > - Again, using lagrange interpolation, compute (s, e) > - Verify the signature as per standard Schnorr > > Security assumptions: > > - Because this is not additive, and instead we are using Shamir > combination, the additional blinding and masking steps of musig are not > needed to create a secure scheme. > - The scheme is the same as Schnorr otherwise > - The only thing to prove is that H(M) * r does not reveal any > information about k ... which relies on the same DL assumptions as Bitcoin > itself > - Overall, this seems, to me at least, to have a smaller attack surface > because there's fewer moving parts > > > On Mon, Jul 9, 2018 at 8:24 AM, Erik Aronesty wrote: > >> I was hoping that nobody in this group saw an obvious problem with it >> then I'd sit down and try to write up a paper. >> >> Not that hard to just reuse the work done on schnorr. And demonstrate >> that there are no additional assumptions. >> > >> On Mon, Jul 9, 2018, 12:40 AM Pieter Wuille >> wrote: >> >>> On Sun, Jul 8, 2018, 21:29 Erik Aronesty wrote: >>> >>>> Because it's non-interactive, this construction can produce multisig >>>> signatures offline. Each device produces a signature using it's own >>>> k-share and x-share. It's only necessary to interpolate M of n shares. >>>> >>>> There are no round trips. >>>> >>>> The security is Shamir + discrete log. >>>> >>>> it's just something I've been tinkering with and I can't see an obvious >>>> problem. >>>> >>>> It's basically the same as schnorr, but you use a threshold hash to fix >>>> the need to be online. >>>> >>>> Just seems more useful to me. >>>> >>> >>> That sounds very useful if true, but I don't think we should include >>> novel cryptography in Bitcoin based on your not seeing an obvious problem >>> with it. >>> >>> I'm looking forward to seeing a more complete writeup though. >>> >>> Cheers, >>> >>> -- >>> Pieter >>> >>> >>> _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > --000000000000724cc30570931147 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Can you please clarify which terms in that description are elliptic curve p= oints, and which are scalars?
On Mon, Jul 9, 2018 at 11:10 AM Erik Aronesty via bitcoin-dev <bitcoin-dev@lists.linuxfo= undation.org> wrote:
Actually, it looks like in order to compute a multiparty sig= nature you will need to broadcast shares of r first, so it's not offlin= e :(

It is still seems, to me, to be a simpler mec= hanism than musig - with security assumptions that match the original Schno= rr construction more closely, and should therefore be easier to prove secur= e in a multiparty context.

Shamir/Schnorr threshol= d multi-signature scheme:

Each party:

- Has a public key g*x', where x' is their private= key, and where H(g*x) can be considered their public index for the purpose= s of Shamir polynomial interpolation
- Rolls a random k' and = compute r' =3D g*k'
- Broadcast r' as a share
- Computes g*k, via lagrange interpolation across shares.=C2=A0 =C2= =A0At this point k is not known to any party unless Shamir is vulnerable or= DL is not hard
- Computes e' =3D H(M) * r'
- C= omputes s' =3D k'-x*e'
- Share of signature is (s'= ;, e')

Verification is the same as Scnhorr, bu= t only after using interpolation to get the needed (s, e, g*x) from shares = of s', e' and g*x':

- Using lagrange interpolation, compute the public key g*x<= /div>- Again, using lagrange interpolation, compute (s, e)=C2=A0
= - Verify the signature as per standard Schnorr

Sec= urity assumptions:

=C2=A0- Because this is not= additive, and instead we are using Shamir combination, the additional blin= ding and masking steps of musig are not needed to create a secure scheme.= =C2=A0=C2=A0
=C2=A0- The scheme is the same as Schnorr otherw= ise
=C2=A0- The only thing to prove is that H(M) * r does not rev= eal any information about k ... which relies on the same DL assumptions as = Bitcoin itself
=C2=A0- Overall, this seems, to me at least, to ha= ve a smaller attack surface because there's fewer moving parts
=C2=A0

On Mon, Jul 9, 2018 at 8:24 AM, Erik Aronesty <erik@q32.com> w= rote:
I was hoping that= nobody in this group saw an obvious problem with it then I'd sit down = and try to write up a paper.=C2=A0=C2=A0

Not that hard to just reuse the work done on schnorr.=C2=A0 =C2= =A0And demonstrate that there are no additional assumptions.

On Mon, Jul 9, 2018, 12:40 AM Pieter Wuille <pieter.wuille@gmail.com= > wrote:
On Sun, Jul 8, 2018, 21= :29 Erik Aronesty <erik@q32.com> wrote:
Because it's non-interactive, this construct= ion can produce multisig signatures offline.=C2=A0 =C2=A0Each device produc= es a signature using it's own k-share and x-share.=C2=A0 =C2=A0It's= only necessary to interpolate M of n shares.

There are no round trips.

The security is Shamir + discrete log.=C2=A0=C2=A0

it's just = something I've been tinkering with and I can't see an obvious probl= em.=C2=A0=C2=A0

It's= basically the same as schnorr, but you use a threshold hash to fix the nee= d to be online.

Just see= ms more useful to me.

That sounds very useful if true, but I d= on't think we should include novel cryptography in Bitcoin based on you= r not seeing an obvious problem with it.

<= div dir=3D"auto">I'm looking forward to seeing a more complete writeup = though.

Cheers,

--=C2=A0
= Pieter


_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--000000000000724cc30570931147--