Sigma Protocol - Revision history

Srikar: /* Definition */

2020-06-25T18:04:46Z

Definition

Srikar at 17:50, 25 June 2020

2020-06-25T17:50:17Z

Srikar: /* Sigma protocols */

2020-06-25T17:49:12Z

Sigma protocols

Srikar: 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}..."

2020-06-25T17:48:31Z

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}..."

New page

===Sigma protocols===

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>.

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.

: <math>PK\{(x): y_1= g_1^{x} \land y_2={(g_2^a)}^{x} g_2^b \},</math>

states that the prover knows an ''x'' that fulfills the relation above.

@@ Line 7: / Line 7: @@
 states that the prover knows an ''x'' that fulfills the relation above.
 === Historical Context ===
 === Resources ===
 Great resources to learn about Sigma Protocols in depth:

@@ 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''&nbsp;=&nbsp;1 and ''b''&nbsp;=&nbsp;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 6: / Line 7: @@
 states that the prover knows an ''x'' that fulfills the relation above.
 Great resources to learn about Sigma Protocols in depth:

← Older revision		Revision as of 17:49, 25 June 2020
Line 1:		Line 1:
−	~~===Sigma protocols===~~
−
	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: