Cryptology ePrint Archive: Report 2019/326

Sublinear Pairing-based Arguments with Updatable CRS and Weaker Assumptions

Alonso González and Carla Rŕfols

Abstract: The need for structured and trusted common parameters is often cited as one of the major drawbacks of pairing-based SNARKs. Although multiparty computation techniques can be used to address this, the resulting parameters are circuit dependent and this costly process must be repeated for every circuit. Recent proposals to switch to a weaker updatable model for parameter generation are not yet sufficiently efficient. We propose a new model for updatability which generates the common reference string in two phases, each of them updatable: in the first phase, parameters are generated for a set of universal quadratic constraints and in the second phase specific circuit dependent parameters which impose some affine constraints can be derived from them non-interactively. We propose a concrete construction based on (but more efficient than) Pinocchio. An additional contribution of the paper is to obtain a very efficient argument for verifiable computation using the same design principles which is based on weaker assumptions. The communication is approximately 4d group elements and verifying a proof requires computing around 4d pairings and O(n+d) exponentiations, where n is the input size and d the circuit depth. While the argument for the quadratic constraints is based on standard falsifiable assumptions, the argument for the linear constraints is based on a very ad-hoc assumption about certain properties of arguments of membership in linear spaces.

Category / Keywords: cryptographic protocols / zero knowledge

Date: received 25 Mar 2019, last revised 29 Mar 2019

Contact author: carla rafols at upf edu

Available format(s): PDF | BibTeX Citation

Version: 20190329:131602 (All versions of this report)

Short URL: ia.cr/2019/326


[ Cryptology ePrint archive ]