This document summarizes Pedersen's non-interactive verifiable secret sharing scheme. It describes how the scheme works by having a dealer distribute polynomial shares to participants that allow them to reconstruct the secret. Each participant can verify their share is consistent by checking commitments published by the dealer. The scheme removes trust in the dealer by having participants act as dealers and combining multiple runs of the protocol to share the sum of secrets.
This document summarizes Pedersen's non-interactive verifiable secret sharing scheme. It describes how the scheme works by having a dealer distribute polynomial shares to participants that allow them to reconstruct the secret. Each participant can verify their share is consistent by checking commitments published by the dealer. The scheme removes trust in the dealer by having participants act as dealers and combining multiple runs of the protocol to share the sum of secrets.
This document summarizes Pedersen's non-interactive verifiable secret sharing scheme. It describes how the scheme works by having a dealer distribute polynomial shares to participants that allow them to reconstruct the secret. Each participant can verify their share is consistent by checking commitments published by the dealer. The scheme removes trust in the dealer by having participants act as dealers and combining multiple runs of the protocol to share the sum of secrets.
This document summarizes Pedersen's non-interactive verifiable secret sharing scheme. It describes how the scheme works by having a dealer distribute polynomial shares to participants that allow them to reconstruct the secret. Each participant can verify their share is consistent by checking commitments published by the dealer. The scheme removes trust in the dealer by having participants act as dealers and combining multiple runs of the protocol to share the sum of secrets.
Copyright:
Attribution Non-Commercial (BY-NC)
Available Formats
Download as PDF, TXT or read online from Scribd
Download as pdf or txt
You are on page 1/ 21
Verifiable Secret Sharing
CMSC 652: Cryptology, Spring 2009 Presented by: Vivek Relan
Outline
Motivation Applications of VSS Types of VSS VSS scheme by T Pedersen (1991) Commitment scheme Conclusion
Motivation
Shamir's secret sharing scheme assumed that dealer is reliable But, in reality dealer may misbehave and can deal inconsistent shares to the participants Thus, k participants will unable to reconstruct a secret Verifiable Secret Sharing (VSS) scheme addresses this issue
Verifiable Secret Scheme
Shares are verifiable without revealing shares and secret Convinces shareholders that their shares are kconsistent
Each shareholder assures that every subset of k out of n defines the same secret
Detects malicious dealer or malicious shareholder
Applications
End-to-end auditable voting systems Threshold software key escrow Secure storage
Types of VSS
Interactive VSS
Interaction between dealer and shareholder is needed for verification e.g. Goldwasser-Micali Scheme (1985), Benaloh VSS scheme (1986)
Non-interactive VSS
No interaction between dealer and shareholder is needed for verification e.g. T Pedersen's VSS scheme (1991)
T Pedersen's VSS Scheme
Non-interactive and information-theoretic secure verifiable secret sharing Published in
Crypto'91 Springer'92
Citation count 661
Preliminaries
Discrete logarithm problem
Let g, h Gq and x Z (set of integer) gx % N = h Given g, x and N, it is easy to find h But, it is hard to find x from g, h and N
Let p and q be prime and p = 2q+1. Z/pZ forms a group. We will restrict our attention to quadratic residue in this group.
Math overview
G = (g, h)
A = (a, b)
C = (c, d)
A + C = (a+c, b+d) n*A = (n*a, n*b) GA = (ga * hb) Let's consider a polynomial f(x) and g(x) f(x) = a0 + a1x + a2x2 + a3x3 + ... + ak-1xk-1 g(x) = b0 + b1x + b2x2 + b3x3 + ... + bk-1xk-1
Given commit(A), one has no idea about A It is hard to find A' such that commit(A) = commit(A') Based on discrete logarithm problem
Commit is binding
VSS: Sharing Protocol
Dealer chooses F = (f, g) randomly, where f, g are (k-1)-degree polynomials and f(0) = a0 and F(0) = (a0, b0) f(x) = a0 + a1x + a2x2 + a3x3 + ... + ak-1xk-1 g(x) = b0 + b1x + b2x2 + b3x3 + ... + bk-1xk-1
a0 is secret a1, a2, ..., ak-1 and b0, b1, ..., bk-1 are selected randomly in a finite field
VSS: Sharing Protocol (cont)
Dealer computes Ai = commit(Fi) i=0,1, ..., k-1 and broadcasts all these commitment Ai to n participants Dealer computes Xi = F(i) and sends this value Xi to participant i, for each 1<= i <= n. Moreover, also sends signD(Xi) to person i
VSS: Verification phase
Each person Pi verifies the following
LHS equals RHS by (+, *) homomorphism property of commitment scheme
VSS: Verification phase (cont)
If verification fails for participant Pi,
Broadcast accusation (Xi , signD(Xi)) to all other participants
There are two cases in front of other participants
Dealer D is faulty Participant Pi is faulty
VSS: Verification phase (cont)
Dealer D proves that he is not faulty by broadcasting Xi to all participants Each participants can verify his share Participant Pi aborts if he sees at least k such accusation or his check fails
Dishonest dealer
Lot of trust is placed in a dealer Instead of choosing prime numbers to construct a quadratic residue subgroup, dealer might pick his phone number. Dealer can find the discrete log before distributing the shares and can manipulate the shares. How do we totally remove trust in the dealer ?
Linear combination of shared secrets
Let two instances of VSS scheme are running with same participants
By combining above these two procedures
Secret E0 + F0 = (x+y) Each person receives E(i) + F(i) = Xi + Yi
Linear combination of shared secrets (cont)
Due to (+, *) homomorphism property,
Combining two VSS procedure yields
Linear combination of shared secrets (cont)
Assume each participant acts as dealer and picks F[i], 1<= i <=n and principle of adding functions to have a secret that's sum of secrets shown above is applied n times:
If any one of the participant is honest and unbiased, the above scheme will be uniform and unbiased
Conclusion
Non-interactive verifiable (k, n)-threshold scheme protects the secret to be distributed unconditionally for any value of k (1<= k <= n) Correctness of shares depends on the assumption that dealer can not find discrete logarithm before the distribution of shares Linear combination of shared secrets is easy which removes the implicit trust placed in a dealer
