Paper 2022/1510

Witness Encryption for Succinct Functional Commitments and Applications

Abstract

Witness encryption (WE), introduced by Garg, Gentry, Sahai, and Waters (STOC 2013) allows one to encrypt a message to a statement $\mathsf{x}$ for some NP language $\mathcal{L}$, such that any user holding a witness for $\mathsf{x} \in \mathcal{L}$ can decrypt the ciphertext. The extreme power of this primitive comes at the cost of its elusiveness: a practical construction from established cryptographic assumptions is currently out of reach. In this work, we investigate a new notion of encryption that has a flavor of WE and that we can build only based on bilinear pairings, for interesting classes of computation. We do this by connecting witness encryption to functional commitments (FC). FCs are an advanced notion of commitments that allows fine-grained openings, that is non-interactive proofs to show that a commitment $\mathsf{cm}$ opens to $v$ such that $y=G(v)$, with the crucial feature that both commitments and openings are succinct. Our new WE notion, witness encryption for (succinct) functional commitment (WE-FC), allows one to encrypt a message with respect to a triple $(\mathsf{cm}, G, y)$, and decryption is unlocked using an FC opening that $\mathsf{cm}$ opens to $v$ such that $y=G(v)$. This mechanism is similar to the notion of witness encryption for NIZK of commitments [Benhamouda and Lin, TCC'20], with the crucial difference that ours supports commitments and decryption time whose size and complexity do not depend on the length of the committed data $v$. Our main contributions are therefore the formal definition of WE-FC, a generic methodology to compile an FC in bilinear groups into an associated WE-FC scheme (semantically secure in the generic group model), and a new FC construction for NC1 circuits that yields a WE-FC for the same class of functions. Similarly to [Benhamouda and Lin, TCC'20], we show how to apply WE-FC to construct multiparty reusable non-interactive secure computation (mrNISC) protocols. Crucially, the efficiency profile of WE-FC yields mrNISC protocols whose offline stage has shorter communication (only a succinct commitment from each party). As an additional contribution, we discuss further applications of WE-FC and show how to extend this primitive to better suit these settings.