Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / zero knowledge, commitments

Date: received 5 Oct 2021, last revised 11 Oct 2021

Contact author: wdnguyen at cs stanford edu, dabo at cs stanford edu, aozdemir at cs stanford edu

Available format(s): PDF | BibTeX Citation

Note: Minor Typo Fixes

Version: 20211011:233215 (All versions of this report)

Short URL: ia.cr/2021/1342


[ Cryptology ePrint archive ]