[CHECKLIST] follow CGGMP20 paper

[ivokub]

Overview

The current implementation is an evaluation over different protocols. There is some mismatch between the proofs and values being transmitted with the papers, leading to potential vulnerabilities. The goal of this checklist is to define a roadmap to streamline the implementation to be more compatible with the paper and easier to audit.

Checklist

• refactor: single set of Paillier keys as in CGGMP paper #41 - We have two sets of Paillier keys: https://github.com/webb-tools/cggmp-threshold-ecdsa/blob/main/multi-party-ecdsa/src/gg_2020/party_i.rs#L174C1-L175. This was true for GG18/GG20, but CGGMP uses only a single set of keys. Having only a single set of keys also strengthens the protocol as right now not all ZK proofs are given for both sets of keys.
• feat: replace ZK_PDL_WITH_SLACK proof with PI-log* from CGGMP paper #39
• refactor: use DLNProof as PI-prm proof and use instead of current ring-Pedersen proofs #38
• feat: implement PI-mod proof and give the proof for the Paillier keys #40
• feat: configurable security levels for testing/release #42 - create a security levels constant which can be used over different packages. Right now for testing we use primes (instead of safe primes). These multiplicative groups modulo primes have different properties and test results may be inconclusive.
• add ZKPs to FS-DKR refresh for ensuring correctness of Paillier keys.
• can remove GG20 signing protocol as we use CGGMP20 signing.
• use merlin.cool for Fiat-Shamir transcripts. Right now we're doing FS ad-hoc in different packages and it may be susceptible to extension/custom-split attack
• use bitvec for bit vectors instead of bit operations.
• perf: safe-prime generation #46

[ivokub]

I'll start creating issues for every subtask for better organization.

[ivokub]

cc @tmpfs, @davidsemakula, @drewstone - any issues to add/remove?

[davidsemakula]

@ivokub replacing FS-DKR with aux info & key refresh from CGGMP paper.

[ivokub]

@ivokub replacing FS-DKR with aux info & key refresh from CGGMP paper.

Makes sense. But what do you think about keeping the resharing strategy of FS-DKR compared to CGGMP? AFAIK in CGGMP the parties secret share 0 and send the shares to the other parties who then add this to their local share and in FS-DKR the parties secret share their local share and send the shares to the other parties.

Changing the threshold is a lot simpler with FS-DKR approach as it is only sufficient to secret share with the new threshold configuration vs in CGGMP where we have to compute particular polynomials through 0 which cancels some some points to decrease the threshold.

But I completely agree that we have to give the proofs as define in CGGMP refresh for the updated Paillier keys etc.

[drewstone]

Looks great, my only point to add would be to not replace things if possible since we at Webb are still using GG20. If we could just add the updated / new primitives to this library that would at least preserve some of the updates we've made to mp-ecdsa. Wdyt?

[ivokub]

Looks great, my only point to add would be to not replace things if possible since we at Webb are still using GG20. If we could just add the updated / new primitives to this library that would at least preserve some of the updates we've made to mp-ecdsa. Wdyt?

One of the update (#41) would change the local key set of a party (from two sets of Paillier keys to one). Can you describe how you are using GG20 or is there a public downstream repository to check? I'll focus on non-breaking changes first

[drewstone]

Hmm ok well we are just using the state machines as is. But if we feel we must overwrite functions then that's fine. We can proceed we'll just migrate.

[drewstone]

@ivokub #43

[davidsemakula]

@ivokub So as we discussed, the main consideration for CGGMP refresh vs FS-DKR was a possible difference in the security assumptions, as I agree that it's much simpler to change the threshold for the FS-DKR approach.

So after a thorough review, my conclusion is the security assumptions are the same.

As its title suggests, CGGMP20's security model is "security with (identifiable) abort" in the "dishonest majority" setting (i.e. n > t where n is number of parties and and t is the number of tolerated corruptions). This means that CGGMP20 gives up the guarantee of robustness (i.e. ability to generate signatures/refresh shares even in the presence of malicious faults) to achieve threshold optimality (i.e. dishonest majority).

When FS-DKR defines its security model as honest majority (i.e. n > 2t) using "standard proactive security assumptions", its doing so with a guarantee of robustness (i.e. honest parties are able to refresh their shares even in the presence of malicious faults).

If CGGMP refresh were required to guarantee robustness, then it would have to operate in the honest majority setting as well, hence the security properties of the two are the same when using the same security model.

Therefore we can keep FS-DKR for this case as its very similar and more amenable to threshold changes as you pointed out above.


However, I propose that we remove the honest majority checks (i.e. n > 2t) currently performed during key refresh in FS-DKR so that the security model is consistent with all the other CGGMP20 subprotocols (i.e. keygen, presigning and signing). This current inconsistency means one can generate a 2/3 access structure and fail to refresh the shares even with all 3 parties being honest (which is undesirable IMO). IMO this library should follow the CGGMP20 security model and assume security with (identifiable) abort in the dishonest majority setting. Applications that prefer robustness in the honest majority setting can enforce that at application level.

Lastly, in addition to proofs for updated Paillier keys etc as you stated above, the FsDkrError::PublicShareValidationError error should also identify parties that fail the related commitment checks to be consistent with other CGGMP identifiable aborts.

cc @tmpfs @drewstone

[ivokub]

Thank you @davidsemakula for the review. The approach completely makes sense and also seems very intuitive. I think it would beneficial to consider the same security assumptions for different protocols.