Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 4A128D5D for ; Mon, 9 Jul 2018 16:33:06 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wr1-f53.google.com (mail-wr1-f53.google.com [209.85.221.53]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 95F8878D for ; Mon, 9 Jul 2018 16:33:03 +0000 (UTC) Received: by mail-wr1-f53.google.com with SMTP id g6-v6so2735911wrp.0 for ; Mon, 09 Jul 2018 09:33:03 -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:cc; bh=BOoo02vh90v4RkLcjyw5VvBuMVCvbdJ96wsoKKAUd9A=; b=JDra/zHR1qpgWnuz24ylTZ19Yx/6TEuXxaNB2nwl2IyZyaAtx0bWzFzvi9ixQiZZKa 0O2F6dF/g5yKwS1Xmum5BUb0d6/vXP4C5cgsyeIzzh0kieEBhGUFjlrNXJfOSobcai1g h4vvvzePn1ekORMZ0MrveMVYr80igcc6AvKXiPqocrUEOTw27Rz4eAAJ3DHgyDq83QL8 DHLsSRbZMzgfAXxDBj49Z6owg3g1JwjI8AqTFCv3kUZMEJmvtTfgkmY+iTFDSaGUjwTi aVlqPcUbJisexqBp61zGammh600/Zq8iy7QiFKAj+XeVnULBRGekHyZLLYGr8na5K1+i poXw== 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:cc; bh=BOoo02vh90v4RkLcjyw5VvBuMVCvbdJ96wsoKKAUd9A=; b=tSLLo4Btvsx4ZKNbwSSB+XJkEwNHe06UCPnl7bI0DDdKE4KejcUROIiY/bWJIR/XAg dKenJe7fLqgqfe4WRO1ZIrixn63lI2xnXHpVG690PeT0xGcRyqR2kvclMLKmMUphs8pq YbIAECrOLYK9KUiGHWJjuDX2IHSJG4Mk2UBu8DOodpObsQRVum8Yy13YG3Cusu+0p32V oEBHqzULylU2R38FU+qTpZB71tLrfV02YSKkig4icF3KX4C5wONqPv4ygeorjSsfcyhD JBx2HxyNgM17BqyUfmRBhmOeeWCif8qfvPRdlfjyMU2sFBukt4zSlI1VbqY4GwR8+kR4 zoIw== 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:cc; bh=BOoo02vh90v4RkLcjyw5VvBuMVCvbdJ96wsoKKAUd9A=; b=ElNoHyJutWu1yp3IlRxSFKEKLWEiUD5mJ0Lp9I0RNljyuwa36qObFsQnRiXMrn+IFH 6C0OEbgUksBm0dWqjFOg5FHB7oMTbvLEPZJ2aBzKbcnhjsmDA42sikmFGrJNLxQOOqXC OCpr8JxvVgMIcYNKLmcYfaW1F8FKgm2HWl9LSptA90BPe159hPpGi3emK+VI6hqu4tUt Zw9i+uy6b+SN0qC/NS2KYD71ElB2cwPhxw8IbOf/h958AxdArRyChJqLaJCKtPO+yTMn cBYNR9yhVQJ34gbCPvmQkFcP0eL5Ttufp34t0MEAuGFCR7XBPPiPcaf43u7zNYDXTnwh tfJA== X-Gm-Message-State: APt69E19KoVGm8kpJ5vMmMFSAADCpXeqoe33Z96kOYIV2GnHT0pDZQwr Ahzne+LZhUMw5S+BA9FMinr7H96kEnXlYpU8u7o+0FM= X-Google-Smtp-Source: AAOMgpe5SJ8s8Y3Jd3JU+XbivDDzKxOEuB43ZN/8YCE6tORyAQFbbvhHSJeYQ4yRnmgqHoTPN22+Spxb63R0NPTT1ys= X-Received: by 2002:adf:9d1c:: with SMTP id k28-v6mr16251762wre.29.1531153982115; Mon, 09 Jul 2018 09:33:02 -0700 (PDT) MIME-Version: 1.0 Sender: earonesty@gmail.com Received: by 2002:a1c:b786:0:0:0:0:0 with HTTP; Mon, 9 Jul 2018 09:33:01 -0700 (PDT) In-Reply-To: References: <08201f2292587821e6d23f6cc201d95e6e5ad2cd.camel@timruffing.de> From: Erik Aronesty Date: Mon, 9 Jul 2018 12:33:01 -0400 X-Google-Sender-Auth: XGgsM8lAxD4xafvg61uBCXqgVgA Message-ID: To: Gregory Maxwell Content-Type: multipart/alternative; boundary="000000000000336246057093912d" 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: Mon, 09 Jul 2018 16:34:09 +0000 Cc: Bitcoin Protocol Discussion 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 16:33:06 -0000 --000000000000336246057093912d Content-Type: text/plain; charset="UTF-8" > More closely than what? More closely than musig. In fact there's no need to distribute the hash at all if you have the first round, you can leave the schnorr construction... thanks for the feedback. I literally can't think about this stuff without someone asking questions. 1. For those who asked, the construction from section 7.1 of this paper describes how to use lagrange interpolation in a group context: http://crypto.stanford.edu/~dabo/papers/homprf.pdf 2. Using shamir interpolation is cleaner than the additive multisig 3. Taking your comments into consideration, I think it's possible to remove the point multiplication instead of a hash and stick to Schnorr "as is", and still cut out all but one online round: OK, so this is a new Multisig variant of schnorr with fewer rounds... I know this is possible, I just needed to have that back and forth... sorry: For sake of terminology and typing in ascii, I'm using ^ to mean "point multiplcation" Each party: 1. Has a public g^x 2. Computes and broadcasts g^k' ... where k' is a random number 3. Computes r = g^k using lagrange interpolation (see http://crypto.stanford.edu/~dabo/papers/homprf.pdf) 4. Computes H(r || M), as per standard schnorr 5. Computes s' = k' - xe , as per standard schnorr .. except k' is a "share" 6. Publish (s', e) Verification: With m of n share-signatures: 1. Use lagrange interpolation on m of n s' shares to get s 2. Standard schnorr verification - Erik On Mon, Jul 9, 2018 at 11:59 AM, Gregory Maxwell wrote: > On Mon, Jul 9, 2018 at 3:02 PM, Erik Aronesty via bitcoin-dev > wrote: > > with > > security assumptions that match the original Schnorr construction more > > closely, > > More closely than what? > --000000000000336246057093912d Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
> More closely than what?<= div class=3D"gmail-m_8217130892002629636gmail-yj6qo" style=3D"font-size:12.= 8px;text-decoration-style:initial;text-decoration-color:initial">

M= ore closely than musig.=C2=A0 =C2=A0

In fact there= 's no need to distribute the hash at all if you have the first round, y= ou can leave the schnorr construction... thanks for the feedback.=C2=A0 I l= iterally can't think about this stuff without someone asking questions.=

1. For those who asked, the construction from sec= tion 7.1 of this paper describes how to use lagrange interpolation in a gro= up context:

2. Using shamir interpolatio= n is cleaner than the additive multisig

3. Taking = your comments into consideration, I think it's possible to remove the p= oint multiplication instead of a hash and stick to Schnorr "as is"= ;, and still cut out all but one online round:

OK,= so this is a new Multisig variant of schnorr with fewer rounds... I know t= his is possible, I just needed to have that back and forth... sorry:

For sake of terminology and typing in ascii, I'm using = ^ to mean "point multiplcation"

Each party:

1. Ha= s a public g^x=C2=A0
2. Computes and broadcasts g^k' ... wher= e k' is a random number
3. Computes r =3D g^k using lagrange = interpolation (see=C2=A0 http://cry= pto.stanford.edu/~dabo/papers/homprf.pdf)
4. Comput= es H(r || M), as per standard schnorr
5. Computes s'= =3D k' - xe , as per standard schnorr .. except k' is a = "share"
6. P= ublish (s', e)
Verification:=

With m of n share-signatures:

1. Use lagrange interpolation on m of n s' shares = to get s
2. Standard s= chnorr verification

- Erik




On Mon, Jul 9, 2018 at 11:59 AM, G= regory Maxwell <greg@xiph.org> wrote:
On Mon, Jul 9, 2018 at 3:02 PM, Erik Aronesty via = bitcoin-dev
<bitcoin-dev@li= sts.linuxfoundation.org> wrote:
> with
> security assumptions that match the original Schnorr construction more=
> closely,

More closely than what?

--000000000000336246057093912d--