Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 5D0B7E83 for ; Mon, 9 Jul 2018 17:59:27 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wm0-f47.google.com (mail-wm0-f47.google.com [74.125.82.47]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 8206CE2 for ; Mon, 9 Jul 2018 17:59:26 +0000 (UTC) Received: by mail-wm0-f47.google.com with SMTP id b188-v6so22062155wme.3 for ; Mon, 09 Jul 2018 10:59:26 -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=2TuFV03se2iO2Nud6dIJmr5HUOpQ5VdmFf7fU60l4K4=; b=AYISbW8taIHXbojlyCwZAHeCq4J8TXO6A6Madz7cQHm5uWsaUquW8taBslu31+rRt7 k/mJHxiBSJEUdG3QdeIpgkW1/1M+dXOk7HMPpuYzu9eVEdO58+41wUuSYe+0copKyPJX w+gj3zR05bVb+u9YV6bMO6fQrmQsmO4MlgeLVjrvtlJGp75NVrz4tOqY3/TfKUbFYGxN GvtprynmEqHgeIlfu2WcKcXcMEQRnnqTgBKiVB7JdCR0sYpSsrMiYxsjEMkJvK54I11F BNPlD+cVldThW1iuIaF5rWG+ZljxAclLLCBPBUbtzaaD004S1owmcwS51bT7hfj3LW45 YPDw== 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=2TuFV03se2iO2Nud6dIJmr5HUOpQ5VdmFf7fU60l4K4=; b=TX+tAfH2Lu0rGMxapo/7V9kT957uOVHDNDGZcDu58c7JjgQ4TObw/qau73V/aV5Ycx mK806xnbnEDDjzGDPC6UbcMlI7Hk83UsOAljt/QhG5VIb7zMba0xXZnVoaino4tBsDPL 7ZMnvH6xCSLwqRXdIGKyuxzrVUwzYWvC7vxKHiX+fV8mENGySrjFIx+35TKTurdQtDcy sLfVcSQ0tbjA4RfXBgjFLTzg+3W7tWdlbPTsyo4biDveoNikeidam7wwma0Tp+B2nT1a 0QRNKWQ1eMuY/ShW++T9Uq//MWCcinn7+Rkyttm1cSjRsaxSjKIUx5trwCNKKnFTuBA4 45Ng== 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=2TuFV03se2iO2Nud6dIJmr5HUOpQ5VdmFf7fU60l4K4=; b=HdbcyWPJAukVtFvYe9Gg+cl5NaN7QJLmslF9xES7pImNzSQYpk/pP8ixfwxH7f0qTx DFmqTFGJnvwRNux4rTJCpfS6f3ZCidmrILssqwU5zcq5uHkaHfWyVfWFI9KjRld01rsj yG3TK5wBOAJyauAw0kd2OX4iY7E3pRAk7SA+i5y8O61c7Ozr/N1S8gtS3sVdLJmFr6hC BIWtvuLyfTQBgKIfURtTw5UMRq2xE5tEvArFHb6XapgyDJkm8hYcxQJbbw8hiXjI8l+8 Ens8Ta7d1ab/SYC+JOCXfWyOUd4guCLI7fv7P15nTJgKGEdquJ31d1tNTw3Tux5RR8D5 8zCw== X-Gm-Message-State: APt69E3Gz/JUIaxsdbOsqIHXipQdfb5BdoCv2tni+JWWib+pE1xky+r4 2H2QC277E7uUVsFj1yZQq7Yr1JTi98+9e14lnVNSScZcv5DH X-Google-Smtp-Source: AAOMgpeUbcisFkFlur8vYVYN3Fn67hAqOAhJPatI6ip12hMKa7FHKO7/+LJ/o1QodooOKxzODQupB4FOf6+j5pI/GGs= X-Received: by 2002:a1c:dc41:: with SMTP id t62-v6mr13388549wmg.42.1531159165004; Mon, 09 Jul 2018 10:59:25 -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 10:59:23 -0700 (PDT) In-Reply-To: References: <08201f2292587821e6d23f6cc201d95e6e5ad2cd.camel@timruffing.de> From: Erik Aronesty Date: Mon, 9 Jul 2018 13:59:23 -0400 X-Google-Sender-Auth: 4KcOZ0m3KNl7GApKWywcQ1Pfh-8 Message-ID: To: Gregory Maxwell Content-Type: multipart/alternative; boundary="0000000000001ff48b057094c6a7" 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 17:59:51 +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 17:59:27 -0000 --0000000000001ff48b057094c6a7 Content-Type: text/plain; charset="UTF-8" - Adaptive r choice shouldn't be possible since r is derived from the original threshold prf and it's not possible for a party to have any adaptive impact on the value of r - I'm guess I don't see how an attacker can use adaptive key choice in this context either. Any modification of the key should be useless AH! I forgot to include some assumptions. The important part here is that each party only has a share of the private key and publishes a share of the public key. This hopefully should preclude any sort of adaptive key attack. From scratch: 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, g^x') Verification: With m of n share-signatures: 1. Interpolation on m of n s' shares to get s 2. Interpolation on m of n g^x' shares to get g^x 3. Standard schnorr verification The actual public key of the "set of signers" is interpolated. On Mon, Jul 9, 2018 at 12:58 PM, Gregory Maxwell wrote: > On Mon, Jul 9, 2018 at 4:33 PM, Erik Aronesty wrote: > >>> with security assumptions that match the original Schnorr construction > more closely, > >> More closely than what? > > More closely than musig. > > Musig is instructions on using the original schnorr construction for > multiparty signing which is secure against participants adaptively > choosing their keys, which is something the naive scheme of just > interpolating keys and shares is vulnerable to. It works as > preprocessing on the keys, then you continue on with the naive > protocol. The verifier (e.g. network consensus rules) is the same. > > Now that you're back to using a cryptographic hash, I think what > you're suggesting is "use naive interpolation of schnorr signatures" > -- which you can do, including with the verifier proposed in the BIP, > but doing that alone is insecure against adaptive key choice (and > potentially adaptive R choice, depending on specifics which aren't > clear enough to me in your description). In particular, although it > seems surprising picking your interpolation locations with the hash of > each key isn't sufficient to prevent cancellation attacks due to the > remarkable power of wagner's algorithm. > --0000000000001ff48b057094c6a7 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
=C2=A0- Adaptive r choice shouldn't be possible since = r is derived from the original threshold prf and it's not possible for = a party to have any adaptive impact on the value of r
=C2=A0- I'm g= uess I don't see how an attacker can use adaptive key choice in this co= ntext either.=C2=A0 =C2=A0Any modification of the key should be useless
= AH!

I forgot to include some assumptions.=C2=A0 =C2=A0The im= portant part here is that each party only has a share of the private key an= d publishes a share of the public key.

This hopefully should= preclude any sort of adaptive key attack.

From scratch:

1. Has a public g^x'=
2. Computes and br= oadcasts g^k' ... where k' is a random number
3. Computes r =3D g^k using lagrange int= erpolation (see=C2=A0=C2=A0http://crypto.stanford.edu/~dabo/papers/homprf.pdf)
4. Computes H(r || M= ), as per standard schnorr
5. Computes s' =3D k' - xe=C2=A0, as per standard schnorr .. except k' is a "= ;share"
6. Publish (s', e, g^x')

Verification:

With m of n share-signatures:
=
= 1. Interpolation on m of n s' shares to ge= t s
<= span style=3D"font-size:small;background-color:rgb(255,255,255);text-decora= tion-style:initial;text-decoration-color:initial;float:none;display:inline"= >2. Interpolation on m of n g^x' shares to= get g^x
3. Standard schnorr verificatio= n

The actual public key of the "set of signers" is interp= olated.=C2=A0 =C2=A0



On Mon, Jul 9, 2018 at 12:58 PM, Gre= gory Maxwell <greg@xiph.org> wrote:
On Mon, Jul 9, 2018 at 4:33 PM, Erik Aronesty <<= a href=3D"mailto:erik@q32.com">erik@q32.com> wrote:
>>> with security assumptions that match the original Schnorr cons= truction more closely,
>> More closely than what?
> More closely than musig.

Musig is instructions on using the original schnorr construction for
multiparty signing which is secure against participants adaptively
choosing their keys, which is something the naive scheme of just
interpolating keys and shares is vulnerable to. It works as
preprocessing on the keys, then you continue on with the naive
protocol. The verifier (e.g. network consensus rules) is the same.

Now that you're back to using a cryptographic hash, I think what
you're suggesting is "use naive interpolation of schnorr signature= s"
-- which you can do, including with the verifier proposed in the BIP,
but doing that alone is insecure against adaptive key choice (and
potentially adaptive R choice, depending on specifics which aren't
clear enough to me in your description). In particular, although it
seems surprising picking your interpolation locations with the hash of
each key isn't sufficient to prevent cancellation attacks due to the remarkable power of wagner's algorithm.

--0000000000001ff48b057094c6a7--