Compressed Sigma-protocol Theory

We review the pivotal protocol in the paper [AC20] Thomas Attema and Ronald Cramer. Compressed sigma-protocol theory and practical application to plug & play secure algorithmics. In CRYPTO (3), volume 12172 of Lecture Notes in Computer Science, pages 513–543. Springer, 2020. 

Reconciling Bulletproofs with -Protocol Theory: strengthening of -protocol theory, rather than replacement. The natural key is  linearization.

• First,the pivotal protocol repurposes BPs as a blackbox compression mechanism for standard -Protocols handling ZK proofs of general linear relations (on compactly committed secret vectors)
• Second, reducing the case of general nonlinear relations to blackbox applications of the pivot via a novel variation on arithmetic secret sharing based techniques for Σ-Protocols (Cramer et al., ICITS 2012).

[CDP 12]  linearization : https://eprint.iacr.org/2011/301.pdf

Outline: 

A. Pivotal Σ-Protocol  commitment with "arbitrary linear form openings" 

B. Compressing the Pivot 

C. Compactifying a Vector of Commitments 

D. Plug-and-Play Secure Algorithmics from Compressed Pivot

Definition (Pedersen Vector Commitment [Ped91]).

Let  be an Abelian group of prime order , then Pedersen vector commitments are defined by the following setup and commitment phase.

• Setup:  

• Commit: 

 and  for any  and  

To partially open a commitment to a linear form

means that the prover wishes to reveal  together with a proof of validity without revealing any additional information on x. Achieving this functionality amounts for the prover to send the opening  along with a ZKPoK for the relation

Protocol   -protocol  for relation   -protocol to prove correctness of a linear form evaluation.

At the heart of Bulletproofs is an interactive proof of knowledge between a Prover and Verifier showing that a Pedersen commitment to a vector of large length  satisfies a multivariate polynomial equation of degree 2, defined with an inner product. We refer to this PoK by BP, with logarithmic communication complexity for the following inner product relation,

to incorporate the linear form into the Pedersen vector commitment

where  and  for all .

where,  and  for a random challenge  sampled by the verifier.

Protocol Argument of Knowledge  for  Reduction from relation  to relation .

Protocol Compressed Proof of Knowledge  for  

For any even dimension  and vector  we define  as its left half and  as its right half. The same notation is used for vectors in  For a linear form  we define

where  are the vectors  appended with  zeros on the right and left, respectively.

The protocol is recursive and in each iteration the dimension of the witness is halved until its dimension equals 2.

The compressed  -protocol  for relation  is the composition of the previously mentioned protocols, i.e.,   is a SHVZK argument of knowledge for relation  with a logarithmic communication complexity.

Protocol Compressed  -protocol  for relation 

 for a compact commitment to a vector  and for a (public) linear form  we write for the interactive protocol that reveals  and nothing else to the verifier.

Protocol Protocol  for Opening a Linear Form Evaluated in a Committed Vector 

The communication costs of  are equal to the cost of the underlying interactive protocol  plus 1 field element from  to  (the output of  unless of course the output is known in advance. Similarly, we write  for the (amortized) interactive protocol that exclusively reveals  for  to the verifier.

A polynomial amortization trick allows us to do many nullity checks on the committed vector  without a substantial increase in complexity. Consider linear forms  and suppose the prover claims that  for  The verifier then samples  uniformly at random and asks the prover to open the linear form  i.e., prover and verifier run  The opening of equals the evaluation of some polynomial of degree at most  If this polynomial is non-zero, it has at most  zero's. Hence,  implies that  for all  with probability at least . When is exponential and  is polynomial in the security parameter this probability is exponentially close to 1. We write  for this protocol.

Protocol Amortized Protocol  for Many Nullity Checks at Once 

The communication costs are equal to the costs of a single nullity-check  plus one additional element from  to  (the challenge  ).

The work of [CDP12] considers homomorphic commitment schemes where the secret committed to is not a vector of large length, but a single element of  instead.

• Handling Multiplication gates:

The primary result is a  -protocol showing the correctness of commitments to  multiplication triples  with low amortized complexity for large  In other words, the protocol verifies the multiplicative relations and the costs per triple are relatively small. They use strongly-multiplicative packed-secret sharing.

Now we adapt this approach to the circuit satisfiability scenario, where we let  be an arbitrary arithmetic circuits with  multiplication gates. We use a simple fact about a circuit . Consider the computation graph induced by evaluation at input-vector  Write  for the resulting outputs of the multiplication gates. For each  write  for the resulting inputs to the  -th multiplication gate. Finally, write  for the resulting output of the circuit. Then, for each  there are affine forms  depending only on  such that, for all  it holds that  and  These forms are uniquely determined by the addition and scalar multiplication gates. Similarly, there is an affine function  such that, for all  it holds that  In other words, a given pair  can be completed to an accepting computation graph if and only if  for and  The vector  from the above multiplication-triples approach, is now adapted as follows. The prover includes the input vector  However, the  's and the  's are omitted from . Otherwise, the vector  is unchanged. In particular,

and  is a subvector of  Subsequently, the prover compactly commits to this adapted vector . By the handle discussed above, the prover needs to convince the verifier that  and that  for all  The  and  's are now taken as the evaluation at  of the affine functions  introduced above. Note that we may capture all these as affine functions evaluated at .

As for  checking that  is just a nullity check as provided by the pivot. As for (2), the polynomials  are still well-defined by the prover's compact commitment to y. Namely,i.e., the randomness underlying its selection, is still included in . As the  's thus defined are affine functions of  the prover is still (implicitly) committed to a polynomial  of degree  such that  and  and evaluation of  in a point  is still, by composition of appropriate maps, an affine evaluation at  as enabled by the pivot. since  is also still included in  a similar conclusion is drawn about the  's,  and evaluation of the latter. As no changes with respect to  were made in  we conclude that the required check can be performed in the same way as before.

• Proving Nonlinear Relations via Arithmetic Circuits

Circuit satisfiability scenario: a prover shows that it knows an input  for which the arithmetic circuit  evaluates to 0.

Protocol Circuit Satisfiability Argument  for Relation  The polynomials  and  are sampled uniformly at random such that their evaluations in  coincide with the left and, respectively, right inputs of the multiplication gates of  evaluated at .