Verifiable secret sharing

From Wikipedia, the free encyclopedia

You have new messages (last change).

In cryptography, a secret sharing scheme is verifiable if auxiliary information is included that allows players to verify their shares as consistent. The concept of verifiable secret sharing (VSS) was first introduced in 1985 by B. Chor, S. Goldwasser, S. Micali and B. Awerbuch.

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 in order to compute some function. In order 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 in order to prevent the deviating nodes from throwing off the protocol.

[edit] Feldman's scheme

A commonly used example of a simple VSS scheme is the protocol by Paul Feldman, which is based on Shamir's secret sharing scheme combined with any homomorphic encryption scheme. For example, one can base it on an encryption system derived from the discrete logarithm problem to obtain (roughly) the following (t, n) -threshold scheme:

First, a cyclic group G of order m, along with a generator g of G, is chosen publicly as a system parameter. (Note that usually some conditions will be imposed on the choice of group, in particular, the discrete logarithm problem should be hard to solve in that group). Typically, one takes (a subgroup of) (Zq)×.

The dealer then computes (and keeps secret) a random polynomial P of degree t with coefficients in Zm, such that P(0)=s, where s is the secret. Each of the n share holders will receive a value P(1), ... , P(n) modulo m. Any t+1 share holders can recover the secret s by polynomial interpolation modulo m, but any set of no more than t share holders know nothing about the secret.

So far, everything proceeded almost identical to the regular Shamir protocol (in particular, reconstruction works identical). In order to make these shares verifiable, the dealer distributes commitments to the coefficients of P. 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 v = P(i) modulo p, we can check that

g^v = c_0 c_1^i c_2^{i^2} \cdots c_t^{i^t} = \prod_{j=0}^t c_j^{i^j} = \prod_{j=0}^t g^{a_j i^j} = g^{\sum_{j=0}^t a_j i^j} = g^{p(i)}.

[edit] See also

[edit] References

  • B. Chor, S. Goldwasser, S. Micali and B. Awerbuch, Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults, FOCS85, pp. 383-395.
  • P. Feldman, A practical scheme for non-interactive verifiable secret sharing. IEEE Symposium on Foundations of Computer Science, pages 427--437. IEEE, 1987.
  • T. Rabin and M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority. In Proceedings of the Twenty-First Annual ACM Symposium on theory of Computing (Seattle, Washington, United States, May 14 - 17, 1989). [1]
 This cryptography-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../v/e/r/Verifiable_secret_sharing.html"