Paper 2022/181
Vector Commitments over Rings and Compressed $\Sigma$Protocols
Thomas Attema, Ignacio Cascudo, Ronald Cramer, Ivan Bjerre Damgård, and Daniel Escudero
Abstract
Compressed $\Sigma$Protocol Theory (CRYPTO 2020) presents an ``alternative'' to Bulletproofs that achieves the same communication complexity while adhering more elegantly to existing $\Sigma$protocol theory, which enables their techniques to be directly applicable to other widely used settings in the context of ``plug \& play'' algorithmics. Unfortunately, their techniques are restricted to arithmetic circuits over \emph{prime} fields, which rules out the possibility of using more machinefriendly moduli such as powers of $2$, which have proven to improve efficiency in applications. In this work we show that such techniques can be generalized to the case of arithmetic circuits modulo \emph{any} number. This enables the use of powers of $2$, which can prove to be beneficial for efficiency, but it also facilitates the use of other moduli that might prove useful in different applications. In order to achieve this, we first present an instantiation of the main building block of the theory of compressed $\Sigma$protocols, namely compact vector commitments. Our construction, which may be of independent interest, is homomorphic modulo any positive integer $m$, a result that was not known in the literature before. Second, we generalize the Compressed $\Sigma$Protocol Theory from finite fields to $\mathbb{Z}_m$. The main challenge here is ensuring that there are large enough challenge sets as to fulfill the necessary soundness requirements, which is achieved by considering certain ring extensions. Our techniques have application as publicly verifiable zero knowledge proofs of correct computation on homomorphically encrypted data, where for a more flexible parameter instantiation it is useful that the ciphertext space is allowed to be a modular or Galois ring rather than a field: concretely, our protocols can be plugged as a commitandproof argument into a recent result on efficient verifiable computation schemes on encrypted data with contexthiding (PKC 21) which exploited this advantage.
Metadata
 Available format(s)
 Publication info
 Preprint. Minor revision.
 Contact author(s)

thomas attema @ tno nl
ignacio cascudo @ imdea org
Ronald Cramer @ cwi nl
ivan @ cs au dk
daniel escudero @ protonmail com  History
 20220224: revised
 20220220: received
 See all versions
 Short URL
 https://ia.cr/2022/181
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/181, author = {Thomas Attema and Ignacio Cascudo and Ronald Cramer and Ivan Bjerre Damgård and Daniel Escudero}, title = {Vector Commitments over Rings and Compressed $\Sigma$Protocols}, howpublished = {Cryptology ePrint Archive, Paper 2022/181}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/181}}, url = {https://eprint.iacr.org/2022/181} }