Paper 2020/152

Compressed $\Sigma$-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics

Thomas Attema and Ronald Cramer

Abstract

Sigma-Protocols form a well-understood basis for plug-and-play secure algorithmics. Bulletproofs (Bünz et al., SP 2018) have been introduced as a ``drop-in'' for Sigma-Protocols in some important applications; notably, zero-knowledge (ZK) for arithmetic circuits and range proofs, each with logarithmic communication instead of linear. At the heart of Bulletproofs is an ingenious, logarithmic-size proof of knowledge (PoK), denoted BP, showing that a compact Pedersen commitment to a long vector satisfies a quadratic equation (``an inner product relation'').However, applications, like those mentioned, meet with technical difficulties: (1) BPs are not ZK and (2) protocol theory requires ``reinvention'' with the quadratic constraint proved as its ``pivot''. This leads to practical, yet complex ZK protocols where applying natural plug-and-play intuition appears hard. Our approach is radically different. We reconcile Bulletproofs with the theory of Sigma-Protocols such that (a) applications can follow established protocol theory, thereby dispensing with the need for ``reinventing'' it, while (b) enjoying exactly the same communication reduction. We do this by giving a precise perspective on BPs as a significant strengthening of the power of Sigma-protocols. We believe this novel perspective is rather useful for practical design. Our program combines two essential components.First, we isolate a natural Sigma-Protocol as alternative pivot that directly yields ZK proofs for arbitrary linear statements (i.e., about the compactly committed secret vector), while deploying suitable BPs to compress communication. We also develop some convenient utility enhancements of the pivot to handle different, natural proof scenarios. Second, to enable ZK proofs of nonlinear statements, we integrate the pivot as a black-box with a novel variation on -- hitherto largely overlooked -- arithmetic secret sharing based techniques for Sigma-Protocols (Cramer et al., ICITS 2012); this linearizes ``all nonlinear statements'' using the fact that arbitrary linear ones can be proved. This yields simple circuit ZK with logarithmic communication. Similarly for range proofs, which are now trivial. Our results are based on either of three assumptions: the Discrete Logarithm assumption, an assumption derived from the Strong-RSA assumption, or a Knowledge-of-Exponent Assumption (KEA). In the latter case - thus, at the cost of relying on an unfalsifiable assumption - the communication complexity is constant instead of logarithmic.

Note: Change log w.r.t. Version 1 - February 11, 2020: (a) minor editorial changes throughout, (b) simplification of the compression mechanism including the observation that it achieves unconditional soundness with an improved knowledge error, see Section 4, (c) added full details for sketch of case 1 compactification protocol, see Section 5.3, (d) described two approaches for achieving unconditional soundness, see Section 4.4, (e) added instantiation of our program from KEA, see Section 9.