Functional Commitments for All Functions, with Transparent Setup and from SIS

Leo de Castro; Chris Peikert

Paper 2022/1368

Functional Commitments for All Functions, with Transparent Setup and from SIS

Leo de Castro, Massachusetts Institute of Technology

Chris Peikert

, University of Michigan–Ann Arbor

Abstract

A *functional commitment* scheme enables a user to concisely commit to a function from a specified family, then later concisely and verifiably reveal values of the function at desired inputs. Useful special cases, which have seen applications across cryptography, include vector commitments and polynomial commitments. To date, functional commitments have been constructed (under falsifiable assumptions) only for functions that are essentially *linear*, with one recent exception that works for arbitrarily complex functions. However, that scheme operates in a strong and non-standard model, requiring an online, trusted authority to generate special keys for any opened function inputs. In this work, we give the first functional commitment scheme for nonlinear functions---indeed, for *all functions* of any bounded complexity---under a standard setup and a falsifiable assumption. Specifically, the setup is ``transparent,'' requiring only public randomness (and not any trusted entity), and the assumption is the hardness of the standard Short Integer Solution (SIS) lattice problem. Our construction also has other attractive features, including: *stateless updates* via generic composability; excellent *asymptotic efficiency* for the verifier, and also for the committer in important special cases like vector and polynomial commitments, via preprocessing; and *post-quantum security*, since it is based on SIS.

Note: Updated to discuss several concurrent related works and add zero-knowledge variant.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published by the IACR in EUROCRYPT 2023
Keywords: functional commitments vector commitments polynomial commitments fully homomorphic computation
Contact author(s): ldec @ mit edu
cpeikert @ umich edu
History: 2023-02-28: revised; 2022-10-11: received; See all versions
Short URL: https://ia.cr/2022/1368
License: CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2022/1368,
      author = {Leo de Castro and Chris Peikert},
      title = {Functional Commitments for All Functions, with Transparent Setup and from SIS},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1368},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1368}},
      url = {https://eprint.iacr.org/2022/1368}
}