Publicly verifiable secret sharing

In cryptography, a secret sharing scheme is publicly verifiable (PVSS) if it is a verifiable secret sharing scheme and if any party (not just the participants of the protocol) can verify the validity of the shares distributed by the dealer. Template:Blockquote

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

Initialization

The PVSS scheme dictates an initialization process in which:

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

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

Distribution

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

• The dealer creates $s_1,s_2...s_n$ for each participant $P_1,P_2...P_n$ respectively.
• The dealer publishes the encrypted share $E_i(s_i)$ for each $P_i$.
• The dealer also publishes a string ${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{f}}_D$ to show that each $E_i$ encrypts $s_i$

(note: ${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{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.

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: it's not required that all participants succeed in decrypting $E_i(s_i)$ as long as a qualified set of participants are successful to decrypt $s_i$).

• The participant release $s_i$ plus a string ${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{f}}_{P_i}$ this shows the released share is correct.

2. Pooling the shares:

• Using the strings ${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{f}}_{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.

Chaum-Pedersen Protocol

A proposed protocol proving: ${\log }_{{}_{g1}}{h}_1={\log }_{{}_{g2}}{h}_2$ :

1. The prover chooses a random $r\in {\mathrm{Z}}_{q^{*}}$
2. The verifier sends a random challenge $c{\in }_R{\mathrm{Z}}_q$
3. The prover responds with $s=r-cx(\mathrm{m}\mathrm{o}\mathrm{d}q)$
4. The verifier checks ${\alpha }_1=g_1^s{h}_1^c$ and ${\alpha }_2=g_2^s{h}_2^c$

Denote this protocol as: $\mathrm{d}\mathrm{l}\mathrm{e}\mathrm{q}(g_1,h_1,g_2,h_2)$
A generalization of $\mathrm{d}\mathrm{l}\mathrm{e}\mathrm{q}(g_1,h_1,g_2,h_2)$ is denoted as: $\text{dleq}(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}$:

1. 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}$
2. The verifier sends a random challenge $c{\in }_R{\mathrm{Z}}_q$.
3. The prover responds with $s_1=r_1-c{x}_1(\mathrm{m}\mathrm{o}\mathrm{d}q)$ , $s_2=r_2-c{x}_2(\mathrm{m}\mathrm{o}\mathrm{d}q)$.
4. 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}$

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

See also

• Verifiable secret sharing

References

• Markus Stadler, Publicly Verifiable Secret Sharing
• Berry Schoenmakers, A Simple Publicly Verifiable Secret Sharing Scheme and its Application to Electronic Voting, Advances in Cryptology – CRYPTO, 1999, pp. 148–164