Erik Aronesty [ARCHIVE] on Nostr: 📅 Original date posted:2018-09-11 📝 Original message:Greg, I added, stripped ...
📅 Original date posted:2018-09-11
📝 Original message: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 at xiph.org> wrote:
> On Tue, Sep 11, 2018 at 4:34 PM Erik Aronesty <erik at 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.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180911/1dad3a33/attachment.html>;
📝 Original message: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 at xiph.org> wrote:
> On Tue, Sep 11, 2018 at 4:34 PM Erik Aronesty <erik at 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.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180911/1dad3a33/attachment.html>;