Multiparty signatures
26 messages, 8 to 26 Jul 2018. Started by Erik Aronesty.
Erik Aronesty (15), Gregory Maxwell (4), Pieter Wuille (3), Tim Ruffing, Dan Robinson, Adam Back, Russell O'Connor
To save space, start with the wiki terminology on schnorr sigs.
Consider changing the "e" term in the schnorr algorithm to hash of message (elligator style) to the power of r, rather than using concatenation.
I don't think this changes the security. An attacker would need to know k to either way to compromise the private key.
This would allow m of n devices to sign a transaction without any of them knowing a private key at all.
IE: each device can roll a random number as a share and the interpolation of that is the private key.
The public shares can be broadcast and combines. And signature shares can be broadcast and combined.
The net result of this is it really possible for an arbitrary set of devices to create a perfectly secure public-private key pair set.
At no point was the private key anywhere.
Hi Erik,
On Sun, 2018-07-08 at 10:19 -0400, Erik Aronesty via bitcoin-dev wrote:
Quoted text (3 lines)
> Consider changing the "e" term in the schnorr algorithm to hash of > message (elligator style) to the power of r, rather than using > concatenation.
How do you compute s = x*e if e is an element of group G? (Similar question: How do you verify if e is element of G?)
Are you aware of http://cacr.uwaterloo.ca/techreports/2001/corr2001-13.ps ? This is a threshold signature scheme for Schnorr signatures, so what you want is possible already with Schnorr signatures.
Best, Tim
You don't have to treat the hash as a group member for the purposes of signing.
Everything else about the algorithm works the same.
This just enables signatures to be computed much more simply.
On Sun, Jul 8, 2018, 11:32 AM Tim Ruffing via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (22 lines)
> Hi Erik, > > On Sun, 2018-07-08 at 10:19 -0400, Erik Aronesty via bitcoin-dev wrote: > > Consider changing the "e" term in the schnorr algorithm to hash of > > message (elligator style) to the power of r, rather than using > > concatenation. > > How do you compute s = x*e if e is an element of group G? > (Similar question: How do you verify if e is element of G?) > > Are you aware of > http://cacr.uwaterloo.ca/techreports/2001/corr2001-13.ps ? > This is a threshold signature scheme for Schnorr signatures, so what > you want is possible already with Schnorr signatures. > > Best, > Tim > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >
On Sun, Jul 8, 2018 at 3:16 PM, Tim Ruffing via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (2 lines)
> so what > you want is possible already with Schnorr signatures.
As also described in "Multisignatures and Threshold Signatures" in the BIP.
Pretty sure these non interactive sigs are more secure.
On Sun, Jul 8, 2018, 5:02 PM Gregory Maxwell via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (11 lines)
> On Sun, Jul 8, 2018 at 3:16 PM, Tim Ruffing via bitcoin-dev > <bitcoin-dev@lists•linuxfoundation•org> wrote: > > so what > > you want is possible already with Schnorr signatures. > > As also described in "Multisignatures and Threshold Signatures" in the BIP. > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >
On Sun, Jul 8, 2018, 07:26 Erik Aronesty via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (5 lines)
> To save space, start with the wiki terminology on schnorr sigs. > > Consider changing the "e" term in the schnorr algorithm to hash of message > (elligator style) to the power of r, rather than using concatenation. >
This is a very vague description. Is there some paper you can reference, or a more detailed explanation of the algorithm?
This would allow m of n devices to sign a transaction without any of them
Quoted text (2 lines)
> knowing a private key at all. >
IE: each device can roll a random number as a share and the interpolation
Quoted text (8 lines)
> of that is the private key. > > The public shares can be broadcast and combines. And signature shares can > be broadcast and combined. > > The net result of this is it really possible for an arbitrary set of > devices to create a perfectly secure public-private key pair set. >
At no point was the private key anywhere.
Quoted text (1 line)
>
All of this sounds like a threshold signature scheme, which as Tim pointed out is already possible with Schnorr.
What are the advantages of what you're describing?
Cheers,
On Sun, Jul 8, 2018, 19:23 Erik Aronesty via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (2 lines)
> 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?
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 <pieter.wuille@gmail•com> wrote:
Quoted text (16 lines)
> 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 > >
On Sun, Jul 8, 2018, 21:29 Erik Aronesty <erik@q32•com> wrote:
Quoted text (16 lines)
> 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,
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 <erik@q32•com> wrote:
Quoted text (41 lines)
> 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 <pieter.wuille@gmail•com> > wrote: > >> On Sun, Jul 8, 2018, 21:29 Erik Aronesty <erik@q32•com> 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 >> >> >>
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:
Quoted text (91 lines)
> 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 <erik@q32•com> 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 <pieter.wuille@gmail•com> >> wrote: >> >>> On Sun, Jul 8, 2018, 21:29 Erik Aronesty <erik@q32•com> 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 >
On Mon, Jul 9, 2018 at 3:02 PM, Erik Aronesty via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (3 lines)
> with > security assumptions that match the original Schnorr construction more > closely,
More closely than what?
On Mon, Jul 9, 2018 at 3:02 PM, Erik Aronesty via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (3 lines)
> 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.
Quoted text (1 line)
> 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 <greg@xiph•org> wrote:
Quoted text (8 lines)
> On Mon, Jul 9, 2018 at 3:02 PM, Erik Aronesty via bitcoin-dev > <bitcoin-dev@lists•linuxfoundation•org> wrote: > > with > > security assumptions that match the original Schnorr construction more > > closely, > > More closely than what? >
On Mon, Jul 9, 2018 at 4:33 PM, Erik Aronesty <erik@q32•com> wrote:
Quoted text (3 lines)
>>> 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.
- 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 <greg@xiph•org> wrote:
Quoted text (23 lines)
> On Mon, Jul 9, 2018 at 4:33 PM, Erik Aronesty <erik@q32•com> 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. >
Basically you're just replacing addition with interpolation everywhere in the musig construction.
But maybe I just don't understand how Wagner's algorithm is relevant here.
On Mon, Jul 9, 2018, 1:59 PM Erik Aronesty <erik@q32•com> wrote:
Quoted text (63 lines)
> - 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 <greg@xiph•org> wrote: > >> On Mon, Jul 9, 2018 at 4:33 PM, Erik Aronesty <erik@q32•com> 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. >> > >
On Wed, Jul 11, 2018, 02:42 Erik Aronesty via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (1 line)
> Basically you're just replacing addition with interpolation everywhere in
the musig construction
Yes, but you can't do that without a delinearization mechanism to prevent adaptive public key choice being used to break the scheme using Wagner's attack. It is not specific to addition, it is a generalized birthday attack.
Look at the delinearization mechanism for an intuition, all public keys are hashed along with per value hash, so that pre-commits and forces the public keys to be non-adaptively chosen.
Adaptively chosen public keys are dangerous and simple to exploit for example pub keys A+B, add party C' he chooses C=C'-A-B, now we can sign for A+B+C using adaptively chose public key C.
Btw Wagner also breaks this earlier delinearization scheme S=H(A)*A+H(B)*B+H(C)*C
Adam
OK, so you're going with this scenario:
1. I know Apub and Bpub, 2. I know M is 3 3. I'm choosing a random number for C's private key
Cpub is g^C
The equation I am solving for .. and trying to factor myself out of is g^Ax + g^B*2 + g^C*3
I don't know A or B... I only know their public keys.
I don't think it's possible to adaptively choose C for an attack on the multisig construction, when using hash of the public key as the X coordinate in the polynomial, because in order to satisfy the equation and factor out C, you would need to be able to break the hash.
With an additive construction, yes... adaptive attacks are possible. But in a shamir secret sharing interpolation, you need a public X coordinate as well as a secret share. Choosing hash(pub) as X, prevents this attack.
On Wed, Jul 11, 2018 at 6:35 AM, Adam Back <adam.back@gmail•com> wrote:
Quoted text (22 lines)
> On Wed, Jul 11, 2018, 02:42 Erik Aronesty via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation•org> wrote: > > Basically you're just replacing addition with interpolation everywhere > in the musig construction > > Yes, but you can't do that without a delinearization mechanism to prevent > adaptive public key choice being used to break the scheme using Wagner's > attack. It is not specific to addition, it is a generalized birthday attack. > > Look at the delinearization mechanism for an intuition, all public keys > are hashed along with per value hash, so that pre-commits and forces the > public keys to be non-adaptively chosen. > > Adaptively chosen public keys are dangerous and simple to exploit for > example pub keys A+B, add party C' he chooses C=C'-A-B, now we can sign for > A+B+C using adaptively chose public key C. > > Btw Wagner also breaks this earlier delinearization scheme > S=H(A)*A+H(B)*B+H(C)*C > > Adam >
Also Wagner's algorithm shouldn't be applicable for a number of reasons. you can't birthday attack something where there's only a single variable that you can modify. And when you change the equation from additive you now have a multi-dimensional equation we're partitioning won't function. this is the basis of the perfect security of Shamir secret sharing.
On Wed, Jul 11, 2018, 10:45 AM Erik Aronesty <erik@q32•com> wrote:
Quoted text (49 lines)
> OK, so you're going with this scenario: > > 1. I know Apub and Bpub, > 2. I know M is 3 > 3. I'm choosing a random number for C's private key > > Cpub is g^C > > The equation I am solving for .. and trying to factor myself out of is > g^Ax + g^B*2 + g^C*3 > > I don't know A or B... I only know their public keys. > > I don't think it's possible to adaptively choose C for an attack on the > multisig construction, when using hash of the public key as the X > coordinate in the polynomial, because in order to satisfy the equation and > factor out C, you would need to be able to break the hash. > > With an additive construction, yes... adaptive attacks are possible. But > in a shamir secret sharing interpolation, you need a public X coordinate as > well as a secret share. Choosing hash(pub) as X, prevents this attack. > > > On Wed, Jul 11, 2018 at 6:35 AM, Adam Back <adam.back@gmail•com> wrote: > >> On Wed, Jul 11, 2018, 02:42 Erik Aronesty via bitcoin-dev < >> bitcoin-dev@lists•linuxfoundation•org> wrote: >> > Basically you're just replacing addition with interpolation everywhere >> in the musig construction >> >> Yes, but you can't do that without a delinearization mechanism to prevent >> adaptive public key choice being used to break the scheme using Wagner's >> attack. It is not specific to addition, it is a generalized birthday attack. >> >> Look at the delinearization mechanism for an intuition, all public keys >> are hashed along with per value hash, so that pre-commits and forces the >> public keys to be non-adaptively chosen. >> >> Adaptively chosen public keys are dangerous and simple to exploit for >> example pub keys A+B, add party C' he chooses C=C'-A-B, now we can sign for >> A+B+C using adaptively chose public key C. >> >> Btw Wagner also breaks this earlier delinearization scheme >> S=H(A)*A+H(B)*B+H(C)*C >> >> Adam >> > >
Probably because my descriptions are a bit vague and rambling.
but I can't help but think that a SMC of a bitcoin private key, followed by a secure multiparty computation of a signature is going to be more secure overall.
I couldn't figure out how to do it offline. But one round of exchange seems to work.
It comes down to the blinding factor (k). All parties need to agree to it ... which creates the second round.
On Thu, Jul 19, 2018, 8:16 AM Erik Aronesty <erik@q32•com> wrote:
Quoted text (59 lines)
> Also Wagner's algorithm shouldn't be applicable for a number of reasons. > you can't birthday attack something where there's only a single variable > that you can modify. And when you change the equation from additive you > now have a multi-dimensional equation we're partitioning won't function. > this is the basis of the perfect security of Shamir secret sharing. > > On Wed, Jul 11, 2018, 10:45 AM Erik Aronesty <erik@q32•com> wrote: > >> OK, so you're going with this scenario: >> >> 1. I know Apub and Bpub, >> 2. I know M is 3 >> 3. I'm choosing a random number for C's private key >> >> Cpub is g^C >> >> The equation I am solving for .. and trying to factor myself out of is >> g^Ax + g^B*2 + g^C*3 >> >> I don't know A or B... I only know their public keys. >> >> I don't think it's possible to adaptively choose C for an attack on the >> multisig construction, when using hash of the public key as the X >> coordinate in the polynomial, because in order to satisfy the equation and >> factor out C, you would need to be able to break the hash. >> >> With an additive construction, yes... adaptive attacks are possible. >> But in a shamir secret sharing interpolation, you need a public X >> coordinate as well as a secret share. Choosing hash(pub) as X, prevents >> this attack. >> >> >> On Wed, Jul 11, 2018 at 6:35 AM, Adam Back <adam.back@gmail•com> wrote: >> >>> On Wed, Jul 11, 2018, 02:42 Erik Aronesty via bitcoin-dev < >>> bitcoin-dev@lists•linuxfoundation•org> wrote: >>> > Basically you're just replacing addition with interpolation everywhere >>> in the musig construction >>> >>> Yes, but you can't do that without a delinearization mechanism to >>> prevent adaptive public key choice being used to break the scheme using >>> Wagner's attack. It is not specific to addition, it is a generalized >>> birthday attack. >>> >>> Look at the delinearization mechanism for an intuition, all public keys >>> are hashed along with per value hash, so that pre-commits and forces the >>> public keys to be non-adaptively chosen. >>> >>> Adaptively chosen public keys are dangerous and simple to exploit for >>> example pub keys A+B, add party C' he chooses C=C'-A-B, now we can sign for >>> A+B+C using adaptively chose public key C. >>> >>> Btw Wagner also breaks this earlier delinearization scheme >>> S=H(A)*A+H(B)*B+H(C)*C >>> >>> Adam >>> >> >>
On Thu, Jul 19, 2018 at 8:16 AM, Erik Aronesty via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (3 lines)
> you can't birthday attack something where there's only a single variable > that you can modify. >
When engaging in a multiparty signature, the attacker can more than one variable to modify. When you are party to a multi-party signature (for example, in some sort of coin-join protocol) it could be that every other participant in the multi-party signature is, in fact, the same single attacker representing themselves as multiple participants. This is how the attacker gets their hands on multiple variables.
That's a great point. It's been solved in musig and that doesn't change the m of n multisig construction.
You use the same musig construction where you hash all keys and sum the multiples....and use that when computing k ... the shared blinding factor.... you're still improving the system .... Getting a nice Shamir m of n multisig.... with a single signature...and all the same properties otherwise.
On Thu, Jul 19, 2018, 9:11 AM Russell O'Connor <roconnor@blockstream•io> wrote:
Quoted text (16 lines)
> On Thu, Jul 19, 2018 at 8:16 AM, Erik Aronesty via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation•org> wrote: > >> you can't birthday attack something where there's only a single variable >> that you can modify. >> > > When engaging in a multiparty signature, the attacker can more than one > variable to modify. When you are party to a multi-party signature (for > example, in some sort of coin-join protocol) it could be that every other > participant in the multi-party signature is, in fact, the same single > attacker representing themselves as multiple participants. This is how the > attacker gets their hands on multiple variables. > > >
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.
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:
Quoted text (33 lines)
> 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. > > > >
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 <erik@q32•com> wrote:
Quoted text (98 lines)
> 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. >> >> >> >> >