Paper 2021/932

Succinct Functional Commitment for a Large Class of Arithmetic Circuits

Helger Lipmaa and Kateryna Pavlyk

Abstract

A succinct functional commitment (SFC) scheme for a circuit class $\mathbf{CC}$ enables, for any circuit $\mathcal{C} \in \mathbf{CC}$, the committer to first succinctly commit to a vector $\vec{\alpha}$, and later succinctly open the commitment to $\mathcal{C} (\vec{\alpha}, \vec{\beta})$, where the verifier chooses $\vec{\beta}$ at the time of opening. Unfortunately, SFC commitment schemes are known only for severely limited function classes like the class of inner products. By making non-black-box use of SNARK-construction techniques, we propose an SFC scheme for the large class of semi-sparse polynomials. The new SFC scheme can be used to, say, efficiently (1) implement sparse polynomials, and (2) aggregate various interesting SFC (e.g., vector commitment and polynomial commitment) schemes. The new scheme is evaluation-binding under a new instantiation of the computational uber-assumption. We provide a thorough analysis of the new assumption.

Note: Full version of our Asiacrypt 2020 paper. It differs by having appendices, more standard AGM security proofs of certain theorems, and general readability improvements.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
aggregated functional commitmentDéjà Qfunctional commitmentSNARKuber-assumptionvector commitment
Contact author(s)
helger lipmaa @ gmail com
History
2021-07-09: received
Short URL
https://ia.cr/2021/932
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/932,
      author = {Helger Lipmaa and Kateryna Pavlyk},
      title = {Succinct Functional Commitment for a Large Class of Arithmetic Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2021/932},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/932}},
      url = {https://eprint.iacr.org/2021/932}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.