Paper 2018/705

Subvector Commitments with Application to Succinct Arguments

Russell W. F. Lai and Giulio Malavolta

Abstract

We put forward the notion of subvector commitments (SVC): An SVC allows one to open a committed vector at a set of positions, where the opening size is independent of length of the committed vector and the number of positions to be opened. We propose two constructions under variants of the root assumption and the CDH assumption, respectively. We further generalize SVC to a notion called linear map commitments (LMC), which allows one to open a committed vector to its images under linear maps with a single short message, and propose a construction over pairing groups. Equipped with these newly developed tools, we revisit the ``CS proofs'' paradigm [Micali, FOCS 1994] which turns any arguments with public-coin verifiers into non-interactive arguments using the Fiat-Shamir transform in the random oracle model. We propose a compiler that turns any (linear, resp.) PCP into a non-interactive argument, using exclusively SVCs (LMCs, resp.). For an approximate $80$ bits of soundness, we highlight the following new implications: - There exists a succinct non-interactive argument of knowledge (SNARK) with public-coin setup with proofs of size 5360 bits, under the adaptive root assumption over class groups of imaginary quadratic orders against adversaries with runtime $2^{128}$. At the time of writing, this is the shortest SNARK with public-coin setup. - There exists a non-interactive argument with private-coin setup, where proofs consist of 2 group elements and 3 field elements, in the generic bilinear group model.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in CRYPTO 2019
Keywords
zero knowledgeRSA
Contact author(s)
russell lai @ cs fau de
giulio malavolta @ hotmail it
History
2020-03-24: last of 5 revisions
2018-08-01: received
See all versions
Short URL
https://ia.cr/2018/705
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/705,
      author = {Russell W. F.  Lai and Giulio Malavolta},
      title = {Subvector Commitments with Application to Succinct Arguments},
      howpublished = {Cryptology ePrint Archive, Paper 2018/705},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/705}},
      url = {https://eprint.iacr.org/2018/705}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.