Cryptology ePrint Archive: Report 2020/152

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

Thomas Attema and Ronald Cramer

Abstract: Sigma-Protocols provide a well-understood basis for secure algorithmics. Recently, Bulletproofs (Bootle et al., EUROCRYPT 2016, and BŁnz et al., S&P 2018) have been proposed as a drop-in replacement in case of zero-knowledge (ZK) for arithmetic circuits, achieving logarithmic communication instead of linear. Its pivot is an ingenious, logarithmic-size proof of knowledge BP for certain quadratic relations. However, reducing ZK for general relations to it forces a somewhat cumbersome ``reinvention'' of cryptographic protocol theory. We take a rather different viewpoint and reconcile Bulletproofs with Sigma-Protocol Theory such that (a) simpler circuit ZK is developed within established theory, while (b) achieving exactly the same logarithmic communication. The natural key here is linearization. First, we repurpose BPs as a blackbox compression mechanism for standard Sigma-Protocols handling ZK proofs of general linear relations (on compactly committed secret vectors); our pivot. Second, we reduce the case of general nonlinear relations to blackbox applications of our pivot via a novel variation on arithmetic secret sharing based techniques for Sigma-Protocols (Cramer et al., ICITS 2012). Orthogonally, we enhance versatility by enabling scenarios not previously addressed, e.g., when a secret input is dispersed across several commitments. Standard implementation platforms leading to logarithmic communication follow from a Discrete-Log assumption or a generalized Strong-RSA assumption. Also, under a Knowledge-of-Exponent Assumption (KEA) communication drops to constant, as in ZK-SNARKS. All in all, our theory should more generally be useful for modular (``plug & play'') design of practical cryptographic protocols; this is further evidenced by our separate work (2020) on proofs of partial knowledge.

Category / Keywords: cryptographic protocols / Sigma-protocols, Bulletproofs, Zero-Knowledge, Plug-and-Play, Secure Algorithmics, ZK-SNARKS, Verifiable Computation.

Original Publication (with minor differences): IACR-CRYPTO-2020

Date: received 11 Feb 2020, last revised 16 Jul 2020

Contact author: thomas attema at tno nl,ronald cramer@cwi nl

Available format(s): PDF | BibTeX Citation

Note: This is the full version of the same title work accepted for publication at CRYPTO 2020. Change log w.r.t. previous version- June 23, 2020: (a) modified the extractor analysis of Appendix A to account for the fact that our previous derivations are only meaningful for a portion of the full parameter space, and (b) for the full range of parameters we rely on prior results and, for this reason, refrain from giving concrete knowledge errors in several theorems.

Version: 20200716:113316 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]