Paper 2024/1294

Laconic Pre-Constrained Encryption

Abstract

The recent work of Ananth et al. (ITCS 2022) initiated the study of pre-constrained encryption (PCE) which achieves meaningful security even against the system authority, without assuming any trusted setup. They provided constructions for special cases such as pre-constrained Attribute Based Encryption (PC-ABE) for point functions and pre-constrained Identity Based Encryption (PC-IBE) for general functions from the Learning with Errors (LWE) assumption. For the most general notion of PCE for circuits, they provided a construction from indistinguishability obfuscation (iO) and moreover, proved a lower bound showing that the reliance on iO was inherent. In all their constructions, the size of the public key scales linearly with the size of the constraint input to the setup algorithm.\smallskip In this work we initiate the study of laconic pre-constrained encryption, where the public key is sublinear in the size as well as number of constraints input to the setup algorithm. We make the following contributions: 1. We construct laconic pre-constrained ABE for point functions and laconic pre-constrained IBE for general functions from LWE which achieves succinct public keys, thus improving upon the work of Ananth et al. 2. For general constraints, we sidestep the lower bound by Ananth et al. by defining a weaker static notion of pre-constrained encryption (sPCE), which nevertheless suffices for all known applications. We show that laconic sPCE is impossible to achieve in the strongest malicious model of security against authority and provide the first construction of semi-malicious laconic sPCE for general constraints from LWE in the random oracle model. 3. For general constraints, to achieve malicious security without iO, we provide constructions of non-laconic sPCE from a variety of assumptions including DDH, LWE, QR and DCR. Our LWE based construction satisfies unconditional security against malicious authorities. 4. As an application of our sPCE, we provide the first construction of pre-constrained group signatures supporting general constraints, achieving unconditional anonymity and unlinkability against malicious authorities from the LWE assumption. The only other construction by Bartusek et al. supports the restricted set/database membership constraint, and achieves computational security from the DDH assumption. Along the way, we define and construct the notion of pre-constrained Input Obfuscation which may be of independent interest.

Note: We changed the title, reorganized several notions, and give new constructions.