Presigning and Signing SPEC

Ring-Pedersen Parameters

Unlike in the key refresh presented in the CGGMP '21 paper, FS-DKR does not result in each party having ring-Pedersen parameters. So this is something we have to append to our protocol.

It makes sense to append this to FS-DKR itself. We also need a ZK that the parameters are generated properly:

Presigning and Signing SPECs

The steps for pre-signing and signing are specified clearly in the CGGMP '21 paper.

What is missing from these SPECs

What is missing from these screenshots is how actually to implement the non-interactive zero-knowledge proofs (NIZKs), but this is also given in the paper. So we provide more screenshots.

In pre-signing round 1, we need:

In pre-signing rounds 2 and 3 we additionally need:

In pre-signing round 4, we additionally need:

In signing, we additionally need:

How to make these zero-knowledge proofs non-interactive:

All of the ZKs screenshotted above are three-move protocols. That is, they are interactive. We need to make them non-interactive.

ZKP Checklist

• Implement ring-Pedersen parameter generation and ZKP
• Implement Paillier Encryption in Range ZKP (enc)
• Implement Paillier Affine Operation with Group Commitment ZKP (aff-g)
• Implement Knowledge of Exponent Assumption vs. Paillier Encryption ZKP (log*)
• Implement Paillier Multiplication ZKP (mul)
• Implement Paillier Decryption modulo q ZKP (dec)
• Implement Multiplication Paillier vs Group ZKP (mul*)

Task summary

Certain modules are duplicated in both utilities modules, these need to be standardized to a single location.

• mta
• zk_pdl
• zk_pdl_with_slack

Overview

CGGMP paper defines ZK proof Π-mod (See Fig 16 https://eprint.iacr.org/2021/060.pdf#page=36) for ensuring that the Paillier modulus is a semiprime and gcd(N, phi(N)) = 1. There is an attack which assumes that N has many small factors described at https://www.fireblocks.com/blog/gg18-and-gg20-paillier-key-vulnerability-technical-report.

I tried searching for the implementation of Π-mod in the repository and wasn't able to find it. Does it seem right and if so, should we implement it? Or would it be sufficient if we test N not to have small factors? (for example primes up to 2**20?)

cc @davidsemakula, @tmpfs, @drewstone

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

• #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.
• #39
• #38
• #40
• #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.
• #46

Issue summary

CGGMP paper requires that the ring-Pedersen parameters is a product of safe primes. For security we need to generate 1024 bit safe primes, which is quite time-consuming. One issue is that right now we're using kzen-paillier for generating Paillier keys. It uses fixed number of Miller-Rabin primality checks, but it is more than recommended.

Additionally, we could use https://eprint.iacr.org/2003/186.pdf - right now we sieve p,q individually but the paper recommends an unified sieve, giving potentially 15x speedup

Say you have $t$ Shamir secret shares of a $t-1$ degree polynomial $(x_{i_1},...,x_{i_{t}})$ and a corresponding secret $x$.

Let the corresponding Lagrange basis polynomials be $(l_{i_1},...,l_{i_t})$.

Then:
$$x = (x_{i_1},...,x_{i_{t}}) \cdot (l_{i_1}(0),...,l_{i_t}(0))$$

So to convert the $x_i$ to additive shares simply multiply by $l_{i}(0)$. Where do we get the Lagrange basis polynomials evaluated at 0...Zengo has already done it for us here. So we don't have to reimplement.

Describe the bug

Just saw this failure, subsequent test run passes ok:

running 21 tests
test utilities::aff_g::tests::test_affine_g_proof ... ok
test utilities::dec_q::tests::test_paillier_decryption_modulo_q ... FAILED
test utilities::enc::tests::test_paillier_encryption_in_range_proof ... ok
test utilities::log_star::tests::test_log_star_proof ... ok
test utilities::mta::range_proofs::tests::alice_zkp ... ok
test presign::state_machine::test::presign_all_parties_works ... ok
test sign::state_machine::test::sign_all_parties_works ... ok
test utilities::mta::test::test_mta ... ok
test utilities::mul::tests::test_paillier_mul ... ok
test utilities::mul_star::tests::test_mul_star_proof ... ok
test utilities::zk_pdl_with_slack::test::test_zk_pdl_with_slack ... ok
test utilities::zk_pdl::test::test_zk_pdl ... ok
test utilities::zk_pdl_with_slack::test::test_zk_pdl_with_slack_soundness - should panic ... ok
test presign::state_machine::test::presign_threshold_works ... ok
test sign::state_machine::test::sign_threshold_works ... ok
test utilities::mta::range_proofs::tests::bob_zkp ... ok
test refresh::state_machine::test::test_dkr_with_remove_parties ... ok
test refresh::state_machine::test::test_dkr_with_no_new_parties ... ok
test refresh::state_machine::test::test_dkr_with_new_threshold ... ok
test refresh::state_machine::test::test_dkr_with_replace_parties ... ok
test refresh::state_machine::test::test_dkr_with_new_parties ... ok

failures:

---- utilities::dec_q::tests::test_paillier_decryption_modulo_q stdout ----
thread 'utilities::dec_q::tests::test_paillier_decryption_modulo_q' panicked at src/utilities/dec_q/mod.rs:168:79:
called `Result::unwrap()` on an `Err` value: [5, 125, 189, 169, 34, 120, 151, 194, 233, 222, 20, 200, 108, 156, 213, 51, 130, 65, 232, 80, 37, 41, 158, 85, 105, 164, 15, 195, 144, 245, 96]
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Issue summary

Message types do not implement the serde Serialize and Deserialize traits which means we can't pass messages across the webassembly/javascript bindings.

I will look into adding serde support to ProtocolMessage etc so we can create bindings in webassembly.

Just wanted to let you know about this.

Other information and links

The multi-party-ecdsa library implements Serialize and Deserialize for all message types and LocalKey so that it works with wasm_bindgen so I think the CGGMP implementation should to.

Thanks!

Goal of this note is to extend $n\text{-of-}n$ CGGMP '21 to $t\text{-of-}n$ CGGMP '21 using ideas from GG '20.

Review of $(t, n)$ Feldman VSS

$(t,n)$ secret sharing is one where $t+1$ parties are needed to reconstruct secret. Let the dealer have a secret $\sigma$. Feldman VSS works as follows:

1. Dealer generates a random $t$-degree polynomial $p(z) = \sigma + a_1z +...+ a_tz^t$.
2. Dealer sends each participant $i$: $\sigma_i = p(i)$, $v_j = g^{a_j}$ (for all $j \in [1..t]$), and $v_0 = g^{\sigma}$.
3. Participant $i$ can check its share is consistent by checking: $g^{\sigma_i} = \Pi_j v_j^{i^j}$.

Phase 1

$P_i$ samples $u_i \leftarrow \mathbb{F}_q$. Set $U_i = g^{u_i} \in \mathbb{G} $. Computes a commitment to $U_i$. Broadcasts commitment to $U_i$.

Phase 2

De-commit from $U_i$. Do a $(t-1, n)$ Feldman-VSS of $u_i$. Note: each party $i$ receives a vector of length $n-1$: $(x_{i,1},...,x_{i,n})$ of secret shares. Let $x_i$ be the sum of the components of these vectors. Note that $x_i$ is $(t-1, n)$ Shamir secret sharing of the the secret key $x = \sum_i u_i$.

Note the values $X_i = g^{x_i}$ are public.

Also, set the group public key as $U_1 \cdot...\cdot U_n$, which is indeed $g^x$.

Phase 3

Each party now has access to an $x_i$ and every party knows $X_i$ for each $i$. From here on, follow CGGMP '21's key generation skipping the first step of round 1 (sampling $x_i \leftarrow \mathbb{F}_q$ and setting $X_i = g^{x_i}$). Also skip the second step of the output (setting $X = \prod_i X_i$). Basically, follow CGGMP '21's steps for the Schnorr proof that party $i$ knows the discrete log of $X_i$.

Issue summary
When we originally modified the Zengo mp-ecdsa, we added additional encryption to P2P messages because we were originally broadcasting/gossiping all messages over our network,

Some old commits which added this extra encryption are:

• webb-tools/multi-party-ecdsa@a4895af
• webb-tools/multi-party-ecdsa@033d799
• webb-tools/multi-party-ecdsa@cd894b6
• webb-tools/multi-party-ecdsa@1ef80e1

I think we should remove this and make more explicit how this type of message can be encrypted before the P2P messages hit the wire.

Goal of this note is to extend $n\text{-out-of-}n$ CGGMP '21 key refresh to $t\text{-out-of-}n$ CGGMP '21

For notation and how keygen works please see: #2

There are two sets of secret values from keygen the $u_i$'s and the $x_i$'s. The $u_i$'s are an $n\text{-out-of-}n$ additive secret sharing of the secret key $x$ and the $x_i$'s are a $t\text{-out-of-}n$ Shamir secret sharing of the secret key $x$.

An attacker that compromises EITHER of these sets of values will learn the secret $x$. We can add to the keygen protocol for each party to delete the $u_i$'s since they are not used in presigning/signing. Things are secure even if one party deletes this toxic waste.

We can refresh the $x_i$'s using Foque-Stern DKR.
fs-dkr-notes.pdf

Another way to key refresh

Let the $t-1$ degree polynomial that can be reconstructed by any $t$ $x_i$'s be $p$.

Each party Feldman VSS shares $0$. So party $i$ receives $p_1(i),...,p_{i-1}(i), p_{i+1}(i)...p_n(i)$, where each $p_j$ is a random $t-1$-degree polynomial with constant term $0$.

Each party makes its new $x_i := x_i + \sum_{j} p_j(i) = (p+p_1+...p_n)(i)$. Note $(p+p_1+...+p_n)$ is a $t-1$-degree polynomial with constant term equal to the secret key $x$, as desired. The new $X_i=g^{x_i}$ are now also public. Each party provides a Schnorr proof that it knows $x_i$ (the discrete log of $X_i$).

@drewstone, I have mentioned that the curv library doesn't seem to be maintained (see this comment) and it would be good for us to forge a path towards using the constant time crypto-bigint library as the BigInt backend which would require forking curv.

And then I just came across this security advisory regarding the secp256k1 library that curv depends upon.

I have searched the codebase(s) and I don't think we are exposed to the issue with Secp256k1::preallocated_gen_new however I do want to start a conversation about what we should do with the curv dependency.

/cc @davidsemakula @ivokub

Very high level overview of fs-dkr

• New parties joining broadcast a JoinMessage.
• Each already existing party broadcasts a RefreshMessage to every other party
• Every party validates and constructs new secret key share from the RefreshMessage's it receives.

Main takeaway from the above section:

• Existing parties and newly joining parties have different behaviors, so the state machine somehow has to account for this.

State Machine for GG '20

What is a state machine?

• A system that can be in any one of a finite number of states $S = {S_1, S_2,...}$ at any given time.
• Has a deterministic transition function $T: (S, M) \rightarrow S$, where $M$ is the message space $M$ of inputs to the state machine.

Contextualizing w.r.t. GG '20. The KeyGen struct makes up the state space, message space, and transition function for each party. Let's be more specific:

• The state space is the round attribute.
• The message space is msgs1, msgs2,.... Note each of these is a collection of messages.
• The transition function is the proceed function.

Basically things work as follows. The handle_incoming function on the StateMachine trait adds a message to a message store. Once the store is filled (a.k.a. the messages have been received from all parties), the state machine is ready to transition state via the proceed function, since it has access to the full message.

State Machine for fs-dkr

Round 0

The initial state will be an Option<LocalKey<Secp256k1>>. If this Option is None then it corresponds to a newly joining party and if it corresponds to an already existing party.

pub struct Round0 {
    local_key: Option<LocalKey<Secp256k1>>
}

Round 0 -> Round 1

The proceed transition from round 0 to round 1 does not entail receiving any messages. Rather the state transition works as follows:

• Generate and broadcast a Option<JoinMessage> (see here).
• This option will be None if local_key is Some and Some if local_key is None.

The round 1 struct looks like:

pub struct Round1 {
    local_key: LocalKey<Secp256k1>,
...
}

Notice here local_key is no longer an Option since every party has generated their local keys.

Round 1 -> Round 2

The transition from round 1 to round 2 entails receiving BroadcastMsgs<Option<JoinMessage>> as the messages. The proceed transition function receives these messages and:

• Updates its local_key. Specifically, the JoinMessage's of the new parties contain Paillier keys so the paillier_key_vec attribute of local_key needs to be updated (for each existing party).
• Each existing party broadcasts a RefreshMessage see here.

The round 2 state looks like:

pub struct Round2 {
    local_key: LocalKey<Secp256k1>,
...
}

...with the updated local_keys.

Round 2 -> Final Output

Each party receives BroadcastMsgs<Option<RefreshMessage>> does the relevant checks and updates its local_key accordingly. The final state is a new LocalKey.

Todos for implementation

• Implement KeyRefresh struct:
• Implement StateMachine trait for KeyRefresh struct
• Implement Round0, Round1, Round2 structs.

Describe the bug

Some tests are flaky due to a [u8; 32] conversion that fails when the byte length is less than 32.

For details, see: #26 (comment)

Replaces #27.

Expected behaviour

Tests always pass.

As this library was built on top of the ZenGo library I assume it is also vulnerable to the c-split attack documented here:

https://www.verichains.io/tsshock/

Can somebody verify this please?

The webassembly checks are broken on Linux, see this comment for more information.