Key Generation and Resharing

Key Generation

Since key generation is an activity that requires several rounds of communication, it is unwise to do this whenever a user requires new keys. Instead, we generate buffers of unassigned keys ahead of time, so that we only need to assign them to users when they request for new keys.‌

We run this Distributed Key Generation (DKG) via a cryptographic scheme called Asynchronous Verifiable Secret Sharing (AVSS) by Cachin et al. (2002). The main advantage the DKG has over the other well-known DKGs like Pedersen DKG, Feldman's VSS and its variants is that it is fully asynchronous and thus does not require a complaint phase when we consider the allowance for a small zero-knowledge proof. This results in a simpler implementation (with constant communication rounds even during malicious scenarios), but at the expense of message size.

In brief, this scheme generates a random bivariate polynomial (i.e. 2D surface) and creates horizontal (X) and vertical (Y) slices at the appropriate indices as sharings. We then get sub-sharings (points) on these horizontal and vertical sharings at the appropriate indices and echo them to other nodes. As a node, the polynomial reconstructed from the sub-sharings received from other nodes should match up with the initial sharing that the node received from the dealer, and even if they do not, the node can always interpolate the correct sharing via these echoed sub-sharings. This eliminates the dealer complaint phase. We then we restrict ourselves to just the horizontal (X) domain such that our final sharings are still on that of a univariate polynomial, which is what a typical DKG does.‌

At the end of the distributed key generation process, the nodes are left with a (polynomial) share to a master polynomial. This master polynomial is the sum of all the initial polynomials which were generated by each participating node. Since a threshold number of nodes contributed to this master polynomial's randomness, it is not possible for any non-threshold subset of nodes to recover its coefficients.

The constant coefficient of this master polynomial is the user's private key.

Proactive Secret Sharing

The Torus network functions in epochs. Each epoch has a set of nodes that are in charge of the node operations, and when they are done, they migrate the necessary state over to the next epoch's nodes. Since our entire system does not store any state other than the mappings of TorusIDs to user IDs and private keys, the only systems needed are the ones that migrate mappings and private keys across epochs.‌

The migration of keys uses Proactive Secret Sharing (PSS), also from the AVSS paper. Simply copying shares across epochs is a bad idea, since a single node operator operating in two separate epochs would get access to two shares, and it also makes it not possible to increase or decrease the number of operators in each epoch.

In brief, the key idea is that we create polynomial sharings of the existing key shares and add these polynomials in a specific way such that the coefficient of the master polynomial is the Lagrange interpolation of the existing key shares. Much like how DKGs are the sum of several secret sharings, where the master secret is the sum of all of the secrets from each of the N-parallel secret sharing protocols, we can do the same thing by setting N-parallel secret sharing protocols to be run by the original set of nodes, with their "secret" as their share. The resulting shares of shares, if added appropriately (multiply them by Lagrange coefficients first), would lead to a re-sharing on the original secret.