From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 09A61D28 for ; Wed, 11 Jul 2018 10:35:22 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-oi0-f44.google.com (mail-oi0-f44.google.com [209.85.218.44]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 9BEAF334 for ; Wed, 11 Jul 2018 10:35:21 +0000 (UTC) Received: by mail-oi0-f44.google.com with SMTP id k81-v6so48333027oib.4 for ; Wed, 11 Jul 2018 03:35:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:reply-to:from:date:message-id :subject:to:cc; bh=UnyKHb/7T1e9sbllKsd+Ur8a340qDrZUM22k8luAqs0=; b=aTbP8CtdYJPFH1Zh9y7a8YPY9WfGo2f7grEupaWzj3EnslXlaXFgOqkfpoRLr+qDSt qyqjRLCZRrSW/YIQdSix8Z0Q4oElPMk3viqhXxF6lr0K6OEoFB58eaBymfQMi9HvrC3I p/5pWflwSwNu/BkE098K6wx+YOZi9vo6qoV+rL6jNQLjfS1xSJjnDJ+OtGxbrmF2VFcu XzyyZ4D9dFktwKTCb9t6aXlc63nOTF9LndScAu5D+4e1d2PDDM8fMtI9JeenChrKqQ8/ aOsGjXXYW0O3QrUqtb5GuK+jsRTysVhK+giAFpxRhBQQSO9AEEWaqiVSDfwLxGS5N4wZ AvdA== 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:reply-to :from:date:message-id:subject:to:cc; bh=UnyKHb/7T1e9sbllKsd+Ur8a340qDrZUM22k8luAqs0=; b=G72OuJBHuZTy/3VFhUos1xsjuBtY9zpHIcdigSKprtqO0HPdmUCM+ttjB7MrVkC/oz bqB6QSinqF/PgAbYMbG4gR0NFqMWHALHHPCA9qAJaBIOBtDjmTg5gDcxTxxlVgmnaQ23 +V9+wAQ/x6kh1vCUdKOL2UV1HGgAKSODaxfVqR1DsPds5F3I01DazZXmeHPGt+d/j5Nr JeHVrDDIVBcpVTYRho25feLN/iOnJXX30Rl3EPuqlaC9171YxMMazrFIo4nP+1HXeOLd 8eI7iC6O/W6KK+frsOaDIvFATy/GLAhNeiBmJlVMeqIS8+VohS6/VRQ0Q27XwqLIHauk cx1Q== X-Gm-Message-State: APt69E0oK9SwmEm5xruKMWWg5L34fHRFUQI34QBBLdjfWwkxycyOQWCm akr8P6Tr8RN51is8PJLpCpllHDlW55BCFuB4WG8= X-Google-Smtp-Source: AAOMgpe/dEfJJKSZfwvDf0xI1gczh0RpRCVHZghK/am6IuSdMHY3Y3/m7ww7O7rMYo37g0sH/U/NVOANbXJX80ii39g= X-Received: by 2002:aca:a982:: with SMTP id s124-v6mr32154717oie.80.1531305320844; Wed, 11 Jul 2018 03:35:20 -0700 (PDT) MIME-Version: 1.0 References: <08201f2292587821e6d23f6cc201d95e6e5ad2cd.camel@timruffing.de> In-Reply-To: Reply-To: adam@cypherspace.org From: Adam Back Date: Wed, 11 Jul 2018 11:35:08 +0100 Message-ID: To: Erik Aronesty , Bitcoin Dev Content-Type: multipart/alternative; boundary="000000000000b1147a0570b6cd6b" X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, 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 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: Wed, 11 Jul 2018 10:35:22 -0000 --000000000000b1147a0570b6cd6b Content-Type: text/plain; charset="UTF-8" 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 --000000000000b1147a0570b6cd6b Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Wed,= Jul 11, 2018, 02:42 Erik Aronesty via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org<= /a>> wrote:
> Basical= ly you're just replacing addition with interpolation everywhere in the = musig construction=C2=A0

Yes, but you can't do that without a delinearization mechanism to pre= vent 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 del= inearization mechanism for an intuition, all public keys are hashed along w= ith per value hash, so that pre-commits and forces the public keys to be no= n-adaptively chosen.=C2=A0

Adaptively chosen public keys are dangerous and simple to exploit for ex= ample pub keys A+B, add party C' he chooses C=3DC'-A-B, now we can = sign for A+B+C using adaptively chose public key C.
=
Btw Wagner also breaks this earlier delineariza= tion scheme S=3DH(A)*A+H(B)*B+H(C)*C

Adam
--000000000000b1147a0570b6cd6b--