In cryptography, a secret sharing scheme is verifiable if auxiliary information is included that allows players to verify their shares as consistent.
(In standard secret sharing, the dealer is assumed to be honest.
)[1] The concept of verifiable secret sharing (VSS) was first introduced in 1985 by Benny Chor, Shafi Goldwasser, Silvio Micali and Baruch Awerbuch.
[2] In a VSS protocol a distinguished player who wants to share the secret is referred to as the dealer.
Each message sent or broadcast by a player is determined by its input, its random input and messages received from other players in previous rounds.
Reconstruction: In this phase each player provides its entire view from the sharing phase and a reconstruction function is applied and is taken as the protocol's output.
An alternative definition given by Oded Goldreich defines VSS as a secure multi-party protocol for computing the randomized functionality corresponding to some (non-verifiable) secret sharing scheme.
Verifiable secret sharing is important for secure multiparty computation.
Multiparty computation is typically accomplished by making secret shares of the inputs, and manipulating the shares to compute some function.
To handle "active" adversaries (that is, adversaries that corrupt nodes and then make them deviate from the protocol), the secret sharing scheme needs to be verifiable to prevent the deviating nodes from throwing off the protocol.
(Note, in particular, that the published value gs leaks information about the dealer's secret s.) First, a cyclic group G of prime order q, along with a generator g of G, is chosen publicly as a system parameter.
(Typically, one takes an order-q subgroup of (Z/pZ)×, where q is a prime dividing p − 1.)
(In fact, at this point any set of at most t share holders has no information about s.) So far, this is exactly Shamir's scheme.
To make these shares verifiable, the dealer distributes commitments to the coefficients of P modulo q.
If P(x) = s + a1x + ... + atxt, then the commitments that must be given are: Once these are given, any party can verify their share.
Pedersen proposed later a scheme[4] where no information about the secret is revealed even with a dealer with unlimited computing power.
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: case 2: the case that we canceled: Interactive proof: The following 5 steps verify the integrity of the dealer to the Share holders: 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.
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.
(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.) 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.
For the election to execute, it is necessary to make sure that the following conditions are fulfilled: 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.
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.
The bounds on perfectly secure (not relying on a computational hardness assumption) and efficient (polynomial time) VSS protocols is given below.