From: Erik Aronesty <erik@q32•com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Multiparty signatures
Date: Fri, 20 Jul 2018 16:18:47 -0400 [thread overview]
Message-ID: <CAJowKgJXzgQuxt3YMjUfOQRp4T_QybpWKpLq=x-EAif4HLNMcQ@mail.gmail.com> (raw)
In-Reply-To: <CAJowKgKB1GDxvpQt1JjPr+cgyM8yztLtgJ_mZ8vsoCHyBdqkVA@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 3496 bytes --]
Sorry there were typos:
- Using MuSig's solution for the blinding factor (e)
- Using interpolation to enhance MuSig to be M of N instead of M of M
References:
- MuSig https://blockstream.com/2018/01/23/musig-key-aggregation-
schnorr-signatures.html
- HomPrf http://crypto.stanford.edu/~dabo/papers/homprf.pdf (sections 7.1
and 7.4)
Each party:
1. Publishes public key G*xi, G*ki, where ki is a random nonce
3. Xi = H(G*xi) ... Xi is the parties x coordinate, for the purposes of
interpolation
3. R = G*k = via interpolation of r1=Gk1, r2=Gk2... (see HomPrf)
4. L = H(X1,X2,…) (see MuSig)
5. X = sum of all H(L,Xi)Xi (see MuSig)
6. Computes e = H(R | M | X) .... standard schnorr e... not a share
7. Computes si = ki *e+ xi * e ... where si is a "share" of the sig, and xi
is the private data, and e is the blinding factor
8. Publishes (si, e) as the share sig
If an attacker has multiple devices, e is safe, because of the musig
construction.
But what protects k from the same multiparty birthday attack?
If an attacker has multiple devices, by carefully controlling the selection
of private keys, the attacker can try to solve
the polynomial equation to force the selection of a "known k".
A "known k" would allow an attacker to sign messages on his own.
To fix this, we need to somehow "blind k as well".
Does this work?
The revision below seems to solve this problem.
1. Publishes public key G*xi, G*ki, where ki is a random nonce
3. Xi = H(G*xi) ... Xi is the parties x coordinate, for the purposes of
interpolation
3. R = G*k = via interpolation of r1=Gk1, r2=Gk2... (see HomPrf)
4. L = H(X1,X2,…) (see MuSig)
5. L2 = H2(XN,XN-1,…) (see MuSig... H2 is a "second hash")
6. X = sum of all H(L,Xi)Xi (see MuSig)
7. Computes e = H(R | M | X) .... standard schnorr e... not a share
8. Computes e2 = H(R | M | X2) ... a second blinding factor
9. Computes si = ki *e2 + xi * e ... where si is a "share" of the sig, and
xi is the private data, and e, e2 are blinding factors
10. Publishes (si, e, e2) as the share sig
The final signature is computed via interpolation, and e2 is can be
subtracted to recover a "normal" schnor sig for the set of participants.
Now there's no mechanism for a birthday attack on k.
On Fri, Jul 20, 2018 at 1:34 PM, Erik Aronesty <erik@q32•com> wrote:
> Hi, thanks for all the help. I'm going to summarize again, and see if
> we've arrived at the correct solution for an M of N "single sig" extension
> of MuSig, which I think we have.
>
> - Using MuSig's solution for the blinding to solve the Wagner attack
> - Using interpolation to enhance MuSig to be M of N instead of M of M
>
> References:
>
> - MuSig https://blockstream.com/2018/01/23/musig-key-aggregation-
> schnorr-signatures.html
> - HomPrf http://crypto.stanford.edu/~dabo/papers/homprf.pdf (sections
> 7.1 and 7.4)
>
> Each party:
>
> 1. Publishes public key G*xi
> 3. Xi = H(G*xi) ... Xi is the parties x coordinate, for the purposes of
> interpolation
> 3. r = G*x = via interpolation of Gx1, Gx2... (see HomPrf)
> 4. L = H(X1,X2,…) (see MuSig)
> 5. X = sum of all H(L,Xi)Xi (see MuSig)
> 6. Computes e = H(r | M | X) .... standard schnorr e... not a share
> 7. Computes si = xi - xe ... where si is a "share" of the sig, and xi is
> the private data
> 8. Publishes (si, e, G*Xi)
>
> Any party can then derive s from m of n shares, by interpolating, not
> adding.
>
>
>
>
[-- Attachment #2: Type: text/html, Size: 12300 bytes --]
next prev parent reply other threads:[~2018-07-20 20:18 UTC|newest]
Thread overview: 26+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-07-08 14:19 Erik Aronesty
2018-07-08 15:16 ` Tim Ruffing
2018-07-08 18:23 ` Erik Aronesty
2018-07-08 21:01 ` Gregory Maxwell
2018-07-09 0:27 ` Erik Aronesty
2018-07-09 2:33 ` Pieter Wuille
2018-07-09 4:29 ` Erik Aronesty
2018-07-09 4:39 ` Pieter Wuille
[not found] ` <CAJowKg+=7nS4gNmtc8a4-2cu1uCOPqxjfchFwDVqUciKNMUYWQ@mail.gmail.com>
2018-07-09 15:02 ` Erik Aronesty
2018-07-09 15:57 ` Dan Robinson
2018-07-09 15:59 ` Gregory Maxwell
2018-07-09 16:33 ` Erik Aronesty
2018-07-09 16:58 ` Gregory Maxwell
2018-07-09 17:59 ` Erik Aronesty
2018-07-10 11:46 ` Erik Aronesty
2018-07-11 10:35 ` Adam Back
2018-07-11 14:45 ` Erik Aronesty
2018-07-19 12:16 ` Erik Aronesty
2018-07-19 12:24 ` Erik Aronesty
2018-07-19 13:11 ` Russell O'Connor
2018-07-20 16:25 ` Erik Aronesty
2018-07-20 17:34 ` Erik Aronesty
2018-07-20 20:18 ` Erik Aronesty [this message]
2018-07-26 2:05 ` Erik Aronesty
2018-07-09 16:21 ` Gregory Maxwell
2018-07-09 2:29 ` Pieter Wuille
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='CAJowKgJXzgQuxt3YMjUfOQRp4T_QybpWKpLq=x-EAif4HLNMcQ@mail.gmail.com' \
--to=erik@q32$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
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