Sigma Protocol

Definition

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.

Resources

Great resources to learn about Sigma Protocols in depth: