Re: [bitcoin-dev] Multiparty signatures

[Erik Aronesty <erik@q32.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 --]