Second round is unnecessary

[earonesty]

If, in the first round each party uses a proof of knowledge of secret key, the second round where signers verify the commitment - which is necessary to prevent a rogue key attack - is not needed. In addition, there's no need to use each of the signer's public keys in the hash.

Instead a precomputed aggregate public key can be used for a given set of signers and a given threshold. Since proof of secret key was used during the establishment of this aggregate, it cannot be pre-selected, and is sufficient to use in the subsequent digest computations.

Finally, it is often desirable for signature schemes to be "malleable" (each message gets a unique sig), and others to be "fixed", (the signature corresponding to a given message is deterministic).

Such a library should allow for both scenarios.

[omershlo]

How do you solve for Wagner k-sum attack without a second round? see #34 for details

[earonesty]

In the first round, each user includes a proof of knowledge of secret key (an ecdh sig is fine). This prevents rogue key attacks.

But yes, as long as R̂ is a simple sum, it seems 2 signers using a birthday attack could discover a favorable R̂ - allowing those 2 signers to sign arbitrary messages.

Seems like this paper proves that nearly all 2 round schemes are somewhat insecure https://eprint.iacr.org/2018/417.pdf.

[omershlo]

exactly

[earonesty]

I've been puzzling over this.

Certainly a 2 round scheme is fine when there are only 2 signers. If you have, for example, a 2 of 4 threshold scheme (a useful and common configuration)... then 2 rounds are sufficient since k-sum is a non-issue. Hence a POKSK round is enough to ensure that a single attacker cannot rouge-key you.

Finally, another solution to k-sums is to simply double the bit strength since the best k-sums can do is halve it, again... POKSK should be sufficient if the bits in R̂ is large. This could still be made bitwise compatible with bitcoin since the specification of the nonce doesn't impact the final signature and validation (hash of R can be used to get the bits into a shape bitcoin needs)

So, 2 decent options that can reduce the number of rounds to 2 while solving for a k-sums attack on R. I suspect you can get it to 1 using pairings + the message itself as a secure multiparty offline nonce-generator. Sounds fun.

[omershlo]

I tend to agree with you that the two party case is a special case. IIRC we even implemented a 2 round 2 parties EdDSA (cc @oleiba ).

About doubling the bit size : sounds interesting but I am not sure how this can be done in practice. Can you elaborate more on how such protocol will look like?

Pairing would enable you to do 1 round but it will not be called Schnorr anymore

[earonesty]

1. Double bit size.

   • During the entire nonce-establishment step (round 1), a curve with double the # of bits is used. Along with an appropriate proof of knowledge, this can be done with only a k-sums attack vulnerability. And since k-sums only can only cut the bits of strength in half, attacking a 512-bit curve during this step is just as hard as attacking a 256 bit curve in 3 rounds.

   • It doesn't matter what curve you use in that first round, since the final signature is a "normal" schnor sig anyway.... and bitcoin doesn't need to be aware of what mechanism was used to coordinate the multisig.

   • This is the simplest solution.

2. Use a non-interactive way to come up with a shared nonce:

   • See https://crypto.stackexchange.com/questions/75920/non-interactive-threshold-signature-without-bilinear-pairing-is-it-possible.

   • Better way to establish that multiparty masking nonce such that a k-sums attack isn't possible... because knowing the DLP for the nonce doesn't help colluding attackers sign in any way. (I like this solution.)

3. Regarding pairings.

   • Just thinking that there might be some way to come up with fragments of a nonce... involving a) the digest of the message as a point and b) your private fragment. .... knowing only others public fragments. Still regular schnorr at the end.

[omershlo]

Hi!

1. I think this idea is VERY solid. If I understand you correctly, you want to try internally to use 512 bit curve (or pairings in 3). I think both 1 and 3 have potential and I would like to explore them further. I will ask in the telegram group (https://t.me/kzen_research , you should join) for more opinions.

about 2 - I must admit I didn't understand.

btw, have you looked into : https://crysp.uwaterloo.ca/software/frost/frost-techreport-20200120.pdf ? I don't think they provide answer

[shumy-tools]

Hello, I'm the author of the stackexchange question. Erik Aronesty, thank you for the invite.

I'm trying to find a solid response for the proposal, since I can't believe myself that such a simple solution exists. It's hard for me to find people to validate my work. So, I would appreciate your help in this matter and, it seems that it would also be useful for you.

Furthermore, I have to say that this scheme is not entirely deterministic for the same message. If you select a different set of t + 1 nodes, the nonce would be different.

[earonesty]

I did read the frost paper, and I think shumy solves the problem more elegantly. it's intuitive to me that a simple random oracle solution to the nonce should exist, although I've tried and messed up a couple times in the past.

[earonesty]

FYI: We found that it was insecure on multiple levels. Didn't protect against k-sums, and had an issue with multiple signings of the same message. I'm back to pairings on the best way to sign stuff, where there's less of a possibility of "doing it wrong".

[omershlo]

Got it, thanks for the update. Pairings - well... it's like magic

[shumy-tools]

@earonesty "it was insecure on multiple levels" - Although I'm still trying to reach to a complete proof of security. With the exception that first attack (which is easily solvable with the seq parameter) none of the other proposed attacks work. The followup in Is this distributed random oracle scheme safe? doesn't present hard evidences that any of the attacks work.

And, unless you want to give up on Schnorr's signatures, what you proposed about the oracle model should also be applicable to non threshold schemes.

You may want to go with Pairings, but I'm still waiting for a good attack on the proposed scheme.

[earonesty]

All you have to do is wait for all the other signers to report their shares. Then you and your attacker partner can ksums attack R. You don't need to attack m0. You and your partner can sign one message now, knowing R.

Another way to think of it is this. If your scheme is secure then any random nonce is secure. Because the hash isn't any better than a random number. And there is no ksums attack at all.

On Fri, Mar 6, 2020, 5:39 AM shumy-tools notifications@github.com wrote:

@earonesty https://github.com/earonesty "it was insecure on multiple levels" - Although I'm still trying to reach to a complete proof of security. With the exception that first attack (which is easily solvable with the seq parameter) none of the other proposed attacks work. The followup in Is this distributed random oracle scheme safe? https://crypto.stackexchange.com/questions/77683/is-this-distributed-random-oracle-scheme-safe doesn't present hard evidences that any of the attacks work.

And, unless you want to give up on Schnorr's signatures, what you proposed about the oracle model should also be applicable to non threshold schemes.

You may want to go with Pairings, but I'm still waiting for a good attack on the proposed scheme.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/KZen-networks/multi-party-schnorr/issues/37?email_source=notifications&email_token=AAAMMUIWHVIHGRNBKNTZVVTRGDHEZA5CNFSM4KQ5UBN2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEOA42HI#issuecomment-595709213, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAAMMUIBGXRZ6MGAUGZNICTRGDHEZANCNFSM4KQ5UBNQ .

[shumy-tools]

@earonesty By R you meen m*G = R ? This is dicussed in the other topic. You can't sign a message without having m, and you can't have m without having m0. You need at least one honest share of y and m. You can k-sum R as you want, you can't revert it. And... "Aman Grewal" in that topic finally assumes this in his response "This shouldn't an issue for signatures".

I state, there is no proof that k-sum works.

[earonesty]

The attacker can have m without being able to get m0, and that's enough.

On Mon, Mar 9, 2020 at 5:54 AM shumy-tools notifications@github.com wrote:

@earonesty https://github.com/earonesty By R you meen m*G = R ? This is dicussed in the other topic. You can't sign a message without having m, and you can't have m without having m0. You need at least one honest share of y and m. You can k-sum R as you want, you can't revert it. And... "Aman Grewal" in that topic finally assumes this in his response "This shouldn't an issue for signatures".

I state, there is no proof that k-sum works.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/KZen-networks/multi-party-schnorr/issues/37?email_source=notifications&email_token=AAAMMUJJYAED6B6F4F74YNDRGS4E5A5CNFSM4KQ5UBN2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEOGNKEI#issuecomment-596432145, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAAMMUNVZCTXJ7HBAOL6IP3RGS4E5ANCNFSM4KQ5UBNQ .

[shumy-tools]

How, can you give me a math proof on that? Because the math formulation that I have done doesn't allow to recover m without knowing m0. Even if k-sum on R you cannot get the respectives m_i.

[earonesty]

Not really good at math proofs. But, it's easy to see that you can birthday-attack to control for a specific R. Which implies you already have m.

On Mon, Mar 9, 2020 at 11:15 AM shumy-tools notifications@github.com wrote:

How, can you give me a math proof on that? Because the math formulation that I have done doesn't allow to recover m without knowing m0. Even if k-sum on R you cannot get the respectives m_i.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or unsubscribe.

[earonesty]

The idea is that two or more attackers are "lying" about their shares of the public nonce. They aren't following your formula and hashing the message. They are just controlling what R will be... because you have know way of knowing whether they are hashing.

On Mon, Mar 9, 2020 at 11:48 AM Erik Aronesty erik@q32.com wrote:

Not really good at math proofs. But, it's easy to see that you can birthday-attack to control for a specific R. Which implies you already have m.

On Mon, Mar 9, 2020 at 11:15 AM shumy-tools notifications@github.com wrote:

How, can you give me a math proof on that? Because the math formulation that I have done doesn't allow to recover m without knowing m0. Even if k-sum on R you cannot get the respectives m_i.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or unsubscribe.

[shumy-tools]

"Which implies you already have m" - There is where you assumption fails. Having a public key does not imply to have the private key, or else every asymmetric encryption would be broken! You cannot produce a signature by just having R.

Yes, you have a R that corresponds to an existing R* for other signature; however, deriving that via a k-sum of public keys won't be able to get you m_i or m, only a set of M_i values. Note that, past m_i values won't work because m0 is always different. In this sense, to get the corresponding m_i values to perform the signature you need to break the DLP.

[shumy-tools]

In a conclusion, controling the R value is a false assumption. It's pointless to control R if you cannot output a signature with it! Because, to output the signature require you to know m_i shares directly.

[earonesty]

Seems this answer here shows the issue better than I can: https://crypto.stackexchange.com/questions/77683/is-this-distributed-random-oracle-scheme-safe

[shumy-tools]

The answer already assumes that the k-sum is not a problem "This shouldn't an issue for signatures", due to exactly of what I explained. The second attack, is also not proved, refer to my comment in the response. The bounty is still open.

[shumy-tools]

A curiosity... if a bilinear pairing can perform a second degree verification, and if you can perform a threshold signature with BLS in one round; then (by intuition), you should be able to perform a 2 round signature without bilinear pairings! Although that intuition may be wrong, but that's what i'm trying to find out.