Paper 2011/301

On the Amortized Complexity of Zero Knowledge Protocols for Multiplicative Relations

Ronald Cramer, Ivan Damgard, and Valerio Pastro


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$.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
cramer @ cwi nl
ivan @ cs au dk
vpastro @ cs au dk
2012-10-05: revised
2011-06-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ronald Cramer and Ivan Damgard and Valerio Pastro},
      title = {On the Amortized Complexity of Zero Knowledge Protocols for Multiplicative Relations},
      howpublished = {Cryptology ePrint Archive, Paper 2011/301},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.