Welcome to the resource topic for 2025/944
Title:
Succinct Witness Encryption for Batch Languages and Applications
Authors: Lalita Devadas, Abhishek Jain, Brent Waters, David J. Wu
Abstract:Witness encryption allows one to encrypt a message to an \mathsf{NP} relation \mathcal{R} and a statement x. The corresponding decryption key is any valid \mathsf{NP} witness w. In a succinct witness encryption scheme, we require that the size of the ciphertext be sublinear in the size of the \mathsf{NP} relation. Currently, all realizations of succinct witness encryption for \mathsf{NP} rely on strong assumptions such as pseudorandom obfuscation, extractable witness encryption, or differing-inputs obfuscation. Notably, none of these notions are known from standard assumptions.
In this work, we consider a relaxation of succinct witness encryption for \mathsf{NP} to the setting of batch \mathsf{NP}. In this setting, one encrypts to an \mathsf{NP} relation \mathcal{R} together with K statements x_1, \ldots, x_K. In the basic version, one can decrypt if they have a witness w_1, \ldots, w_K for all K statements. The succinctness requirement is that the size of the ciphertext should be sublinear in the number of instances K, but is allowed to grow with the size of the \mathsf{NP} relation (i.e., the size of a single instance). More generally, we can also impose a (monotone) policy P \colon \{0,1\}^K \to \{0,1\} over the K instances. In this case, decryption is possible only if there exists w_1, \ldots, w_K such that P(\mathcal{R}(x_1, w_1), \ldots, \mathcal{R}(x_K, w_K)) = 1.
In this work, we initiate a systematic study of succinct witness encryption for batch languages. We start with two simple constructions that support CNF and DNF policies based on plain witness encryption in conjunction with a somewhere statistically sound batch argument for \mathsf{NP} or a function-binding hash function. Then, using indistinguishability obfuscation, we show how to support policies that can be computed by read-once bounded-space Turing machines. The latter construction is in fact a unique witness map for monotone-policy batch \mathsf{NP}, and as such, also gives a SNARG for monotone-policy batch \mathsf{NP} where the size of the common reference string is sublinear in the number of instances.
Finally, we demonstrate some immediate applications of succinct witness encryption for batch languages. We construct new succinct computational secret sharing schemes for CNFs, DNFs, and weighted threshold policies. We also show how to build distributed monotone-policy encryption, a notion that generalizes recent trustless primitives like distributed broadcast encryption and threshold encryption with silent setup.
ePrint: https://eprint.iacr.org/2025/944
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .