View source for Mersenne's laws

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.
{{quotation|
    In verifiable secret sharing (VSS) the object is to resist malicious players, such as<br />
 (i) a dealer sending incorrect shares to some or all of the participants, and<br />
 (ii) participants submitting incorrect shares during the reconstruction protocol,cf. [CGMA85].<br />
 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 <math>i</math> can be verified publicly.
|Berry Schoenmakers. A Simple Publicly Verifiable Secret Sharing Scheme and its Application to Electronic Voting .}}

The method introduced here according to the paper by [http://eprint.iacr.org/2004/201.ps 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: 
#All system parameters are generated.
#Each participant must have a registered public key.

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

==Distribution==
1.Distribution of secret <math>s</math> shares is performed by the dealer <math>D</math>, which does the following:
* The dealer creates <math>s_{1},s_{2}...s_{n}</math> for each participant <math>P_{1},P_{2}...P_{n}</math> respectively.
* The dealer publishes the encrypted share <math>E_{i}(s_{i})</math> for each <math>P_{i}</math>.
* The dealer also publishes a string <math>\mathrm{proof}_{D}</math> to show that each <math>E_{i}</math> encrypts <math>s_{i}</math>
(note: <math>\mathrm{proof}_{D}</math> guarantees that the reconstruction protocol will result in the same <math>s</math>.

2. Verification of the shares:
* Anybody knowing the public keys for the encryption methods <math>E_{i}</math>, 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 <math>P_{i}</math> decrypts their share of the secret <math>s_{i}</math> using <math>E_{i}(s_{i})</math>.
(note: fault-tolerance can be allowed here: it's not required that all participants succeed in decrypting <math>E_{i}(s_{i})</math> as long as a qualified set of participants are successful to decrypt <math>s_{i}</math>).
* The participant release <math>s_{i}</math> plus a string <math>\mathrm{proof}_{P_{i}}</math> this shows the released share is correct.

2. Pooling the shares:
* Using the strings <math>\mathrm{proof}_{P_{i}}</math> to exclude the participants which are dishonest or failed to decrypt <math>E_{i}(s_{i})</math>.
* Reconstruction <math>s</math> can be done from the shares of any qualified set of participants.

==Chaums and Pedersen Scheme==
A proposed protocol proving: <math>\log_{_{g1}}h_{1} = \log_{_{g2}}h_{2}</math> :
#The prover chooses a random <math>r\in  \boldsymbol{\Zeta}_{q^*} </math>
#The verifier send a random challenge <math>c \in _{R}\boldsymbol{\Zeta}_{q} </math>
#The prover responds with <math>s = r - c x(\mathrm{mod}\,q)</math>
#The verifier checks <math>\alpha_1 = g_{1}^s h_{1}^c </math> and <math>\alpha_2 = g_{2}^s h_{2}^c </math>

Denote this protocol as: <math>\mathrm{dleq}(g_1, h_1,g_2,h_2)</math><br />
A generalization of <math>\mathrm{dleq}(g_1, h_1,g_2,h_2)</math> is denoted as: <math>\text{dleq}(X, Y, g_1, h_1,g_2,h_2)</math> where as: <math>X = g_{1}^{x_1}g_{2}^{x_2}</math> and <math>Y = h_{1}^{x_1}h_{2}^{x_2}</math>:
#The prover chooses a random <math> r_1,r_2 \in Z_{q}^*</math> and sends <math>t_1 = g_{1}^{r_1} g_{2}^{r_2}</math> and <math>t_2 = h_{1}^{r_1} h_{2}^{r_2}</math>
#The verifier send a random challenge <math>c \in _{R}\boldsymbol{\Zeta}_{q} </math>.
#The prover responds with <math>s_1 = r_1 - cx_1 (\mathrm{mod}\,q) </math> , <math>s_2 = r_2 - cx_2 (\mathrm{mod}\,q) </math>.
#The verifier checks <math>t_1 = X^c g_{1}^{s_1}g_{2}^{s_2}</math> and <math>t_2 = Y^c h_{1}^{s_1}h_{2}^{s_2}</math>

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

==See also==
* [[Verifiable secret sharing]]

==References==
* Markus Stadler, [http://www.ubilab.org/publications/print_versions/pdf/sta96.pdf Publicly Verifiable Secret Sharing]
* Berry Schoenmakers, [http://www.win.tue.nl/~berry/papers/crypto99.pdf A Simple Publicly Verifiable Secret Sharing Scheme and its Application to Electronic Voting], Advances in Cryptology—CRYPTO, 1999, pp.&nbsp;148–164

[[Category:Applications of cryptography]]