mimblewimble team mailing list archive

[Andrew Poelstra <apoelstra@xxxxxxxxxxxxxx>]

On Tue, May 30, 2017 at 01:17:01AM +0200, Tim Ruffing wrote:
> 
> By the way, I wasn't aware that someone is writing up that Schnorr-
> multisig idea formally. It's not a big deal in the end, this
> cancellation attack has been known since the 1994 and we know how to
> avoid it. What Pieter Wuille  [2] proposed as a solution is pretty
> similar to what Mihir Bellare and Gregory Neven [3] proposed in 2006.
> Bellare and Neven give a formal security proof for their scheme.
> (Pieter's idea is a slightly simpler, and it will be nice to see a
> formal proof for it.)
>

The difference between Bellare/Neven and the paper that Greg, Pieter and I
are working on is that Bellare/Neven seed their key randomization with the
message being signed. (And they characterize this as randomizing the message
hashes rather than randomizing the keys, but it's algebraically the same.)
This means that you can't pre-combine the keys...and indeed, they don't
combine keys at all.

The holdup in our paper is that I'm hoping the adapt the Bellare/Neven paper
to our scheme, basically by removing the message from the hash, seeing where
that breaks the proof, and then combining the keys at keygen time rather
than during verification and seeing where -that- breaks the proof. We weren't
aware of the Bellare/Neven paper at the time that we wrote the original
draft and we were rejected from FC'17 for not citing them. This is mostly
on me, I've been juggling a lot of stuff and haven't given this enough
attention. But we're getting pressure from several directions to release the
damn thing, so I'll try to get in gear ASAP.


Cheers
Andrew


-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
       --Joanna Newsom

Attachment: signature.asc
Description: PGP signature