Paper 2021/1342

Efficient Functional Commitments: How to Commit to a Private Function

Dan Boneh, Wilson Nguyen, and Alex Ozdemir

Abstract

We construct efficient (function hiding) functional commitments for arithmetic circuits of polynomial size. A (function hiding) functional commitment scheme enables a \textit{committer} to commit to a secret function $f$ and later prove that $y = f(x)$ for public $x$ and $y$ without revealing any other information about $f$. As such, functional commitments allow the operator of a secret process to prove that the process is being applied uniformly to everyone. For example, one can commit to the secret function that computes credit scores and then prove that it is applied uniformly to all. To build a functional commitment scheme, we introduce a new primitive called a proof of function relation (PFR) to show that a committed relation is a function. We show that combining a suitable preprocessing zk-SNARK (or more precisely, an Algebraic Holographic Proof) with a PFR yields a secure functional commitment scheme. We then construct efficient PFRs for two popular preprocessing zk-SNARKs, and obtain two functional commitment schemes for arithmetic circuits. Along the way we develop new techniques for proving interesting properties of committed polynomials, which may be of independent interest.

Note: CRYPTO'22 Submission

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
zero knowledgecommitments
Contact author(s)
wdnguyen @ cs stanford edu
dabo @ cs stanford edu
aozdemir @ cs stanford edu
History
2022-02-28: last of 3 revisions
2021-10-07: received
See all versions
Short URL
https://ia.cr/2021/1342
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1342,
      author = {Dan Boneh and Wilson Nguyen and Alex Ozdemir},
      title = {Efficient Functional Commitments: How to Commit to a Private Function},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1342},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1342}},
      url = {https://eprint.iacr.org/2021/1342}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.