Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 562A6C3A for ; Thu, 19 Jul 2018 12:24:54 +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 5B3FC784 for ; Thu, 19 Jul 2018 12:24:53 +0000 (UTC) Received: by mail-wm0-f44.google.com with SMTP id h20-v6so6166631wmb.4 for ; Thu, 19 Jul 2018 05:24:53 -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 :cc; bh=WZxiYH8jkzpvNaSbv7q4mXieujmKQpM3gu/v0djgsKU=; b=Pl3/6CCwmQXbKJnrU2ZibKrku+QXgG/nKcY0x8iq9f/Vb9wcz5o06Z/9T80ibGsIyx CzazOX7gdPjVCk7eK6RShj8nW8hLAtXQUIQolKCl8/5zrlUv2txMCk+wpmjIHyNr9CWi zZySJ6xshI8v0JHqZJiD8zdz1BGRDnMkCFYJUVGvLSU7zBf+y7rM+/ez/JvDln1GaXN0 I7IgUUiwerGUnrnwjGAmRG+q7uE2PEobXonphc+5OE0aB0RPdiK6alLYmErGyVPEwPYf VdnTgTdq0zwBpaXaigzf51GUTxfeKdYOlzkry4HKI24mIwJt5wd0vBFLrfS6+TQ0hMPm OsTg== 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:cc; bh=WZxiYH8jkzpvNaSbv7q4mXieujmKQpM3gu/v0djgsKU=; b=IX5SDwvy3plII3/M7QcDJfs+8Z7zWN/YGznhFqfdiJ8MHTtTrdtfZ8HVu3QAHfyfmp oZL32uENAziPSRNuw1mzBUHUi0ZdzClgQbN46Cmaq3r7xv5Mor8V7IyQw7nGB5mWHc7X RONqwGUW/K170m5k8UyrZDgEa4gWl4iWtb1udN5aCtz8Os2vh6wuM3Sgoj49GATP9gPi bNYVfTqhk7D3THt6JFc8BKzKk4GYEQdGVLoAFWgEeJq/q83LjlownOk9d+lBAXjjALqE 7ZRH0aoKoq0Lm6ENmW97Yrl7PEVHz5TcrnHXVjNx7JwwWIbZ6eN6iQ3cS5rQIL1ScTOo XzZw== X-Gm-Message-State: AOUpUlHk3R7LutO4FtXYHERR/VQdBV9LSmfHokvUM8XiloeIjvpaZv6S VkCcyKdVhPOQwxi2OJbarmEvjXKxpF/sT3LZFfUFVBVC1Q== X-Google-Smtp-Source: AAOMgpdmOrazoIs0C/iQ2x0OxvF6sF2rtPkQGBdYQ/dAUDRtTFiULENgJir46qJr2l6R4GgzdLbTnOJ2iRmnv7piQtQ= X-Received: by 2002:a1c:8952:: with SMTP id l79-v6mr3904764wmd.7.1532003091836; Thu, 19 Jul 2018 05:24:51 -0700 (PDT) MIME-Version: 1.0 References: <08201f2292587821e6d23f6cc201d95e6e5ad2cd.camel@timruffing.de> In-Reply-To: From: Erik Aronesty Date: Thu, 19 Jul 2018 08:24:39 -0400 Message-ID: To: adam@cypherspace.org Content-Type: multipart/alternative; boundary="000000000000157453057159441b" 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, 19 Jul 2018 12:51:32 +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: Thu, 19 Jul 2018 12:24:54 -0000 --000000000000157453057159441b Content-Type: text/plain; charset="UTF-8" Probably because my descriptions are a bit vague and rambling. but I can't help but think that a SMC of a bitcoin private key, followed by a secure multiparty computation of a signature is going to be more secure overall. I couldn't figure out how to do it offline. But one round of exchange seems to work. It comes down to the blinding factor (k). All parties need to agree to it ... which creates the second round. On Thu, Jul 19, 2018, 8:16 AM Erik Aronesty wrote: > Also Wagner's algorithm shouldn't be applicable for a number of reasons. > you can't birthday attack something where there's only a single variable > that you can modify. And when you change the equation from additive you > now have a multi-dimensional equation we're partitioning won't function. > this is the basis of the perfect security of Shamir secret sharing. > > On Wed, Jul 11, 2018, 10:45 AM Erik Aronesty wrote: > >> OK, so you're going with this scenario: >> >> 1. I know Apub and Bpub, >> 2. I know M is 3 >> 3. I'm choosing a random number for C's private key >> >> Cpub is g^C >> >> The equation I am solving for .. and trying to factor myself out of is >> g^Ax + g^B*2 + g^C*3 >> >> I don't know A or B... I only know their public keys. >> >> I don't think it's possible to adaptively choose C for an attack on the >> multisig construction, when using hash of the public key as the X >> coordinate in the polynomial, because in order to satisfy the equation and >> factor out C, you would need to be able to break the hash. >> >> With an additive construction, yes... adaptive attacks are possible. >> But in a shamir secret sharing interpolation, you need a public X >> coordinate as well as a secret share. Choosing hash(pub) as X, prevents >> this attack. >> >> >> On Wed, Jul 11, 2018 at 6:35 AM, Adam Back wrote: >> >>> On Wed, Jul 11, 2018, 02:42 Erik Aronesty via bitcoin-dev < >>> bitcoin-dev@lists.linuxfoundation.org> wrote: >>> > Basically you're just replacing addition with interpolation everywhere >>> in the musig construction >>> >>> Yes, but you can't do that without a delinearization mechanism to >>> prevent adaptive public key choice being used to break the scheme using >>> Wagner's attack. It is not specific to addition, it is a generalized >>> birthday attack. >>> >>> Look at the delinearization mechanism for an intuition, all public keys >>> are hashed along with per value hash, so that pre-commits and forces the >>> public keys to be non-adaptively chosen. >>> >>> Adaptively chosen public keys are dangerous and simple to exploit for >>> example pub keys A+B, add party C' he chooses C=C'-A-B, now we can sign for >>> A+B+C using adaptively chose public key C. >>> >>> Btw Wagner also breaks this earlier delinearization scheme >>> S=H(A)*A+H(B)*B+H(C)*C >>> >>> Adam >>> >> >> --000000000000157453057159441b Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Probably because my descriptions are a bit vague and ramb= ling.

but I can't help but= think that a SMC of a bitcoin private key, followed by a secure multiparty= computation of a signature is going to be more secure overall.

I couldn't figure out how to do= it offline.=C2=A0 But one round of exchange seems to work.

It comes down to the blinding factor = (k).=C2=A0 All parties need to agree to it ... which creates the second rou= nd.

On Thu, Jul = 19, 2018, 8:16 AM Erik Aronesty <erik@q3= 2.com> wrote:
Also Wagner's algorithm shouldn't be applicable for a number of= reasons.=C2=A0 you can't birthday attack something where there's o= nly a single variable that you can modify.=C2=A0 =C2=A0 And when you change= the equation from additive you now have a multi-dimensional equation we= 9;re partitioning won't function.=C2=A0 this is the basis of the perfec= t security of Shamir secret sharing.

On Wed, Jul 11, 2018, 10:45 AM Erik Aronesty <erik@q32.com&= gt; wrote:
OK, so = you're going with this scenario:

1. I know Apub = and Bpub,
2. I know M is 3
3. I'm choosing a random= number for C's private key

Cpub is g^C
<= div>
The equation I am solving for .. and trying to factor my= self out of is g^Ax + g^B*2 + g^C*3

I don't kn= ow A or B... I only know their public keys.

I don&= #39;t think it's possible to adaptively choose C for an attack on the m= ultisig construction, when using=C2=A0hash of the public key as the X coord= inate in the polynomial, because in order to satisfy the equation and facto= r out C, you would need to be able to break the hash.

<= div>With an additive construction, yes... adaptive attacks are possible.=C2= =A0 =C2=A0But in a shamir secret sharing interpolation, you need a public X= coordinate as well as a secret share.=C2=A0 =C2=A0Choosing hash(pub) as X,= prevents this attack.


On Wed, Jul 11, 2018 at 6:35 AM, Adam Back = <adam.back@gmail.com> wrote:=
On Wed, Jul 11, 2018, 02:42 Erik Aronesty= via bitcoin-dev <bitcoin-dev@lists.linuxf= oundation.org> wrote:
> Basically you're just replacing addition with interpolation ever= ywhere in the musig construction=C2=A0

Yes, but you can't do that without a delineariza= tion mechanism to prevent adaptive public key choice being used to break th= e scheme using Wagner's attack. It is not specific to addition, it is a= generalized birthday attack.

Look at the delinearization mechanism for an intuition, all public ke= ys are hashed along with per value hash, so that pre-commits and forces the= public keys to be non-adaptively chosen.=C2=A0

=
Adaptively chosen public keys are dangerous and sim= ple to exploit for example pub keys A+B, add party C' he chooses C=3DC&= #39;-A-B, now we can sign for A+B+C using adaptively chose public key C.

Btw Wagner also breaks thi= s earlier delinearization scheme S=3DH(A)*A+H(B)*B+H(C)*C

Adam
<= /div>

--000000000000157453057159441b--