Paper 2021/1342 Original: eprint.iacr.org/2021/1342 ↗

Efficient Functional Commitments: How to Commit to a Private Function

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.