public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Gregory Maxwell <greg@xiph.org>
To: Erik Aronesty <erik@q32.com>
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Schnorr signatures BIP
Date: Tue, 11 Sep 2018 17:00:25 +0000	[thread overview]
Message-ID: <CAAS2fgSfdfQ2CiEabjrjspQGQufwzk84f1mzM1j_LRWqAPd8wA@mail.gmail.com> (raw)
In-Reply-To: <CAJowKg+-45h6vraL1PpnqfhHSbG+G40L+FD7xN+C-Dn1E6Y_Vg@mail.gmail.com>

[-- 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 --]

  reply	other threads:[~2018-09-11 17:00 UTC|newest]

Thread overview: 31+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-07-06 18:08 [bitcoin-dev] Schnorr signatures BIP Pieter Wuille
2018-07-06 21:05 ` Russell O'Connor
2018-07-06 22:00   ` Gregory Maxwell
2018-07-06 22:01     ` Gregory Maxwell
2018-07-08 14:36     ` Russell O'Connor
2018-07-14 15:42 ` Sjors Provoost
2018-07-14 21:20   ` Pieter Wuille
2018-08-04 12:22     ` Russell O'Connor
2018-08-05 14:33       ` Russell O'Connor
2018-08-06  8:39         ` Anthony Towns
2018-08-06 14:00           ` Russell O'Connor
2018-08-06 21:12 ` Tim Ruffing
2018-08-12 16:37   ` Andrew Poelstra
2018-08-29 12:09     ` Erik Aronesty
2018-09-03  0:05       ` Andrew Poelstra
2018-09-05 12:26         ` Erik Aronesty
2018-09-05 13:05           ` Andrew Poelstra
2018-09-05 13:14             ` Erik Aronesty
2018-09-05 15:35           ` Gregory Maxwell
2018-09-11 16:34             ` Erik Aronesty
2018-09-11 17:00               ` Gregory Maxwell [this message]
2018-09-11 17:20                 ` Erik Aronesty
2018-09-11 17:27                   ` Gregory Maxwell
2018-09-11 17:37                     ` Erik Aronesty
2018-09-11 17:51                       ` Gregory Maxwell
2018-09-11 18:30                         ` Erik Aronesty
2018-09-13 18:46                       ` Andrew Poelstra
2018-09-13 20:20                         ` Erik Aronesty
2018-09-14 14:38                           ` Andrew Poelstra
2018-09-20 21:12 ` Russell O'Connor
2018-07-07  2:47 Артём Литвинович

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=CAAS2fgSfdfQ2CiEabjrjspQGQufwzk84f1mzM1j_LRWqAPd8wA@mail.gmail.com \
    --to=greg@xiph.org \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=erik@q32.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox