search

unboundsecurity / blockchain-crypto-mpc

Protecting cryptographic signing keys and seed secrets with Multi-Party Computation.
GNU General Public License v3.0
456 stars 165 forks source link

some observations on Share Refresh #1

Closed omershlo closed 5 years ago

omershlo commented 5 years ago

Hi,

Referring to ecdsa Share Refresh as described in text https://github.com/unbound-tech/blockchain-crypto-mpc/blob/master/docs/Unbound_Cryptocurrency_Wallet_Library_White_Paper.md#56-share-refresh and in code https://github.com/unbound-tech/blockchain-crypto-mpc/blob/74a4864b940e74f4da9858bf6b51202bb6ee2a7a/src/mpc_protocols/mpc_ecdsa.cpp#L473

  1. Since a new Paillier key pair is generated, I think that a zk proof that the Paillier public key was generated correctly is needed (same as in Key Generation).
  2. It is important to note that the new value encrypted under pailliler is not the same value as the private key because of the modulo operation. I.e. for Alice the private key is x1' = x1 + r mod q and the paillier encryption is for x1 + r. Theoretically after many rotations some bits could be leaked but in practice this is a very big number. Since in signing r part of the encryptions cancel out the difference between the private key and its encryption does not matter much.
Samuel-Ranellucci commented 5 years ago

  1. Regarding your first point, thank you for catching this. Indeed, the zero-knowledge proof that the Paillier key is generated correctly was mistakenly omitted from the refresh, but obviously must be included (as in key generation). We have added this zero-knowledge proof to the refresh.

  2. Regarding your second point: no bits can be leaked by the addition of r in refresh. In order to see this, observe that by not doing a modular reduction, the encrypted value can increase by at most q each time. Now, by the ECDSA two-party paper (https://eprint.iacr.org/2017/552.pdf, Protocol 3.2, Step 4c), the second party must choose noise \rho in \Z{q^2} in the signing protocol to ensure no leakage. Thus, for an encryption of the private key of size up to q, the amount of noise needed is random in \Z{q^2}. However, in our implementation, we add noise \rho in \Z_{q^2 2^80}. This means that we prevent leakage as long as the encryption of the private key is a value at most q 2^{80}. This means that as long as the number of refreshes done is at most 2^{80} (can never feasibly be reached), the amount of noise added is sufficient to prevent any leakage.

Thank you again for your review and help in improving our library.