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, while deploying suitable BPs to compress communication. We also develop convenient utility enhancements of the pivot. Second, to enable ZK proofs of nonlinear statements, we integrate the pivot as a blackbox with a novel variation on -- hitherto largely overlooked -- arithmetic secret sharing based techniques for Sigma-Protocols (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 two assumptions, the Discrete Logarithm assumption, or an assumption derived from the Strong-RSA assumption.