Paper 2021/1342

Efficient Functional Commitments: How to Commit to Private Functions

Dan Boneh and Wilson Nguyen and Alex Ozdemir

Abstract

We construct efficient functional commitments for all bounded size arithmetic circuits. A (function hiding) functional commitment scheme allows a 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. Thus, functional commitments allow the operator of a secret process to prove that the process is being applied uniformly to everyone. Possible applications include bail decisions, credit scores, online ranking algorithms, and proprietary software-as-a-service. To build functional commitments, we introduce a new type of protocol: a proof of function relation (PFR) to show that a committed relation is a function. We show that combining a suitable preprocessing zk-SNARK 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. These constructions build on polynomial commitments (a special case of functional commitments), so our work shows that polynomial commitments are “complete” for functional commitments.

Note: Minor Typo Fixes