Re: [bitcoin-dev] Multiparty signatures
- Adaptive r choice shouldn't be possible since r is derived from the original threshold prf and it's not possible for a party to have any adaptive impact on the value of r - I'm guess I don't see how an attacker can use adaptive key choice in this context either. Any modification of the key should be useless AH! I forgot to include some assumptions. The important part here is that each party only has a share of the private key and publishes a share of the public key. This hopefully should preclude any sort of adaptive key attack. >From scratch: 1. Has a public g^x' 2. Computes and broadcasts g^k' ... where k' is a random number 3. Computes r = g^k using lagrange interpolation (see http://crypto.stanford.edu/~dabo/papers/homprf.pdf) 4. Computes H(r || M), as per standard schnorr 5. Computes s' = k' - xe , as per standard schnorr .. except k' is a "share" 6. Publish (s', e, g^x') Verification: With m of n share-signatures: 1. Interpolation on m of n s' shares to get s 2. Interpolation on m of n g^x' shares to get g^x 3. Standard schnorr verification The actual public key of the "set of signers" is interpolated. On Mon, Jul 9, 2018 at 12:58 PM, Gregory Maxwell wrote: > On Mon, Jul 9, 2018 at 4:33 PM, Erik Aronesty wrote: > >>> with security assumptions that match the original Schnorr construction > more closely, > >> More closely than what? > > More closely than musig. > > Musig is instructions on using the original schnorr construction for > multiparty signing which is secure against participants adaptively > choosing their keys, which is something the naive scheme of just > interpolating keys and shares is vulnerable to. It works as > preprocessing on the keys, then you continue on with the naive > protocol. The verifier (e.g. network consensus rules) is the same. > > Now that you're back to using a cryptographic hash, I think what > you're suggesting is "use naive interpolation of schnorr signatures" > -- which you can do, including with the verifier proposed in the BIP, > but doing that alone is insecure against adaptive key choice (and > potentially adaptive R choice, depending on specifics which aren't > clear enough to me in your description). In particular, although it > seems surprising picking your interpolation locations with the hash of > each key isn't sufficient to prevent cancellation attacks due to the > remarkable power of wagner's algorithm. > ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Multiparty signatures
On Mon, Jul 9, 2018 at 4:33 PM, Erik Aronesty wrote: >>> with security assumptions that match the original Schnorr construction more >>> closely, >> More closely than what? > More closely than musig. Musig is instructions on using the original schnorr construction for multiparty signing which is secure against participants adaptively choosing their keys, which is something the naive scheme of just interpolating keys and shares is vulnerable to. It works as preprocessing on the keys, then you continue on with the naive protocol. The verifier (e.g. network consensus rules) is the same. Now that you're back to using a cryptographic hash, I think what you're suggesting is "use naive interpolation of schnorr signatures" -- which you can do, including with the verifier proposed in the BIP, but doing that alone is insecure against adaptive key choice (and potentially adaptive R choice, depending on specifics which aren't clear enough to me in your description). In particular, although it seems surprising picking your interpolation locations with the hash of each key isn't sufficient to prevent cancellation attacks due to the remarkable power of wagner's algorithm. ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Multiparty signatures
Can you please clarify which terms in that description are elliptic curve points, and which are scalars? On Mon, Jul 9, 2018 at 11:10 AM Erik Aronesty via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Actually, it looks like in order to compute a multiparty signature you > will need to broadcast shares of r first, so it's not offline :( > > It is still seems, to me, to be a simpler mechanism than musig - with > security assumptions that match the original Schnorr construction more > closely, and should therefore be easier to prove secure in a multiparty > context. > > Shamir/Schnorr threshold multi-signature scheme: > > Each party: > > - Has a public key g*x', where x' is their private key, and where H(g*x) > can be considered their public index for the purposes of Shamir polynomial > interpolation > - Rolls a random k' and compute r' = g*k' > - Broadcast r' as a share > - Computes g*k, via lagrange interpolation across shares. At this point > k is not known to any party unless Shamir is vulnerable or DL is not hard > - Computes e' = H(M) * r' > - Computes s' = k'-x*e' > - Share of signature is (s', e') > > Verification is the same as Scnhorr, but only after using interpolation to > get the needed (s, e, g*x) from shares of s', e' and g*x': > > - Using lagrange interpolation, compute the public key g*x > - Again, using lagrange interpolation, compute (s, e) > - Verify the signature as per standard Schnorr > > Security assumptions: > > - Because this is not additive, and instead we are using Shamir > combination, the additional blinding and masking steps of musig are not > needed to create a secure scheme. > - The scheme is the same as Schnorr otherwise > - The only thing to prove is that H(M) * r does not reveal any > information about k ... which relies on the same DL assumptions as Bitcoin > itself > - Overall, this seems, to me at least, to have a smaller attack surface > because there's fewer moving parts > > > On Mon, Jul 9, 2018 at 8:24 AM, Erik Aronesty wrote: > >> I was hoping that nobody in this group saw an obvious problem with it >> then I'd sit down and try to write up a paper. >> >> Not that hard to just reuse the work done on schnorr. And demonstrate >> that there are no additional assumptions. >> > >> On Mon, Jul 9, 2018, 12:40 AM Pieter Wuille >> wrote: >> >>> On Sun, Jul 8, 2018, 21:29 Erik Aronesty wrote: >>> Because it's non-interactive, this construction can produce multisig signatures offline. Each device produces a signature using it's own k-share and x-share. It's only necessary to interpolate M of n shares. There are no round trips. The security is Shamir + discrete log. it's just something I've been tinkering with and I can't see an obvious problem. It's basically the same as schnorr, but you use a threshold hash to fix the need to be online. Just seems more useful to me. >>> >>> That sounds very useful if true, but I don't think we should include >>> novel cryptography in Bitcoin based on your not seeing an obvious problem >>> with it. >>> >>> I'm looking forward to seeing a more complete writeup though. >>> >>> Cheers, >>> >>> -- >>> Pieter >>> >>> >>> ___ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Multiparty signatures
> More closely than what? More closely than musig. In fact there's no need to distribute the hash at all if you have the first round, you can leave the schnorr construction... thanks for the feedback. I literally can't think about this stuff without someone asking questions. 1. For those who asked, the construction from section 7.1 of this paper describes how to use lagrange interpolation in a group context: http://crypto.stanford.edu/~dabo/papers/homprf.pdf 2. Using shamir interpolation is cleaner than the additive multisig 3. Taking your comments into consideration, I think it's possible to remove the point multiplication instead of a hash and stick to Schnorr "as is", and still cut out all but one online round: OK, so this is a new Multisig variant of schnorr with fewer rounds... I know this is possible, I just needed to have that back and forth... sorry: For sake of terminology and typing in ascii, I'm using ^ to mean "point multiplcation" Each party: 1. Has a public g^x 2. Computes and broadcasts g^k' ... where k' is a random number 3. Computes r = g^k using lagrange interpolation (see http://crypto.stanford.edu/~dabo/papers/homprf.pdf) 4. Computes H(r || M), as per standard schnorr 5. Computes s' = k' - xe , as per standard schnorr .. except k' is a "share" 6. Publish (s', e) Verification: With m of n share-signatures: 1. Use lagrange interpolation on m of n s' shares to get s 2. Standard schnorr verification - Erik On Mon, Jul 9, 2018 at 11:59 AM, Gregory Maxwell wrote: > On Mon, Jul 9, 2018 at 3:02 PM, Erik Aronesty via bitcoin-dev > wrote: > > with > > security assumptions that match the original Schnorr construction more > > closely, > > More closely than what? > ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Multiparty signatures
On Mon, Jul 9, 2018 at 3:02 PM, Erik Aronesty via bitcoin-dev wrote: > and where H(g*x) can > be considered their public index for the purposes of Shamir polynomial > interpolation This is isomorphic to the insecure musig variant where keys are blinded by H(g*x) instead of a commitment to all keys. It is insecure because it vulnerable to an attacker knowing a victim pubkey P who uses wagner's algorithim to solve a random modular subset sum problem: -1H(P) = H(aP)/a + H(bP)/b + H(cP)/c + ... for some a,b,c... then claiming to be participants with keys aP, bP, cP, ..., xG (their own key) and canceling out key P, allowing the value to just be signed for with their key alone. AFAICT your suggestion is using simple multiplication in the place of a cryptographic hash. E.g. you have just suggested a schnorr signature where H() is just r*m in the field of size n. It doesn't have any new properties about how you can use it. The same linearities do and don't apply as the normal schnorr construction, but for any of the security proofs to hold we'd have to believe that multiplication in the field of n is a suitable random oracle-- which is not very plausible. ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Multiparty signatures
On Mon, Jul 9, 2018 at 3:02 PM, Erik Aronesty via bitcoin-dev wrote: > with > security assumptions that match the original Schnorr construction more > closely, More closely than what? ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Multiparty signatures
Actually, it looks like in order to compute a multiparty signature you will need to broadcast shares of r first, so it's not offline :( It is still seems, to me, to be a simpler mechanism than musig - with security assumptions that match the original Schnorr construction more closely, and should therefore be easier to prove secure in a multiparty context. Shamir/Schnorr threshold multi-signature scheme: Each party: - Has a public key g*x', where x' is their private key, and where H(g*x) can be considered their public index for the purposes of Shamir polynomial interpolation - Rolls a random k' and compute r' = g*k' - Broadcast r' as a share - Computes g*k, via lagrange interpolation across shares. At this point k is not known to any party unless Shamir is vulnerable or DL is not hard - Computes e' = H(M) * r' - Computes s' = k'-x*e' - Share of signature is (s', e') Verification is the same as Scnhorr, but only after using interpolation to get the needed (s, e, g*x) from shares of s', e' and g*x': - Using lagrange interpolation, compute the public key g*x - Again, using lagrange interpolation, compute (s, e) - Verify the signature as per standard Schnorr Security assumptions: - Because this is not additive, and instead we are using Shamir combination, the additional blinding and masking steps of musig are not needed to create a secure scheme. - The scheme is the same as Schnorr otherwise - The only thing to prove is that H(M) * r does not reveal any information about k ... which relies on the same DL assumptions as Bitcoin itself - Overall, this seems, to me at least, to have a smaller attack surface because there's fewer moving parts On Mon, Jul 9, 2018 at 8:24 AM, Erik Aronesty wrote: > I was hoping that nobody in this group saw an obvious problem with it then > I'd sit down and try to write up a paper. > > Not that hard to just reuse the work done on schnorr. And demonstrate > that there are no additional assumptions. > > On Mon, Jul 9, 2018, 12:40 AM Pieter Wuille > wrote: > >> On Sun, Jul 8, 2018, 21:29 Erik Aronesty wrote: >> >>> Because it's non-interactive, this construction can produce multisig >>> signatures offline. Each device produces a signature using it's own >>> k-share and x-share. It's only necessary to interpolate M of n shares. >>> >>> There are no round trips. >>> >>> The security is Shamir + discrete log. >>> >>> it's just something I've been tinkering with and I can't see an obvious >>> problem. >>> >>> It's basically the same as schnorr, but you use a threshold hash to fix >>> the need to be online. >>> >>> Just seems more useful to me. >>> >> >> That sounds very useful if true, but I don't think we should include >> novel cryptography in Bitcoin based on your not seeing an obvious problem >> with it. >> >> I'm looking forward to seeing a more complete writeup though. >> >> Cheers, >> >> -- >> Pieter >> >> >> ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Multiparty signatures
Because it's non-interactive, this construction can produce multisig signatures offline. Each device produces a signature using it's own k-share and x-share. It's only necessary to interpolate M of n shares. There are no round trips. The security is Shamir + discrete log. it's just something I've been tinkering with and I can't see an obvious problem. It's basically the same as schnorr, but you use a threshold hash to fix the need to be online. Just seems more useful to me. On Sun, Jul 8, 2018, 10:33 PM Pieter Wuille wrote: > On Sun, Jul 8, 2018, 19:23 Erik Aronesty via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> wrote: > >> Pretty sure these non interactive sigs are more secure. >> > > Schnorr signatures are provably secure in the random oracle model assuming > the discrete logarithm problem is hard in the used group. > > What does "more secure" mean? Is your construction secure with weaker > assumptions? > > -- > Pieter > > ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] BIP sighash_noinput
On Tue, Jul 03, 2018 at 11:45:22PM +, Gregory Maxwell wrote: > On Tue, Jul 3, 2018 at 5:21 AM, Peter Todd wrote: > > The problem with that name is `SIGHASH_REUSE_VULNERABLE` tells you nothing > > about what the flag actually does. > > I believe that making the signature replayable is 1:1 with omitting > the identification of the specific coin being spent from it. I think you have a good point there. But that's not the only way that reuse could be a vulnerability: consider hash-based signatures. I'm happy with adding a suffix or prefix to the term SIGHASH_NOINPUT, e.g. SIGHASH_NOINPUT_UNSAFE to re-use Rust terminology. -- https://petertodd.org 'peter'[:-1]@petertodd.org signature.asc Description: PGP signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
