Also we don't need any new opcodes to support this. Done right this could literally go out into clients immediately.
On Fri, Jul 20, 2018, 4:18 PM Erik Aronesty <e...@q32.com> wrote: > 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 <e...@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. >> >> >> >> >
_______________________________________________ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
