Proposal: Σ-protocols(2)-Basic Σ Protocols in Prime-Order Groups

Proposal: Σ-protocols(1)

A basic -protocol for the relation:

for a group homomorphism is given by the following algorithms:

1. The prover's first algorithm consists of the following steps:

(a) It chooses random elements .

(b) It then computes .

(c) The algorithm sets and .

(d) It finally outputs .

2. The prover's second algorithm proceeds as follows:

(a) It checks that and aborts if this is not the case.

(b) It then parses and .

(c) It computes its response as for .

3. The verifier's algorithm proceeds as follows:

(a) It parses , and

(b) It checks that for and for , and outputs 0 if this is not the case.

(c) It checks whether , and outputs true if this is the case; otherwise, outputs false.

4. The required simulator for a basic -protocol works as follows:

(a) It parses .

(b) It chooses .

(c) It sets

(d) Finally, the algorithm outputs the simulated transcript by setting

Proving linear relations among witnesses

While the above protocol allows one to efficiently prove knowledge of a pre-image under a homomorphism, many protocols found in the literature require one to prove relations among witnesses. Specifically, they require to prove relations like the following:

where the matrix and vector specify the system of linear equations.

Proving such a relation can easily by achieved by modifying the above protocol as follows:

• In Item 1a, the prover draws the randomnesses such that they satisfy the system of equations, i.e., such that .

• In Item 3b, the verifier additionally checks that and outputs false if this is not the case.

• In Item , the simulator draws the responses such that they satisfy the verification equations, i.e., such that .

1Examples

Example 1 (DLOG)

Let be a group over an elliptic curve with prime order . Proving knowledge of the discrete logarithm of a point in base means proving knowledge of such that .

Using the above notation, we have . The protocol flow is then as depicted in Protocol

For a given challenge , the simulator chooses , and sets . It then outputs the simulated transcript .

Example 2 (DLEQ)

Let be a group over an elliptic curve with prime order . Proving equality of the known discrete logarithm of in base and in base means proving knowledge of such that and , and

Using the above notation, we have . The linear system of equations is given by . The protocol flow is then as depicted in Protocol 3 .

For a given challenge , the simulator chooses such that , and sets and . It then outputs the simulated transcript .

Example 3 (DLEQ; alternative)

The same proof goal as in the previous example can also be achieved by considering a slightly different homomorphism, which directly encodes the linear relation, that is . The protocol flow is then as depicted in Protocol

For a given challenge , the simulator chooses , and sets and . It then outputs the simulated tran

• Remark 1 . The two protocols illustrated prove the same statement, but achieve this via different approaches. The first protocol uses the more general framework of liner relations among witnesses introduced above. Alternatively, as shown in the second protocol, the linear relation can also be realized by directly incorporating the linear relation into the proof goal, thereby achieving a slightly shorter proof size (as the prover's last message consists of one element of less). However, when proving inhomogeneous linear relations, incorporating the relation into the homomorphism also requires some additional computations in the target group, which in certain cases might compensate the advantage of a smaller proof size.

Example 4 (REP)

Let be a group over an elliptic curve of prime order . Proving knowledge of a valid opening of a Pedersen commitment means proving knowledge of such that .

Using the above notation, we have .

The protocol flow is then as depicted in Protocol 5 .

For a given challenge , the simulator chooses , and sets It then outputs the simulated transcript .

Example 5 (DH).

Let be a group over an elliptic curve with prime order . Proving knowledge of the exponents of a valid Diffie-Hellman triple means proving knowledge of such that , , and . Yet, the mapping is not a homomorphism, and consequently the basic protocol presented before cannot be deployed directly. However, the required multiplicative relation can be proven by observing that the proof goal is equivalent to , and , leading the homomorphism .

The protocol flow is then as depicted in Protocol 6 . 

For a given challenge , the simulator chooses , and sets , and . It then outputs the simulated transcript .

As shown in this example, and in contrast to linear relations, multiplicative relations among witnesses typically require a reformulation of the proof goal in order to be compatible with the generic protocol presented above. We refer, e.g., to Krenn [Kre12] for generic techniques.

Stephan Krenn. Bringing Zero-Knolwedge Proofs of Knowledge to Practice. PhD thesis, University of Fribourg, Switzerland, 2012.