Re: [bitcoin-dev] Schnorr signatures BIP

[Gregory Maxwell <greg@xiph.org>]

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

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: 3393 bytes --]