Difference between revisions of "Sigma Protocol"
(Created page with "===Sigma protocols=== Protocols which have the above three-move structure (commitment, challenge and response) are called ''sigma protocols''{{Citation needed|date=June 2017}...") |
|||
| Line 1: | Line 1: | ||
| − | |||
| − | |||
Protocols which have the above three-move structure (commitment, challenge and response) are called ''sigma protocols''{{Citation needed|date=June 2017}}. The Greek letter <math>\Sigma</math> visualizes the flow of the protocol. Sigma protocols exist for proving various statements, such as those pertaining to discrete logarithms. Using these proofs, the prover can not only prove the knowledge of the discrete logarithm, but also that the discrete logarithm is of a specific form. For instance, it is possible to prove that two logarithms of <math>y_1</math> and <math>y_2</math> with respect to bases <math>g_1</math> and <math>g_2</math> are equal or fulfill some other [[linear]] [[Relation (mathematics)|relation]]. For ''a'' and ''b'' elements of <math>Z_q</math>, we say that the prover proves knowledge of <math>x_1</math> and <math>x_2</math> such that <math>y_1= g_1^{x_1} \land y_2=g_2^{x_2}</math> and <math>x_2 = a x_1 + b</math>. Equality corresponds to the special case where ''a'' = 1 and ''b'' = 0. As <math>x_2</math> can be [[trivial (mathematics)|trivially]] computed from <math>x_1</math> this is equivalent to proving knowledge of an ''x'' such that <math>y_1= g_1^{x} \land y_2={(g_2^a)}^{x} g_2^b</math>. | Protocols which have the above three-move structure (commitment, challenge and response) are called ''sigma protocols''{{Citation needed|date=June 2017}}. The Greek letter <math>\Sigma</math> visualizes the flow of the protocol. Sigma protocols exist for proving various statements, such as those pertaining to discrete logarithms. Using these proofs, the prover can not only prove the knowledge of the discrete logarithm, but also that the discrete logarithm is of a specific form. For instance, it is possible to prove that two logarithms of <math>y_1</math> and <math>y_2</math> with respect to bases <math>g_1</math> and <math>g_2</math> are equal or fulfill some other [[linear]] [[Relation (mathematics)|relation]]. For ''a'' and ''b'' elements of <math>Z_q</math>, we say that the prover proves knowledge of <math>x_1</math> and <math>x_2</math> such that <math>y_1= g_1^{x_1} \land y_2=g_2^{x_2}</math> and <math>x_2 = a x_1 + b</math>. Equality corresponds to the special case where ''a'' = 1 and ''b'' = 0. As <math>x_2</math> can be [[trivial (mathematics)|trivially]] computed from <math>x_1</math> this is equivalent to proving knowledge of an ''x'' such that <math>y_1= g_1^{x} \land y_2={(g_2^a)}^{x} g_2^b</math>. | ||
| Line 8: | Line 6: | ||
states that the prover knows an ''x'' that fulfills the relation above. | states that the prover knows an ''x'' that fulfills the relation above. | ||
| + | |||
| + | Great resources to learn about Sigma Protocols in depth: | ||
Revision as of 17:49, 25 June 2020
Protocols which have the above three-move structure (commitment, challenge and response) are called sigma protocolsTemplate:Citation needed. The Greek letter \(\Sigma\) visualizes the flow of the protocol. Sigma protocols exist for proving various statements, such as those pertaining to discrete logarithms. Using these proofs, the prover can not only prove the knowledge of the discrete logarithm, but also that the discrete logarithm is of a specific form. For instance, it is possible to prove that two logarithms of \(y_1\) and \(y_2\) with respect to bases \(g_1\) and \(g_2\) are equal or fulfill some other linear relation. For a and b elements of \(Z_q\), we say that the prover proves knowledge of \(x_1\) and \(x_2\) such that \(y_1= g_1^{x_1} \land y_2=g_2^{x_2}\) and \(x_2 = a x_1 + b\). Equality corresponds to the special case where a = 1 and b = 0. As \(x_2\) can be trivially computed from \(x_1\) this is equivalent to proving knowledge of an x such that \(y_1= g_1^{x} \land y_2={(g_2^a)}^{x} g_2^b\).
This is the intuition behind the following notation<ref>https://www.researchgate.net/publication/243300730_Efficient_Group_Signature_Schemes_for_Large_Groups</ref>, which is commonly used to express what exactly is proven by a proof of knowledge.
\[PK\{(x): y_1= g_1^{x} \land y_2={(g_2^a)}^{x} g_2^b \},\]
states that the prover knows an x that fulfills the relation above.
Great resources to learn about Sigma Protocols in depth:
