Verifiable secret sharing

Baghery's hash-based scheme

A recent line of research has proposed a unified framework, for building practical VSS schemes that do not necessarily require homomorphic commitments —a key requirement in traditional constructions such as Feldman's and Pedersen's schemes. The framework allows instantiations with different commitment schemes, including post-quantum secure options such as hash-based commitments. This offers a flexible and efficient approach to build VSS schemes, in which the verifiability of shares is decoupled from the need for homomorphic commitments, which are often tied to assumptions like the Discrete Logarithm (DL) problem, known to be insecure against quantum adversaries. One instantiation of the new framework uses hash-based commitments and a random oracle to construct a hash-based VSS scheme based on Shamir's secret sharing.

Protocol Overview

• Sharing Phase: Given a secure hash-based commitment scheme ${\displaystyle \mathcal{C}}$ and a hash function ${\displaystyle \mathcal{H}}$ (modeled as a random oracle), to share a secret value ${\displaystyle s}$ among ${\displaystyle n}$ parties with threshold ${\displaystyle t}$, the dealer acts as follows:
  1. Following Shamir sharing, the dealer samples a random degree-${\displaystyle t}$ polynomial ${\displaystyle P(X)}$ over a filed or ring, with ${\displaystyle P(0)=s}$. Each of the ${\displaystyle n}$ parties will receive a value ${\displaystyle v_i=P(i)}$ modulo ${\displaystyle q}$ as a share.
  2. To prove the validity of the shares, the dealer acts as follows:
     1. Samples another random degree-${\displaystyle t}$ polynomial ${\displaystyle R(X)}$ and ${\displaystyle n}$ random values ${\displaystyle {\gamma }_1,\dots ,{\gamma }_n}$ from the same filed or ring.
     2. Computes a set of commitments ${\displaystyle c_i=\mathcal{C}(P(i),R(i),{\gamma }_i)}$ for ${\displaystyle i=1,2,\dots ,n}$. Note that, the additional randomness ${\displaystyle {\gamma }_i}$ is used when the secret ${\displaystyle s}$ does not have sufficient entropy, but it can be omitted when sharing a uniformly random secret. Each of the ${\displaystyle n}$ parties will also receive a value ${\displaystyle {\gamma }_i}$ modulo ${\displaystyle q}$ as a share.
     3. Calculates a challenge value ${\displaystyle d}$ via a hash function ${\displaystyle d=\mathcal{H}(c_1,\dots ,c_n)}$ and then computes a polynomial ${\displaystyle Z(X)=R(X)+d\cdot P(X)}$.
     4. Broadcasts the commitments ${\displaystyle c_1,\dots ,c_n}$ along with ${\displaystyle Z(X)}$ as the proof and privately sends ${\displaystyle (v_i,{\gamma }_i)}$ as the individual share to party ${\displaystyle i}$.
• Verification Phase: Given an individual share ${\displaystyle (v_i,{\gamma }_i)}$ and a proof ${\displaystyle (c_1,\dots ,c_n,Z(X))}$, party ${\displaystyle i}$ verifies the correctness of it as below:
  1. Checks that ${\displaystyle Z(X)}$ is a valid (up to) degree-${\displaystyle t}$ polynomial.
  2. Recomputes the challenge value ${\displaystyle d=\mathcal{H}(c_1,\dots ,c_n)}$, and verifies the commitment equation ${\displaystyle c_i=\mathcal{C}(v_i,Z(i)-d{v}_i,{\gamma }_i)}$.

If the verification fails, similar to Feldman’s and Pedersen’s schemes, the party raises a complaint. If too many complaints (more than ${\displaystyle t}$) are raised, the dealer is disqualified. In case of a complaint, the dealer can publicly reveal the disputed share to allow global verification. Honest parties can then collectively agree to either continue or disqualify the dealer.

This scheme supports the sharing of both low-entropy and high-entropy secrets. Moreover, since it relies solely on secure hash functions for commitments and on a (quantum) random oracle, it plausibly achieves security even against quantum adversaries. Additionally, by using only lightweight cryptographic primitives, the scheme is considerably more efficient in practice compared to traditional VSS constructions based on number-theoretic assumptions.

Benaloh's scheme

Once n shares are distributed to their holders, each holder should be able to verify that all shares are collectively t-consistent (i.e., any subset t of n shares will yield the same, correct, polynomial without exposing the secret).

In Shamir's secret sharing scheme the shares ${\displaystyle s_1,s_2,...,s_n}$ are t-consistent if and only if the interpolation of the points ${\displaystyle (1,s_1),(2,s_2),...,(n,s_n)}$ yields a polynomial degree at most d = t − 1.

Based on that observation, Benaloh's protocol can be shown to allow the share holders to perform the required validation while also verifying the dealer's authenticity and integrity.

A second observation is that given the degree of the sum of two polynomials F and G is less than or equal to t, either the degrees of both F and G are less than or equal to t, or both the degrees of F and G are greater than t. This claim is evident due to Polynomial function's Homomorphic property, examples:

case 1:

${\displaystyle f_1=3x}$, ${\displaystyle f_2=11x^6}$, ${\displaystyle t=6}$

case 2:

${\displaystyle f_1=18x^7}$, ${\displaystyle f_2=-18x^7}$, ${\displaystyle t=6}$

the case that we canceled:

${\displaystyle f_1=2x^2+3x^3}$, ${\displaystyle f_2=x+x^7}$, ${\displaystyle t=6}$

Interactive proof:
The following 5 steps verify the integrity of the dealer to the Share holders:

• Dealer chooses polynomial P, distributes shares (as per Shamir's secret sharing scheme).
• Dealer constructs a very large number (k) of random polynomials ${\displaystyle P_1,...,P_k}$ of degree t, and distributes shares.
• Share-holder chooses a random subset of m < k polynomials.
• Dealer reveals shares of the m chosen polynomials ${\displaystyle P_{i_1},...,P_{i_m}}$ and sums of remaining k − m sums ${\displaystyle P+\sum _{j=m+1}^k{P}_j}$ then shares the result as well.
• Each share-holder or verifier ascertains that all revealed polynomials are degree-t, and corresponds to its own known share.

The secret s remains safe and unexposed.

These 5 steps will be done in small number of iterations to achieve high probability result about the dealer integrity.

Diagnosis 1: Because the degree of polynomial ${\displaystyle P+\sum _{j=m+1}^k{P}_j}$ is less than or equal to t and because the Dealer reveals the other ${\displaystyle P_{i_1},...,P_{i_m}}$ polynomials (step 4), the degree of the polynomial P must be less than or equal to t (second observation case 1, with height probability when these steps are repeated in different iterations).

Diagnosis 2: One of the parameters for the problem was to avoid exposing the secret which we are attempting to verify. This property is kept through the use of Algebra homomorphism to perform validation. (A set of random polynomials of degree at most t together with a set of sums of P and other polynomials of degree at most t gives no useful information about P.)

Secret ballot elections

Verifiable secret sharing can be used to build end-to-end auditable voting systems.

Using the technique of verifiable secret sharing one can satisfy the election problem that will be described here.

In the election problem each voter can vote either 0 (to oppose) or 1 (for support), and the sum of all votes will determine election's result. For the election to execute, it is necessary to make sure that the following conditions are fulfilled:

• The voters' privacy should not be compromised.
• The election administrator must verify that no voter committed fraud.

If using verifiable secret sharing, n tellers will replace the single election administrator. Each voter will distribute one share of its secret vote to every one of the n tellers. This way the privacy of the voter is preserved and the first condition is satisfied.

Reconstruction of the election's result is easy, if there exist enough k < n tellers to discover polynomial P.

The interactive proof can be generalized slightly to allow verification of the vote shares. Each voter will prove (in the distribution of the secret share phase) to the tellers that his vote is legitimate using the five steps of the interactive proof.

Round-optimal and efficient verifiable secret sharing

The round complexity of a VSS protocol is defined as the number of communication rounds in its sharing phase; reconstruction can always be done in a single round. There is no 1-round VSS with t > 1, regardless of the number of players. The bounds on perfectly secure (not relying on a computational hardness assumption) and efficient (polynomial time) VSS protocols is given below.