Algorithms

Overview

Shamir's Secret Sharing is an algorithm in cryptography created by Adi Shamir. It is a form of secret sharing, where a Secret is divided into Shares, giving each participant its own unique Share. To reconstruct the original Secret, a minimum number of Shares is required. In the threshold scheme, the Secret is divided into $n$ Shares and at least $k$ Shares are required to reconstruct the orignial Secret.

Even though a lot of services and systems nowadays are using SSS to protect the user's Private Key, but SSS is safe only when the generation of keys are done in one environment without any communication between the participants. That's why we only apply it at the client to divide the user's Private Key into Factors.

When it comes to servers where everything is vulnerable, or a distributed network where the node operators are anonymous, there is no way to apply any cryptographic technique on SSS to protect the Secrets.

Our implementation

In our application, we have 3 Factors which are Network Factor, Device Factor and Recovery Factor. Also on this Cartesian coordinate system, we can generate as many Child Keys as needed by choosing the x-value randomly and calculate the corresponding y-value.

[object Object] — Figure 1: Shamir's Secret Sharing (SSS) algorithm

But since all of those Keys following a single polynomial, if user cannot reconstruct this straight line, everything will be lost.

For detailed information about this process, please refer to Keystore Mechanisms page.

Overview

The predecessor of this algorithm is from Distributed Key Generation (DKG) process from Torus Labs. The DSS algorithm is a advanced version of SSS in which it is safe to generate the keys in a distributed environment without having to share the Secrets between the participants.

Our implementation

In our application, we use 5 nodes whose the polynomial is of degree 2. In future, we also plan to increase the number of nodes to 9 in future (which means the degree of the polynomial is 3). But to make it simple, the following example is for the 3-node system.

In which, $\Sigma\text{z}_{*}$ is the Network Key (or called as Master Secret in the algorithm context), it can be calculated by the sum of Secrets $\text{s}_{*}$ from the nodes. But instead, we apply an SSS for each node to divide its Secret into Shares and deliver each of them corresponding to each of the other nodes.

When all the nodes complete the sharing process, each of them can construct its Master Share by calculate the sum of the Shares it recevied and transfer it to the client. The process is of course masked by an encryption layer.

The client after receiving all the Master Shares from the nodes, it can calculate the Network Key by applying Lagrange interpolation to 2/3 of the Master Shares to construct the Master Share's Polynomial and intersect it with the y-axis.

In short, the DSS algorithm is a set of SSS algorithms corresponding to each of the nodes in the network.

Proof

Considering node 1, we can see that $\left(1, s_1^1\right)$ , $\left(2, s_1^2\right)$ and $\left(3, s_1^3\right)$ are the points on the polynomial $f_1(x) = z_1 + \alpha_1x$ . Therefore, we have a system of linear equations:

\begin{cases} z_1 + 1\alpha_1 = s_1^1 \\ z_1 + 2\alpha_1 = s_1^2 \\ z_1 + 3\alpha_1 = s_1^3 \end{cases}

We can represent this for any $i$ -th node by transforming it into a matrix equation as $\textbf{A} \times \textbf{z}_i = \textbf{s}_i$ :

\begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix} \begin{bmatrix} z_i \\ \alpha_i \end{bmatrix} = \begin{bmatrix} s_i^1 \\ s_i^2 \\ s_i^3 \end{bmatrix}

Similarly, we also have $\textbf{A} \times \Sigma\textbf{z}_* = \Sigma\textbf{s}_*$ since $\left(1, \Sigma s_*^1\right)$ , $\left(2, \Sigma s_*^2\right)$ and $\left(3, \Sigma s_*^3\right)$ are the points on the polynomial $f_*(x) = \Sigma z_* + \Sigma\alpha_*x$ :

\begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix} \begin{bmatrix} \Sigma z_* \\ \Sigma \alpha_* \end{bmatrix} = \begin{bmatrix} \Sigma s_*^1 \\ \Sigma s_*^2 \\ \Sigma s_*^3 \end{bmatrix}

Since we have $\textbf{z}_i = \begin{bmatrix} \textbf{A} \mid \textbf{s}_i \end{bmatrix}$ are already non-singlar matrices for every $i$ . Therefore, $\Sigma \textbf{z}_* = \Sigma{\begin{bmatrix} \textbf{A} \mid \textbf{s}_* \end{bmatrix}} = \begin{bmatrix} n \times \textbf{A} \mid \Sigma\textbf{s}_* \end{bmatrix}$ is also non-singular (from positive-definiteness property).

Thus, the row-echelon form $\Sigma\textbf{z}_* = \begin{bmatrix} \textbf{A} \mid \Sigma\textbf{s}_* \end{bmatrix}$ is a non-singular matrix (from consistency of the augmented matrix property), which leads the system of linear equations $\textbf{A} \times \Sigma\textbf{z}_* = \Sigma\textbf{s}_*$ to have a unique solution, or $\Sigma z_*$ is valid and unique. We call it Master Secret.

The same proof can be also applied for any polynomials of degree $k$ with $n$ nodes (in which $k \leq n$ ).

\begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & 2 & 4 & \cdots & 2^k \\ 1 & 3 & 9 & \cdots & 3^k \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & n & n^2 & \cdots & n^k \end{bmatrix} \begin{bmatrix} z_i \\ \alpha_i \\ \alpha_i^2 \\ \vdots \\ \alpha_i^k \end{bmatrix} = \begin{bmatrix} s_i^1 \\ s_i^2 \\ s_i^3 \\ \vdots \\ s_i^n \end{bmatrix}

Overview

Regarding to the DSS algorithm above, we can see that 3/3 nodes are needed to generate the Network Key and 2/3 nodes are needed to derive the Key. Therefore, if one of the nodes is down, the system will be unavailable for users to register (but still available for the existing users to login).

Our implementation

To solve this problem, we apply a mechanism that a node will supervise another node circularly and be responsible to simulate that node's behavior (e.g creating Secret and delivering Shares on its behalf) when that node is down.

But in the 3-node system, this is completely dangerous because in this case, one node can control 2/3 of the network, which is enough to manipulate the user's Master Key. Luckily, our system implements 5 nodes, which can prevent this vulnerability. But we only accept this mechanism when JUST ONE node is down, if there are 2 nodes, there are two cases:

The second down node is the one that is supervised by the first down node: There is not enough nodes.
The second down node is not the one that is supervised by the first down node: The system is vulnerable because there are 2 nodes controlling 2/5 of the network.

That's why, in the 5-node system, 4/5 nodes are needed to generate the Network Key and 3/5 nodes are needed to derive the Network Key.

Overview

After having applied the ISS algorithm to ensure the system's availability, we must recover the data generated by its supervising node. Of course we will not allow the supervising node to save that data and deliver directly to that node. Instead, we will apply a algorithm that allows the other nodes to consensually recover the data by sharing the Shares they generated for that node.

Overview

In a distributed and trustless network, there is no way to ensure that a node will keep the data safe and private after a node joins and leaves the network. That's why we apply a mechanism that allows the nodes to proactively update their Shares and Master Shares whenever a node leaves the network.

Overview

In addition to the vulnerabilities for a distributed key management system that we mentioned above, there is a problem that the nodes can generate fake Shares and Master Shares to falsify the system and Keys. To solve this problem, we apply a Zero-Knowledge mechanism to prove that the Shares that a node delivered are valid without forcing it to reveal its Secret.

Algorithms

Shamir's Secret Sharing (SSS)

Overview

Our implementation

Distributed Secret Sharing (DSS)

Overview

Our implementation

Proof

Interchangeable Secret Sharing (ISS)

Overview

Our implementation

Recoverable Secret Sharing (RSS)

Overview

Proactive Secret Sharing (PSS)

Overview

Verifiable Secret Sharing (VSS)

Overview