Welcome to the resource topic for 2011/301
Title:
On the Amortized Complexity of Zero Knowledge Protocols for Multiplicative Relations
Authors: Ronald Cramer, Ivan Damgard, Valerio Pastro
Abstract:We present a protocol that allows to prove in zero-knowledge that committed values x_i, y_i, z_i, i=1,\dots,l satisfy x_iy_i=z_i, where the values are taken from a finite field K, or are integers. The amortized communication complexity per instance proven is O(\kappa + l) for an error probability of 2^{-l}, where \kappa is the size of a commitment. When the committed values are from a field of small constant size, this improves complexity of previous solutions by a factor of l. When the values are integers, we improve on security: whereas previous solutions with similar efficiency require the strong RSA assumption, we only need the assumption required by the commitment scheme itself, namely factoring. We generalize this to a protocol that verifies l instances of an algebraic circuit D over K with v inputs, in the following sense: given committed values x_{i,j} and z_i, with i=1,\dots,l and j=1,\dots,v, the prover shows that D(x_{i,1},\dots,x_{i,v})= z_i for i=1,\dots,l. For circuits with small multiplicative depth, this approach is better than using our first protocol: in fact, the amortized cost may be asymptotically smaller than the number of multiplications in D.
ePrint: https://eprint.iacr.org/2011/301
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .