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 introduce and construct a new notion of encryption that has a strong flavor of WE and that, crucially, we can build from well-studied assumptions (based on bilinear pairings) for interesting classes of computation. Our new notion, witness encryption for (succinct) functional commitment, takes inspiration from a prior weakening of witness encryption introduced by Benhamouda and Lin (TCC 2020). In a nutshell, theirs is a WE where: the encryption statement consists of a (non compressible) commitment $\mathsf{cm}$, a function $G$ and a value $y$; the decryption witness consists of a (non succinct) NIZK proof about the fact that $\mathsf{cm}$ opens to $v$ such that $y=G(v)$. Benhamouda and Lin showed how to apply this primitive to obtain MPC with non-interactive and reusability properties—dubbed $\mathsf{mrNISC}$—replacing the requirement of WE in existing round-collapsing techniques. Our new WE-like notion is motivated by supporting both commitments of a fixed size and fixed decryption complexity, independent of the size of the value $v$—in contrast to the work by Benhamouda and Lin where this complexity is linear. As a byproduct, our efficiency requirement substantially improves the offline stage of $\mathsf{mrNISC}$ protocols. From a technical standpoint, our work shows how to solve additional challenges arising from relying on computationally binding commitments and computational soundness (of functional commitments), as opposed to statistical binding and unconditional soundness (of NIZKs), used in Benhamouda and Lin's work. In order to tackle them, we need not only to modify their basic blueprint, but also to model and instantiate different types of projective hash functions as building blocks. Our techniques are of independent interest and may highlight new avenues to design practical variants of witness encryption. As an additional contribution, we show that our new WE-flavored primitive and its efficiency properties are versatile: we discuss its further applications and show how to extend this primitive to better suit these settings.