[bitcoin-dev] Multiparty signatures

[bitcoin-dev] Multiparty signatures

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 822 bytes --]

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.

[-- Attachment #2: Type: text/html, Size: 1271 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Tim Ruffing]

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

Re: [bitcoin-dev] Multiparty signatures

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 1082 bytes --]

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:

> 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
>

[-- Attachment #2: Type: text/html, Size: 1924 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Gregory Maxwell]

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.

Re: [bitcoin-dev] Multiparty signatures

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 614 bytes --]

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:

> 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
>

[-- Attachment #2: Type: text/html, Size: 1279 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Pieter Wuille]

[-- Attachment #1: Type: text/plain, Size: 1143 bytes --]

On Sun, Jul 8, 2018, 07:26 Erik Aronesty via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> 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
> 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.
>

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,

-- 
Pieter

[-- Attachment #2: Type: text/html, Size: 2759 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Pieter Wuille]

[-- Attachment #1: Type: text/plain, Size: 396 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 1036 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 989 bytes --]

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:

> 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
>
>

[-- Attachment #2: Type: text/html, Size: 2204 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Pieter Wuille]

[-- Attachment #1: Type: text/plain, Size: 816 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 2104 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 2963 bytes --]

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
>>
>>
>>

[-- Attachment #2: Type: text/html, Size: 5361 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Dan Robinson]

[-- Attachment #1: Type: text/plain, Size: 3483 bytes --]

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 <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
>

[-- Attachment #2: Type: text/html, Size: 6411 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Gregory Maxwell]

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?

Re: [bitcoin-dev] Multiparty signatures

[Gregory Maxwell]

On Mon, Jul 9, 2018 at 3:02 PM, Erik Aronesty via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> 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.

Re: [bitcoin-dev] Multiparty signatures

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 1784 bytes --]

> 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:

> 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?
>

[-- Attachment #2: Type: text/html, Size: 6529 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Gregory Maxwell]

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.

Re: [bitcoin-dev] Multiparty signatures

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 2450 bytes --]

 - 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.
>

[-- Attachment #2: Type: text/html, Size: 8749 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 2784 bytes --]

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:

>  - 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.
>>
>
>

[-- Attachment #2: Type: text/html, Size: 9381 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Adam Back]

[-- Attachment #1: Type: text/plain, Size: 896 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 1339 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 1804 bytes --]

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
>

[-- Attachment #2: Type: text/html, Size: 2813 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 2302 bytes --]

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
>>
>
>

[-- Attachment #2: Type: text/html, Size: 3551 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 2861 bytes --]

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:

> 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
>>>
>>
>>

[-- Attachment #2: Type: text/html, Size: 4500 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 627 bytes --]

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.

[-- Attachment #2: Type: text/html, Size: 994 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 1141 bytes --]

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:

> 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.
>
>
>

[-- Attachment #2: Type: text/html, Size: 1836 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 1062 bytes --]

 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: 3820 bytes --]

Re: [bitcoin-dev] Multiparty signatures

[Erik Aronesty]

[-- 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 --]

Re: [bitcoin-dev] Multiparty signatures

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 3829 bytes --]

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:

> 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: 12825 bytes --]