Secret Splitting

The dealer computes a random shared secret \(S\) and splits it into encrypted shares \(Y_i\) for each user \(i\). The dealer also shows that those encrypted shares are consistent by producing a non-interactive zero-knowledge proof of knowledge.

To achieve this, the dealer carries out the following steps:

  • Define how many shares are required to reconstruct the secret: \(t \in [1,n]\).
    This is also known as the size of the qualified subset of users.

  • Choose two polynomials with random coefficients:

    • \(f_0(i) = \sum\limits_{j=0}^{t-1} {\alpha_{j}}_0 i^j,~ {\alpha_{j}}_0 \in_R Z_q\)

    • \(f_1(i) = \sum\limits_{j=0}^{t-1} {\alpha_{j}}_1 i^j,~ {\alpha_{j}}_1 \in_R Z_q\)

  • Compute the shared secret:
    \(S = G_0^{f_0(0)} G_1^{f_1(0)} = G_0^{{\alpha_0}_0} G_1^{{\alpha_0}_1}\).
  • Compute commitments for the coefficients:
    \(C_j = g_0^{{\alpha_j}_0} g_1^{{\alpha_j}_1},~ j \in [0,t)\).

  • For each user \(i\), compute:

    • Random values for commitments:
      \({k_i}_0, {k_i}_1 \in_R Z_q\)
    • Encrypted share:
      \(Y_i = {y_i}_0^{f_0(i)} {y_i}_1^{f_1(i)}\)
    • Random commitment for \(Y_i\):
      \(Y'_i = {y_i}_0^{{k_i}_0} {y_i}_1^{{k_i}_1}\)
    • Share with alternative generators:
      \(X_i = g_0^{f_0(i)} g_1^{f_1(i)}\)
    • Random commitment for \(X_i\):
      \(X'_i = g_0^{{k_i}_0} g_1^{{k_i}_1}\)

  • Compute the challenge for the zero knowledge proof using a cryptographic hash function \(c = H(G, g_0, g_1, G_0, G_1, C_j, y_i, Y_i, Y'_i, X_i, X'_i)\) with \(j \in [0,t)\) and for all users \(i\).

    How those values are serialised into an input for the hash function is not important as long as it is deterministic and impossible to generate the same serialisation for different values. The output of the hash function needs to be a non-negative integer. This can be achieved e.g. by using sha2_256 and treating the 256 bit output as an integer.

  • Compute the response for the zero knowledge proof for each user \(i\):

    • \({s_i}_0 = {k_i}_0 + c f_0(i)\)

    • \({s_i}_1 = {k_i}_1 + c f_1(i)\)

This proves knowledge of the values \(f_0(i)\) and \(f_1(i)\) that were used to calculate \(X_i, Y_i\).

The dealer then publishes the values \(t, c, C_j, Y_i, {s_i}_0, {s_i}_1\).

The shared secret \(S\) can be used to encrypt some payload, e.g. by computing a hash over it and using it as the key for some symmetric encryption function like AES-GCM. It must then be discarded.

The polynomials \(f_{0,1}\) and the random values \({k_i}_{0,1}\) are secret and must be discarded.

The values \(Y'_i, X_i, X'_i\) could be made public, but other parties can recompute them. So they are discarded too.

Verification

To verify that the public values generated by the splitting operation are consistent, the following steps are carried out:

  • For each user \(i\), compute:

    • \(Y_i' = {y_i}_0^{{s_i}_0} {y_i}_1^{{s_i}_1} Y_i^{-c}\)

    • \(X_i = \prod\limits_{j=0}^{t-1} C_j^{(i^j)}\)

    • \(X_i' = g_0^{{s_i}_0} g_1^{{s_i}_1} X_i^{-c}\)

  • Compute the challenge for the zero knowledge proof using a cryptographic hash function \(c' = H(G, g_0, g_1, G_0, G_1, C_j, y_i, Y_i, Y'_i, X_i, X'_i)\) with \(j \in [0,t)\) and for all users \(i\).

  • Verify that \(c = c'\)