Mersenne's laws

2014-01-11T21:22:44Z

190.19.86.67: Added a little more information on Marin Mersenne.

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 
(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 <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> 
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. 148–164

[[Category:Applications of cryptography]]

Fundamental increment lemma

2013-11-01T16:37:02Z

190.19.175.174: /* Differentiability in higher dimensions */ The error funciton Phi takes values in R not in R^{n}

This honeycomb is one of [[Uniform_polypeton#Regular_and_uniform_honeycombs|12 unique uniform honeycombs]]<ref>[http://mathworld.wolfram.com/Necklace.html], [http://oeis.org/A000029 A000029] 13-1 cases, skipping one with zero marks</ref> constructed by the <math>{\tilde{A}}_5</math> [[Coxeter group]]. The extended symmetry of the hexagonal diagram of the <math>{\tilde{A}}_5</math> Coxeter group allows for [[isomorphism]]s that map diagram nodes (mirrors) on to each other. So the various 12 honeycombs represent higher symmetries based on the ring arrangement symmetry in the diagrams:

{| class=wikitable
![[:File:Regular hexagon symmetries.png|Hexagon symmetry]]
![[Coxeter notation|Extended symmetry]]
!Extended diagram
!Extended order
!Diagrams
|- align=center
!a1
![3[6]]
|{{CDD|node|split1|nodes|3ab|nodes|split2|node}}
|×1
|{{CDD|node_1|split1|nodes_10lur|3ab|nodes|split2|node_1}}
|- align=center
!d2
!<[3[6]]>
|{{CDD|node_c1|split1|nodeab_c2|3ab|nodeab_c3|split2|node_c4}}
|×2
|{{CDD|node_1|split1|nodes|3ab|nodes|split2|node}}[[5-simplex honeycomb|1]], {{CDD|node|split1|nodes_11|3ab|nodes|split2|node}}, {{CDD|node_1|split1|nodes_11|3ab|nodes|split2|node}}, {{CDD|node_1|split1|nodes_11|3ab|nodes|split2|node_1}}, {{CDD|node_1|split1|nodes_11|3ab|nodes_11|split2|node}}
|- align=center
!p2
!<nowiki>[[</nowiki>3[6]]]
|{{CDD|node_c3|split1|nodeab_c1-2|3ab|nodeab_c1-2|split2|node_c4}}
|×2
|{{CDD|node|split1|nodes_10lur|3ab|nodes_10lru|split2|node}}[[Truncated 5-simplex honeycomb|2]], {{CDD|node_1|split1|nodes_10lur|3ab|nodes_10lru|split2|node_1}}
|- align=center
!i4
![2[3[6]]]
|{{CDD|node_c3|split1|nodeab_c1-2|3ab|nodeab_c1-2|split2|node_c3}}
|×4
|{{CDD|node_1|split1|nodes|3ab|nodes|split2|node_1}}, {{CDD|node|split1|nodes_11|3ab|nodes_11|split2|node}}
|- align=center
!d6
![3[3[6]]]
|{{CDD|node_c1|split1|nodeab_c2|3ab|nodeab_c1|split2|node_c2}}
|×6
|{{CDD|node_1|split1|nodes|3ab|nodes_11|split2|node}}
|- align=center
!r12
![6[3[6]]]
|{{CDD|node_c1|split1|nodeab_c1|3ab|nodeab_c1|split2|node_c1}}
|×12
|{{CDD|node_1|split1|nodes_11|3ab|nodes_11|split2|node_1}}[[Omnitruncated 5-simplex honeycomb|3]]
|}<noinclude>

==References==
{{reflist}}

[[Category:Encyclopedic content templates]]
</noinclude>

formulasearchengine - User contributions [en]

Mersenne's laws

Fundamental increment lemma