Documentation threshold ecdsa

[andrea]

Would it be preferable to collect more dealings before moving on?

How do you know how long to wait until the next dealing comes? What if the next dealing is the problematic one? You cannot fully verify them by yourself, since this depends on private verification of the dealing.

Maybe it would be quicker to wait for that dealing, instead of being in a situation in which almost every node has to go through a complaint step?

The current protocol optmizes the efficiency of the optimistic case. Note that in case you do have cheating dealers in a protocol instance, you can actually identify them and thus remove them from the protocol.

[andrea]

@Cryptouf

After verification, it appears I am able to run the scheme with 10 nodes and threshold = 5. It is valid with your rule as I have two polynomials of degree 4, and I need at least 9 points to reconstruct the product of their polynomial.

Note that with these parameters, you cannot achieve liveness. If you have 10 nodes, you are expecting to collect at least 9 dealings. Which means you can tolerate at most 1 corrupt party (note that corrupt/faulty nodes may never send a single message in the protocol). If you assume that more than 1 party can corrupt, then you protocol cannot achieve liveness, i.e. it could never terminate.

[Cryptouf]

Thank you @andrea !

For each dealing we need to collect support shares from the receivers. How many shares should we collect? In the protocol we collect 2f+1, which is actually the maximum assuming up to f corruptions: if you want to collect more support shares then the protocol cannot guarantee liveness, since you would need the participation of possibly corrupt parties to make progress. Therefore in the protocol we have that each dealing has support from 2f+1 receivers, however you don’t know a priori how many of the supporters are honest. Since we assume up to f corruptions, then it means we have at least f+1 honest supporters for each dealing. So in the worst case the f+1 honest supporters need to be able to sign, which means that the threshold can be at most f+1. AFAIK this issue applies in general to interactive DKG protocols.

Is this related to the section 3.4 of the paper?
What seems weird to me is the fact that we need 2f+1 support shares, but we say that the threshold is f+1. If at some point in the protocol, we need 2f+1 users, it means that the “global” threshold is 2f+1, even if the ecdsa threshold is f+1?
Maybe it’s because we need 2f+1 support shares, but only f+1 out of these should rely on honest supporters?

This was explained, e.g., in this forum post

Will read it in details, thanks for sharing !

How do you know how long to wait until the next dealing comes? What if the next dealing is the problematic one?

I don’t know, my idea was about running the two processes in the same time, and see which one ends first.

Note that with these parameters, you cannot achieve liveness. If you have 10 nodes, you are expecting to collect at least 9 dealings. Which means you can tolerate at most 1 corrupt party (note that corrupt/faulty nodes may never send a single message in the protocol). If you assume that more than 1 party can corrupt, then you protocol cannot achieve liveness, i.e. it could never terminate.

And even if I tolerate at most 1 corrupt party, this means that there is no need to have a threshold higher that 2, so I can directly use a (10,2) scheme instead of that (10,5) scheme, right?

[andrea]

@Cryptouf

Maybe it’s because we need 2f+1 support shares, but only f+1 out of these should rely on honest supporters?

Yes, that is the reason. You collect 2f+1, so that you know you can rely on at least f+1 of them.

And even if I tolerate at most 1 corrupt party, this means that there is no need to have a threshold higher that 2, so I can directly use a (10,2) scheme instead of that (10,5) scheme, right?

Yes. But note that with 10 nodes the protocol can tolerate up to 3 dishonest parties, meaning setting the threshold to 4.

[mathcrypto]

@andrea So if we use schemes (10,2) or (10,3) we are risking the security of the protocol or they are also good as (10,4) scheme? since the protocol can tolerate up to 3 dishonest parties, we can assume f=1 or f=2 or f=3

[andrea]

The threshold should be higher than the maximum number of corrupt parties you can/want to tolerate. If you have threshold t, it means that you tolerate up to t-1 corrupt parties, while t corrupt parties can break the security of the protocol. So if you use threshold 2 you can only tolerate a single corrupt party, with threshold 3 you can only tolerate 2 corrupt parties, and so on. Moreover, with 10 nodes the maximum threshold you can achieve is 4.

In principle you can decide to use a threshold which smaller than the maximum (e.g. to make the protocol faster), however you are trading off efficiency with security.

[Cryptouf]

@andrea

You collect 2f+1, so that you know you can rely on at least f+1 of them.

Right now, this supporting part is related to each participant verifying the dealing that he received, so that every dealer can aggregate these verifications into a certificate. Let’s suppose we remove this part : we do not verify each dealing that is broadcasted by every dealer. This means that one malicious actor that provides a false dealing is able to block the whole protocol. Are there any other drawbacks?

[andrea]

@Cryptouf

This means that one malicious actor that provides a false dealing is able to block the whole protocol.

To me it seems already a pretty big drawback! This means that you cannot even guarantee that you can complete the protocol unless you assume all participants are honest. Note also that the security proof uses explicitly the fact that the dealings are privately verified by the receivers. So the current security proof would not carry to the modified protocol.

[Cryptouf]

Hi again @andrea,

can you tell me where in the white paper it is explained that the dealings needs to be privately verified in order for the security proof to be valid? I would like to understand what part of that proof would fail to the modified protocol.
And yes, this is a huge drawback, but in some cases it may not be a problem : if all dealers are in the same family, or owned by the same person for example.

[andrea]

@Cryptouf

if all dealers are in the same family, or owned by the same person for example.

I am not sure it improves security to have multiple dealers controlled by the same party. In any case, these are stronger assumptions than the ones made in the protocol.

can you tell me where in the white paper it is explained that the dealings needs to be privately verified

For example in Section 9, in the security proof of theorem 4 (Game 3 and Game 4), it is explicitly used that the dealings produced by the adversary have been verified by honest receivers. There may be other places though.

[Cryptouf]

In any case, these are stronger assumptions than the ones made in the protocol.

Of course, this is not meant to be the general case. I was wondering if we could remove some steps only in the case where all dealings are owned by the same person.

in Section 9, in the security proof of theorem 4 (Game 3 and Game 4)

Thank you !