Subvector Commitments with Application to Succinct Arguments
Lai RWF, Malavolta G (2019)
Publication Type: Conference contribution
Publication year: 2019
Journal
Publisher: Springer Verlag
Book Volume: 11692 LNCS
Pages Range: 530-560
Conference Proceedings Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Event location: Santa Barbara, CA
ISBN: 9783030269470
DOI: 10.1007/978-3-030-26948-7_19
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: 1.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.2.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.
Authors with CRIS profile
Involved external institutions
How to cite
APA:
Lai, R.W.F., & Malavolta, G. (2019). Subvector Commitments with Application to Succinct Arguments. In Daniele Micciancio, Alexandra Boldyreva (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 530-560). Santa Barbara, CA, US: Springer Verlag.
MLA:
Lai, Russell W. F., and Giulio Malavolta. "Subvector Commitments with Application to Succinct Arguments." Proceedings of the 39th Annual International Cryptology Conference, CRYPTO 2019, Santa Barbara, CA Ed. Daniele Micciancio, Alexandra Boldyreva, Springer Verlag, 2019. 530-560.
BibTeX: Download