International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Vector Commitments over Rings and Compressed $\Sigma$-Protocols

Authors:
Thomas Attema , CWI, Amsterdam; Leiden University, Leiden; and TNO, The Hague, The Netherlands
Ignacio Cascudo , IMDEA Software Institute, Madrid, Spain
Ronald Cramer , CWI, Amsterdam, The Netherlands; and Leiden University, Leiden, The Netherlands
Ivan Damgård , Aarhus University, Aarhus, Denmark
Daniel Escudero , J.P. Morgan AI Research, New York, U.S.A.
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: TCC 2022
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 machine-friendly 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 \emph{any} positive integer $m$, a result that was not known in the literature before. Second, we generalize 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 direct application for example to verifiable computation on homomorphically encrypted data.
BibTeX
@inproceedings{tcc-2022-32578,
  title={Vector Commitments over Rings and Compressed $\Sigma$-Protocols},
  publisher={Springer-Verlag},
  author={Thomas Attema and Ignacio Cascudo and Ronald Cramer and Ivan Damgård and Daniel Escudero},
  year=2022
}