The Round Complexity of Verifiable Secret Sharing Revisited

Verifiable Secret Sharing (VSS) is a two phase protocol (Sharing and Reconstruction) carried out among n parties in the presence of an adversary who can corrupt up to t parties. The motive of VSS is to share a secret s with n parties in a phase called sharing phase and reconstruct back in reconstruction phase while keeping the secrecy of s in between.

Definition of VSS

Let D be the distributor of s and let s comes from a field F. (s ∈ F)

The following conditions should hold good for a VSS protocol.

• Secrecy: If D is honest then the adversary's view during the sharing phase reveals no information on s: More formally, the adversary's view is identically distributed for all different values of s.
• Correctness: If D is honest then the honest parties output s at the end of the reconstruction phase.
• Strong Commitment: If D is corrupted, then at the end of the sharing phase there is a value s* ∈ F ∪{NULL}, such that at the end of the reconstruction phase all honest parties output s*. 

Definition of WSS

This is a weaker notion of VSS. In fact the only change with VSS is in the property of commitment. WSS doesn't have Strong Commitment property; instead it has a property called Weak Commitment

• Weak Commitment: If D is corrupted, then at the end of the sharing phase there is a value s* ∈ F ∪{NULL} such that at the end of the reconstruction phase, each honest party will output either s* or NULL. (Notice that it is not required that all honest parties output the same value; some may output s* and some may output NULL)

Statistical-WSS:

We say a WSS protocol is Statistical-WSS if it achieves the correctness property and weak commitment property holds except with a negligible probability.

A 2-Round Statistical-WSS with n = 3t + 1  setting

Sharing Phase

Local Computations: D does the following:

    1. Picks a random bivariate polynomial F(x; y) over F of degree t in the

variable y and degree nk + 1 in the variable x, such that F(0, 0) = s.

    2. Defines f_i(x) = F(x, i) for 1 ≤ i ≤  n.

    3. Picks random polynomials r_i(x) over F, deg(r_i(x)) = nk+1 for 1 ≤ i ≤ n.

    4. nk random, non-zero, distinct elements from F, denoted by

    α(i,1), α(i,2), α(i,k) for 1 ≤ i ≤ n:

Round 1: D sends to party Pi:

    -The polynomials f_i(x); r_i(x). Let f_i(0) be P_i's share of D's secret s.

    -The random evaluation points α(i,l) for 1 ≤ l ≤ k

    -a(j,i,l) = f_j(α(i,l)) and  a(j,i,l) = r_j(α(i,l)) for 1 ≤ l ≤ k, 1 ≤ j ≤ n.

Round 2: Party Pi broadcasts the following:

    - A random non-zero value c_i and polynomial g_i(x) = f_i(x) +

     c_i.r_i(x); deg(g_i(x)) = nk + 1

    - For a random subset of indices l₍₁₎,..., l_(k/2), the evaluation points

     α(i, l₍₁₎), ... α(i, l_(k/2)) and a(j,i,l₍₁₎), ... a(j,i,l_(k/2)) and b(j,i,l₍₁₎), ... b(j,i,l_(k/2)) for 1 ≤ j ≤ n.

Local Computation: For all parties:

    1. Party Pi is accepted by party Pj if a(i,j,l) + c_i.b(i,j,l) = g_i(α(j,l)) for all l in the

    set of indices broadcasted by P_j in Round 2.

    2. Initiate the set SH = Φ. Place P_i in SH if it is accepted by at least 2t+1 parties.

    3. If |SH| ≤ 2t disqualify dealer D. Note that SH computed by all honest parties are identical.

Reconstruction Phase, 2-rounds:

Round 1: Each P_i in SH broadcasts f_i(x); deg(f_i(x)) = nk + 1.

Round 2: Each P_j ∈ P, broadcasts all the evaluation points α(j,l) which were not

           broadcasted in the sharing phase and a(i,j,l) corresponding to those indices, for i =  
           1, .. , n.

Local Computation: For all parties:

    1. Party P_i ∈ SH is re-accepted by P_j ∈ P if for one of the newly revealed points

        it holds that a(i,j,l)  = f_i(α(j,l))

    2. Initiate the set REC = Φ. Place Pi in REC if it is re-accepted by at least

        t + 1 parties. If the shares of the parties in REC interpolate to a t degree

        polynomial g(y) then output s = g(0). Otherwise output NULL.

Property 1: satisfies (1-ε) correctness

If dealer D is honest, all parties will be in REC as well as SH. If a faulty player P_i broadcasts a polynomial f_i'(x) ≠ f_i(x), with high probability Pi will not be added to REC; because it needs to be accepted by (t+1) parties, that is at least 1 honest party. fi'(x) and fi(x) can be same in at most (2k+1) evaluation points, so a faulty party P_i is re-accepted by P_j with prob. (nk)/|F|. So prob. of any faulty party to be in REC is negligible.

Property 2: satisfies (1-ε) weak commitment

If a faulty D to be accepted, (i.e. |SH| ≥ 2t + 1) then with high probability, all honest parties will be in REC as well as in SH. If so, s* being the committed message is defined by the shares of honest parties in SH. As we require that shares of all the parties in REC define a polynomial of degree t, then either the value s* or NULL will be reconstructed.

We need to prove what we claimed at first. If an honest P_i in SH and not being in REC, then he must had been accepted by 2t+1 in sharing phase, but at most t parties re-accepted him in reconstruction phase. So there is at least one honest P_j who accepted P_i but did not re-accept it. This implies

that the evaluation points and values that P_j exposed in the sharing phase satisfies the polynomial g_i(x) that P_i broadcasted during the sharing phase, but none among remaining evaluation points that are used by P_j in the reconstruction phase, satisfies the polynomial f_i(x) produced by P_i. This means that for the selected k/2 indices l₍₁₎, .., l_(k/2), a(i,j,l) + c_i. b(i,j,l) = g_i(α(j,l)) for all indices from the set {l₍₁₎, .. l_(k/2)} and f_i(α(j,l)) ≠  a(i,j,l) for all remaining indices. But P_i chooses c_i independently of values given by D. also P_j chooses the k/2 indices randomly. So the prob. of happening the above event is 1 / _kC_k/2, which is negligible.

Property 3: satisfies perfect secrecy

When D is honest, Round 1 of sharing, adversary will know f₁(x), .., f_t(x), r₁(x),.. r_t(x), kt points on fi(x), r_i(x) for t+1 ≤ i ≤ n assuming first t parties are corrupted. Round 2 of the Sharing Phase, the adversary learns k/2 (2t+1) additional points on f_i(x) and r_i(x). Hence total points learned by adversary is kt+k/2(2t+1), less than the degree of polynomial f_i(x) on t+1 ≤ i ≤ n. This is information theoretically secure.