Re: [bitcoin-dev] Schnorr signatures BIP

[Erik Aronesty <erik@q32.com>]

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

Greg,

I added, stripped out, and added analogous musig delinearization 3 times in
response to stuff posted here.  I'm adding it back now. Not sure why my
head is thick around that issue.

The security advantages of a redistributable threshold system are huge.
If a system isn't redistributable, then a single lost or compromised key
results in lost coins... meaning the system is essetntially unusable.

I'm actually worried that Bitcoin releases a multisig that encourages loss.




On Tue, Sep 11, 2018 at 1:00 PM Gregory Maxwell <greg@xiph.org> wrote:

> On Tue, Sep 11, 2018 at 4:34 PM Erik Aronesty <erik@q32.com> wrote:
>
>> To answer points:
>>
>> - I switched to the medium article so that I could correct, edit and
>> improve things to make them more clear.
>> - I responded to feedback by modifying the protocol to make it work - not
>> by ignoring it.
>>
>
> To this moment there remains no response at your post.
> https://bitcointalk.org/index.php?topic=4973123.0
>
> I'm not sure how I am supposted to have figured out that you wrote a
> somewhat different repost of it elsewhere...
>
> - An M-1 rogue-key attack would require the attacker would to either
>>
>>   - attack the hash function to produce a predictable R based on a known
>> mesage
>>   - attack the DLP to influence x or k
>>
>> Neither attack gives any particular advantage to someone who has M-1 keys.
>>
>
> You keep asserting this. It isn't true. Asserting it more does not make it
> any more true.  I already explained how to attack this style of signature
> (e.g. in the BCT thread).
>
> Set aside your 'interpolation' for a moment, and imagine that you
> construct a 2 of 2 signature by just adding the keys.  Your tell me your
> key, P1  and then I tell you that my key P2 which I derived by computing
> -P1  + xG.   We now compute P = P1 + P2 = P1 + -P1 + xG = xG ... and now in
> spite adding P1 with an unknown discrete log, I know the discrete log of P
> with respect to G and I did not need to violate the standard DL security
> assumption to achieve that.
>
> With the 'interpolation' in effect the same attack applies but its
> execution is somewhat more complex: instead of adding the negation of P1  I
> must add a number of multiplicities of P1 (like P1*2, P1*3, P1*4...)
> selected so that their interpolation coefficients add up to -1. Finding a
> suitable subset requires solving a randomized modular subset sum problem
> and Wagner's algorithm provides a computationally tractable solution to it.
>
> The potential of rogue keys applies to both the keys themselves and to the
> nonces. There are several ways to prevent these attacks, the musig paper
> describes a delinearization technique which doesn't require additional
> interaction or communication.
>
> I haven't tested whether the R,s version is susceptible though.
>>
>
> There is a perfect bijection between the two encodings which is easily
> computable, so they're the same thing from an abstract security perspective.
>
>

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