system parameter. The group G must be chosen such that computing discrete logarithms is hard in this group. (Typically, one takes an order-q subgroup of (Z/pZ)×, where q is a prime dividing .) The dealer then computes (and keeps secret) a random polynomial P of degree t with coefficients in Zq, such that , where s is the secret. Each of the n share holders will receive a value P(1), ..., P(n) modulo q. Any share holders can recover the secret s by using polynomial interpolation modulo q, but any set of at most t share holders cannot. (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: c0 = gs, c1 = ga1, ... ct = gat. Once these are given, any party can verify their share. For instance, to verify that modulo q, party i can check that . This scheme is, at best, secure against computationally bounded adversaries, namely the intractability of computing discrete logarithms. Pedersen proposed later a scheme where no information about the secret is revealed even with a dealer with unlimited computing power. 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 are t-consistent if and only if the interpolation of the points yields a polynomial degree at most . 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