FS-DKR: One Round Distributed Key Rotation


FS-DKR: One Round Distributed Key Rotation


In this note we aim to re-purpose the Fouque-Stern Distributed Key Generation (DKG) to support a secure Distributed Key Refresh (DKR). As we claim, FS-DKR is well suited for rotation of threshold ECDSA keys.


The FS-DKG protocol is a one round DKG based on Publicly Verifiable Secret Sharing (PVSS) and the Paillier cryptosystem. There are two major security shortcomings to FS-DKG:

  1. It introduces a factoring assumptions (DCRA)
  2. it is insecure against rushing adversary

Rushing adversary is a common assumption in Multiparty Computation (MPC). In FS-DKG, an adversary waiting to receive messages from all other parties will be able to decide on the final public key. In the worst case it can lead to a rouge-key attack, giving full control of the secret key to the attacker. This is the main reason, in our opinion, why FS-DKG, altough with prominent features, was over-looked for the past 20 years. in this write-up we show how by adjusting FS-DKG to key rotation for threshold ecdsa the above shortcomings are avoided.

Our Model

We use standard proactive security assumptions. The protocol will be run by $n$ parties. We assume honest majority, that is, number of corruptions is $t<n/2$. The adversary is malicious, and rushing. For communication, the parties have access to a broadcast channel (can be implemented via a bulletin board). For threshold ECDSA, we focus on GG20 protocol, currently considered state of the art and most widely deployed threshold ecdsa scheme (e.g. multi-party-ecdsa, tss-lib).

High-level Description of FS-DKG

Here we give a short description of the FS-DKG protocol. FS-DKG works in one round. This round includes a single broadcast message from each party $P_j$. For Setup, we assume every party in the system has a public/private key pair for Paillier encryption scheme. At first, $P_j$ picks a random secret $s$ and secret shares it. $P_j$ publishes one set of size $t$ of commitment points $\textbf{A}$ corresponding to the polynomial coefficients: $A_i = a_iG$, and one set of $n$ commitment points $\textbf{S}$ corresponding to $n$ points on the polynomial: $S_i = \sigma_i G$. The points on the polynomial are also encrypted using the paillier keys of the receiving parties: $Enc_{pk_i}(\sigma_i)$. Finally, $P_j$ computes zero knowledge proofs $\pi_i$ to show that the paillier encryption for $P_i$ encrypts the same value commited in $S_i$. The ZK proof is a sigma protocol (can be made non-interactive using Fiat-Shamir) given in the original FS paper under the name proof of fairness. We implemented it under the same name.

Verification proceeds as follows. Each party $P_j$ verifies:

  1. all broadcasted proofs of fairness
  2. all secret sharing schemes - computing the polynomial points "at the exponent"

The parties define the set $\mathcal{Q}$ to be the set of the first $t+1$ parties for which all checks passed. we now show a simple optimization on how each party computes its local secret key: Each party maps its encrypted shares from ${t,n}$ to ${\mathcal{Q},\mathcal{Q}}$. It then homomorphically adds all the paillier ciphertext (which is an additive homomorphic scheme) and decrypts to get the local secret key.

Adjusting FS-DKG to DKR and threshold ECDSA

We will now highlight the adjustments required for FS-DKR. In a key refresh protocol the parties start with their inputs equal to the outputs of a DKG done in the past or the output of previous DKR. Meaning, as opposed to FS-DKG protocol in which the inputs are pseudorandom such that the attacker can bias the output, for example in a rushing adversary attack, FS-DKR avoids this potential attack on FS-DKG because of the added restriction over the inputs of the attacker. Concretely, in the case the parties must reshare their DKG/DKR output secret share, all other parties already know a public commitment to the attacker secret share and can check for it. Recall that FS-DKG is secure assuming Paillier is secure (what we called DCRA assumption). Moreover, we assumed a setup phase in which all parties generate paillier keys and share them. This fits well with threshold ECDSA: First, GG20 already requires us to assume Paillier security, therefore in this particular case, no new assumption is needed. The setup phase actually happens as part of GG20 DKG. We will use this to our advantage, running the FS-DKR using the GG20-DKG paillier keys. Obviously because we need to refresh the paillier keys as well we will also add a step to FS-DKR to generate new paillier keys and prove they were generated correctly. This is a standard proof, that can be made non-interactive. See the zk-paillier lib for an implementation.

Adding/Removing parties: There is a clear distinction between parties with secret shares (”Senders”) and new parties (”Receivers”). The FS-DKR protocol therefore supports adding and removing parties in a natural way: Define $\mathcal{J}>t+1$ the subset of parties participating in the protocol. To remove an existing party $P_i$, other parties exclude it from the subset $\mathcal{J}$. To add a new party, we assume the parties in $\mathcal{J}$ are aware of the new party' paillier key. In that case, the parties in $\mathcal{J}$ assign an index $i$ to the new party and broadcast the PVSS messages to it. Removal of a party is simply done by not broadcasting the encrypted messages to it. If enough parties decide on that for a party index, they will not be able to reconstruct a rotated key.

Identifiable Abort: A nice property of FS-DKR is that if a party misbehaves all honest parties learn about it. This is due to the nature of PVSS used in the protocol. As GG20, our reference threshold ECDSA protocol, also have this property, it is important that identifiable abort can be guaranteed throughout the DKR as well.

For completeness, Below is the FS-DKR protocol, written as FS-DKG with changes in red for DKR. The protocol is implemented in the ZenGo-X/fs-dkr repo (warning, the code is not audited yet).

Related Work

Our main requirement from FS-DKR is minimal round-count. In FS-DKR the parties can pre-process all the data they need to send. Our main bottleneck is $\mathcal{O}(n^2)$ communication, which seems a standard cost in our context: It is the same asymptotic complexity as we have in GG20-DKG and GG20-Signing.

In this section we focus on alternative protocols for DKR. Three recent results come to mind. The first one, CGGMP20, is another threshold ECDSA protocol with a companion refresh protocol, see figure 6 in the paper. Their protocol has the most resemblance to FS-DKR, with few notable differences. First, while FS-DKR is publicly verifiable, CGGMP20-DKR current version suffers from a technichal issue with its Identifiable Abort (acknowledged by the authors). Second, the paillier keys used in the CGGMP20-DKR are the new ones, while in FS-DKR, we use the old ones, already known to all, which helps us save a round of communication. Finally, CGMMP20-DKR key refresh is done by adding shares of zero while in FS-DKR we re-share existing shares. Overall we treat the similarities between the protocols as a positive signal of validation for FS-DKR. A second protocol, by Gurkan et. al., uses gossip for aggregating transcripts from the parties. However, their DKG is generating group elements secret shares and we need field elements secret shares for our threshold ECDSA. The third relevant work is Jens Groth' Non interactive DKG and DKR. There, instead of paillier encryption, they use El-Gamal based encryption scheme that offers forward security. Their DKR makes the assumption that the El-Gamal decryption keys are long-term and not rotated. This assumption seems crucial for the Groth-DKG construction. In our context it means that we need to let the parties generate, store and use a new set of keypair,in addition to the Paillier keypair, and that this new keypair poses a security risk against the classical mobile adversary, which our model does not allow. As opposed to Groth-DKR, FS-DKR is reusing the existing paillier keypair and rotate it as well. In terms of efficiency - there is no complexity analysis given in the paper, however, from inspection we estimate the asymptotic complexity is comparable to FS-DKR (quadratic in the number of parties).


We thank Claudio Orlandi, Kobi Gurkan and Nikolaos Makriyannis for reviewing the note

  • Update versions of packages

    Update versions of packages


    Updates all packages to the latest versions they have in the other repos so that it's consistent with multi-party-ecdsa master. It is needed to generalize some types to make this consistent there as well.

    Would appreciate reviews if possible. All but one tests are passing at the moment. Currently, the failing test is:

    running 6 tests
    test proof_of_fairness::tests::test_bad_fairness_proof - should panic ... ok
    test proof_of_fairness::tests::test_fairness_proof ... ok
    test test::tests::test1 ... ok
    test test::tests::test_add_party ... FAILED
    test test::tests::test_remove_sign_rotate_sign ... ok
    test test::tests::test_sign_rotate_sign ... ok
    ---- test::tests::test_add_party stdout ----
    thread 'test::tests::test_add_party' panicked at 'Incorrect Alice's range proof in MtA: InvalidKey', /Users/drew/webb/multi-party-ecdsa/src/protocols/multi_party_ecdsa/gg_2020/state_machine/sign/rounds.rs:156:14

    Namely, it fails to simulate_offline: https://github.com/webb-tools/fs-dkr/blob/drew/update-versions/src/test.rs#L162-L164

    simulate_replace(&mut keys, &[2, 7], t as usize, n as usize).unwrap();
    let offline_sign = simulate_offline_stage(keys, &[1, 2, 7]);
    simulate_signing(offline_sign, b"ZenGo");
    opened by drewstone 3
  • dkr-remove problem

    dkr-remove problem

    Hi teams. After I use dkr-removal, I use the removed keypair to sign and it is normal.

    Test case code

    fn test_remove_sign_rotate_sign() {
            let mut keys = simulate_keygen(2, 5);
            let offline_sign = simulate_offline_stage(keys.clone(), &[1, 2, 3]);
            simulate_signing(offline_sign, b"ZenGo");
            simulate_dkr_removal::<{ M_SECURITY }>(&mut keys, [1].to_vec());
            let offline_sign = simulate_offline_stage(keys.clone(), &[1, 3, 4]); // index 1 has been removed
            simulate_signing(offline_sign, b"ZenGo");
            simulate_dkr_removal::<{ M_SECURITY }>(&mut keys, [1, 2].to_vec());
            let offline_sign = simulate_offline_stage(keys, &[3, 4, 5]);
            simulate_signing(offline_sign, b"ZenGo");
    opened by jacksoom 0
  • write a test with multiple refresh cycles

    write a test with multiple refresh cycles

    refresh is repeating operation - write a test with few consecutive refreshes. Make sure that each time the same joint public key is outputted not secret shares are not the same

    opened by omershlo 0
  • add new paillier keys to DKR

    add new paillier keys to DKR


    As part of thee DKR we need each party to generate a new paillier keypair and broadcast it together with a proof of correctness (proof can be taken from: https://github.com/ZenGo-X/zk-paillier/blob/master/src/zkproofs/correct_key_ni.rs)

    opened by omershlo 0
  • What is the purpose of the local public key tpk_i?

    What is the purpose of the local public key tpk_i?

    What happens if we don't verify that $A_{0}^{(a)} = tpk_{(a)}^{old}$ in step 2 of the FS-DKR protocol?

    Also why does $tpk$, the group public key stay the same from FS-DKG to FS-DKR?

    opened by saiakilesh 1
  • Replace proof of fairness with a PDL with Slack proof from GG18/20

    Replace proof of fairness with a PDL with Slack proof from GG18/20

    This utilizes the PDL With Slack ZK proof from GG18/20 (https://github.com/ZenGo-X/multi-party-ecdsa/tree/master/src/utilities/zk_pdl_with_slack) and uses range-proofs from https://github.com/ZenGo-X/multi-party-ecdsa/pull/145 to validate it. Also added a check for the moduli size to make sure it's ~2048 bits.

    I still need to update the Readme to remove any mention of the fairness proof

    opened by elichai 0
  • Assert that t <= n/2 and add examples to the readme

    Assert that t <= n/2 and add examples to the readme

    This adds an assertion of the assumption that t <= n/2 to RefreshMessage::distribute. And adds documentation on how to replace refresh the keys or replace a party

    opened by elichai 0
  • dlog proofs bug

    dlog proofs bug

    Currently we follow multi-party-ecdsa logic of two dlog proofs see here: https://github.com/ZenGo-X/fs-dkr/pull/17/files#diff-386a609f746d74ecbc3e04d7ae0e82e2e7a58a72a16908d2fbbb955b9d355971R73

    There is a bug in this logic, as can be explained and fixed here: https://github.com/ZenGo-X/multi-party-ecdsa/pull/145#issuecomment-953734674

    please apply the same fix here as well

    opened by omershlo 1
  • Existing Parties DLog proof

    Existing Parties DLog proof

    Existing parties should submit their dlog proof as well (currently it's a bit cumbersome, as the LocalKey does not save the proofs and the secret is not available anymore later).

    opened by tudorcebere 0
[ZenGo X]
Threshold cryptography for blockchains. Projects with "city" in name are work in progress.
[ZenGo X]
A distributed, cryptographically-verifiable blog / social network

FeoBlog FeoBlog is a distributed blogging platform. It takes a lot of its inspiration from Mastodon and Scuttlebutt. It aims to solve a couple of prob

Cody Casterline 71 Dec 11, 2022
End-to-end encryption and mutual authentication for distributed applications.

✨ Hands-on Introduction: Build end-to-end encrypted, mutually-authenticated, secure messaging in Rust ✨ Rust and Elixir libraries for end-to-end encry

Ockam | Trust for Data-in-Motion 2.8k Jan 2, 2023
This is an experiment in designing a distributed connected garden experience.

This is an experiment in designing a distributed connected garden experience. It started as an implementation of a blockchain, but has moved on to be a bit more than that. There is no proof of work like a cryptocurrency, but plays with the idea of a distributed consensus-building system.

Greg Tatum 4 Feb 28, 2022
Distributed Vault For Your Secrets

https://meta-secret.github.io Application Design Activity Diagram graph TD User --> |split password| MSS{MetaSecret} MSS --> |split| Hash1

Meta Secret 4 Nov 9, 2022
The fly.io distributed systems challenges solved in Rust

The fly.io distributed systems challenges solved in Rust. Live-streamed in https://youtu.be/gboGyccRVXI License Licensed under either of Apache Licens

Jon Gjengset 162 Apr 19, 2023
🐴 RusTOTPony — CLI manager of one-time password generators aka Google Authenticator

?? RusTOTPony CLI manager of time-based one-time password generators. It is a desktop alternative for Google Authenticator. Installation Arch Linux Pa

German Lashevich 23 Jan 5, 2023
Aptos-core strives towards being the safest and most scalable layer one blockchain solution.

Aptos-core strives towards being the safest and most scalable layer one blockchain solution. Today, this powers the Aptos Devnet, tomorrow Mainnet in order to create universal and fair access to decentralized assets for billions of people.

Aptos Labs 4.7k Jan 6, 2023
tool for generating wordlists or extending an existing one using mutations.

gorilla gorilla is the ultimate wordlist tool packing a lot of amazing utilities like: building wordlists based on patterns (like crunch) building wor

andrei 348 Jan 3, 2023
An all-in-one IBC protocol providing fungible token transfer, interchain account, and async query functionalities

ICS-999 An all-in-one IBC protocol providing fungible token transfer, interchain account (ICA), and query (ICQ) functionalities, implemented in CosmWa

larry 9 Apr 1, 2023
HD wallet BIP-32 related key derivation utilities.

HDWallet Docs HD wallet(BIP-32) key derivation utilities. This crate is build upon secp256k1 crate, this crate only provides BIP-32 related features,

jjy 23 Nov 27, 2022
X25519 elliptic curve Diffie-Hellman key exchange in pure-Rust, using curve25519-dalek.

x25519-dalek A pure-Rust implementation of x25519 elliptic curve Diffie-Hellman key exchange, with curve operations provided by curve25519-dalek. This

dalek cryptography 252 Dec 26, 2022
An implementation of the OPAQUE password-authenticated key exchange protocol

The OPAQUE key exchange protocol OPAQUE is an asymmetric password-authenticated key exchange protocol. It allows a client to authenticate to a server

Novi 178 Jan 9, 2023
A safe implementation of the secure remote password authentication and key-exchange protocol (SRP), SRP6a and legacy are as features available.

Secure Remote Password (SRP 6 / 6a) A safe implementation of the secure remote password authentication and key-exchange protocol (SRP version 6a). Ver

Sven Assmann 10 Nov 3, 2022
Keyhouse is a skeleton of general-purpose Key Management System written in Rust.

Keyhouse Keyhouse is a skeleton of general-purpose Key Management System. Keyhouse is not an off-the-shelf system, and it's not ready for production.

Bytedance Inc. 148 Jan 1, 2023
Manage secret values in-repo via public key cryptography

amber Manage secret values in-repo via public key cryptography. See the announcement blog post for more motivation. Amber provides the ability to secu

FP Complete 82 Nov 10, 2022
A suite of programs for Solana key management and security.

?? goki Goki is a suite of programs for Solana key management and security. It currently features: Goki Smart Wallet: A wallet loosely based on the Se

Goki Protocol 157 Dec 8, 2022
🧑‍✈ Version control and key management for Solana programs.

captain ??‍✈️ Version control and key management for Solana programs. Automatic versioning of program binaries based on Cargo Separation of deployer a

Saber 35 Mar 1, 2022
Password-Authenticated Key Agreement protocols

RustCrypto: PAKEs Password-Authenticated Key Agreement protocols implementation. Warnings Crates in this repository have not yet received any formal c

Rust Crypto 81 Dec 5, 2022
Multi Party Key Management System (KMS) for Secp256k1 Elliptic curve based digital signatures.

Key Management System (KMS) for curve Secp256k1 Multi Party Key Management System (KMS) for Secp256k1 Elliptic curve based digital signatures. Introdu

[ZenGo X] 61 Dec 28, 2022