Re: [bitcoin-dev] Multiparty signatures

[Erik Aronesty <erik@q32.com>]

[-- Attachment #1: Type: text/plain, Size: 2302 bytes --]

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 <erik@q32.com> 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 <adam.back@gmail.com> 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
>>
>
>

[-- Attachment #2: Type: text/html, Size: 3551 bytes --]