Publicly Verifiable Secret Sharing

From Wikipedia, the free encyclopedia

In cryptography, a secret sharing scheme is publicly verifiable (PVSS) if it is a verifiable secret sharing scheme and if any party involved can verify the validity of the shares distributed by the dealer.

In verifiable secret sharing (VSS) the object is to resist malicious players, such as
(i) a dealer sending incorrect shares to some or all of the participants, and
(ii) participants submitting incorrect shares during the reconstruction protocol,cf. [CGMA85].
In publicly verifiable secret sharing (PVSS), as introduced by Stadler [Sta96], it is an explicit goal that not just the participants can verify their own shares, but that anybody can verify that the participants received correct shares. Hence, it is explicitly required that $i$ can be verified publicly.

– Berry Schoenmakers. A Simple Publicly Veriﬁable Secret Sharing Scheme and its Application to Electronic Voting .

The method introduced here according to the paper by: Chunming Tang and Dingyi Pei and Zhuo Liu and Yong He is non-interactive and maintains this property through out the protocol.

1 Initialization
2 Distribution
3 Reconstruction
4 Chaums and Pedersen Scheme
5 See also
6 References

[edit] Initialization

The PVSS scheme dictates an initialization process in which:

All system parameters are generated.
Each participant must have a registered public key.

Excluding the initialization process, the PVSS consists of two phases:

[edit] Distribution

1.Distribution of secret $s$ shares is preformed by the dealer $D$ , which does the following:

The dealer creates $s 1, s 2 ... s n$ for each $P 1, P 2 ... P n$ respectively.
The dealer publishes the encrypted share $E i (s i)$ for each participant $P i$ .
The dealer also publishes a string $P R O O F D$ to show that each $E i$ encrypts $s i$

(note: $P R O O F D$ guarantees that the reconstruction protocol will result in the same $s$ .

2. Verification of the shares:

Anybody knowing the public keys for the encryption methods $E i$ , can verify the shares.
If one or more verifications fails the dealer fails and the protocol is aborted.

[edit] Reconstruction

1. Decryption of the shares:

The Participants $P i$ decrypts their share of the secret $s i$ using $E i (s i)$ .

(note: fault-tolerance can be allowed here: its not required that all participants succeed in decrypting $E i (s i)$ as long long as a qualified set of participant are successful to decrypt $s i$ ).

The participant release $s i$ plus a string $PROOF_{P_{i}}$ this shows the released share is correct.

2. Pooling the shares:

Using the strings $PROOF_{P_{i}}$ to exclude the participants which are dishonest or failed to decrypt $E i (s i)$ .
Reconstruction $s$ can be done from the shares of any qualified set of participants.

[edit] Chaums and Pedersen Scheme

A proposed protocol proving: $log_{_{g1}}h_{1} = log_{_{g2}}h_{2}$ :

The prover chooses a random $r\in \boldsymbol{\Zeta}_{q^*}$
The verifier send a random challenge $c \in _{R}\boldsymbol{\Zeta}_{q}$
The prover responds with $s = r - c x (m o d q)$
The verifier checks $\alpha_1 = g_{1}^s h_{1}^c$ and $\alpha_2 = g_{2}^s h_{2}^c$

Denote this protocol as: $D L E Q (g 1, h 1, g 2, h 2)$
A generalization of $D L E Q (g 1, h 1, g 2, h 2)$ is denoted as: $D L E Q (X, Y, g 1, h 1, g 2, h 2)$ where as: $X = g_{1}^{x_1}g_{2}^{x_2}$ and $Y = h_{1}^{x_1}h_{2}^{x_2}$ :

The prover chooses a random $r_1,r_2 \in Z_{q}^*$ and sends $t_1 = g_{1}^{r_1} g_{2}^{r_2}$ and $t_2 = h_{1}^{r_1} h_{2}^{r_2}$
The verifier send a random challenge $c \in _{R}\boldsymbol{\Zeta}_{q}$ .
The prover responds with $s 1 = r 1 - c x 1 (m o d q)$ , $s 2 = r 2 - c x 2 (m o d q)$ .
The verifier checks $t_1 = X^c g_{1}^{s_1}g_{2}^{s_2}$ and $t_2 = Y^c h_{1}^{s_1}h_{2}^{s_2}$

Chaums and Pedersen method is an interactive method and needs some modification to be used in non-interactive way: Replacing the randomly chosen $c$ by a 'secure hash' function with $m$ as input value.