Paper 2021/307
A Compressed $\Sigma$Protocol Theory for Lattices
Thomas Attema, Ronald Cramer, and Lisa Kohl
Abstract
We show a latticebased solution for commitandprove transparent circuit zeroknowledge (ZK) with polylogcommunication, the first not depending on PCPs. We start from compressed $\Sigma$protocol theory (CRYPTO 2020), which is built around basic $\Sigma$protocols for opening an arbitrary linear form on a long secret vector that is compactly committed to. These protocols are first compressed using a recursive ``foldingtechnique'' adapted from Bulletproofs, at the expense of logarithmic rounds. Proving in ZK that the secret vector satisfies a given constraint  captured by a circuit  is then by (blackbox) reduction to the linear case, via arithmetic secretsharing techniques adapted from MPC. Commitandprove is also facilitated, i.e., when commitment(s) to the secret vector are created ahead of any circuitZK proof. On several platforms (incl.\ DL) this leads to logarithmic communication. Noninteractive versions follow from FiatShamir. This abstract modular theory strongly suggests that it should somehow be supported by a latticeplatform as well. However, when going through the motions and trying to establish low communication (on an SISplatform), a certain significant lack in current understanding of multiround protocols is exposed. Namely, as opposed to the DLcase, the basic $\Sigma$protocol in question typically has polysmall challenge space. Taking into account the compressionstep  which yields nonconstant rounds  and the necessity for parallelization to reduce error, there is no known tight result that the compound protocol admits an efficient knowledge extractor. We resolve the state of affairs here by a combination of two novel results which are fully general and of independent interest. The first gives a tight analysis of efficient knowledge extraction in case of nonconstant rounds combined with polysmall challenge space, whereas the second shows that parallel repetition indeed forces rapid decrease of knowledge error. Moreover, in our present context, arithmetic secret sharing is not defined over a large finite field but over a quotient of a number ring and this forces our careful adaptation of how the linearization techniques are deployed. We develop our protocols in an abstract framework that is conceptually simple and can be flexibly instantiated. In particular, the framework applies to arbitrary rings and norms.
Note: Change log w.r.t. Version 2  March 13, 2021: Minor (local) correction of the proof of Lemma 5. More precisely, adjusted the conditioning in the expected value of the run time random variable.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint. MINOR revision.
 Keywords
 Zero KnowledgeCircuit ZKLatticesSigmaProtocolsCompressionShort Integer Solution Problem
 Contact author(s)

thomas attema @ tno nl
cramer @ cwi nl
lisa kohl @ cwi nl  History
 20211014: last of 3 revisions
 20210309: received
 See all versions
 Short URL
 https://ia.cr/2021/307
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/307, author = {Thomas Attema and Ronald Cramer and Lisa Kohl}, title = {A Compressed $\Sigma$Protocol Theory for Lattices}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/307}, year = {2021}, url = {https://eprint.iacr.org/2021/307} }