Paper 2024/1294

Don't Trust Setup! New Directions in Pre-Constrained Cryptography

Abstract

The recent works of Ananth et al. (ITCS 2022) and Bartusek et al. (Eurocrypt 2023) initiated the study of pre-constrained cryptography which achieves meaningful security even against the system authority. In this work we significantly expand this area by defining several new primitives and providing constructions from simple, standard assumptions as follows. - Pre-Constrained Encryption. We define a weaker notion of pre-constrained encryption (PCE), as compared to the work of Ananth et al. which nevertheless suffices for all known applications. We then provide constructions for general constraints, satisfying malicious security from a variety of assumptions including DDH, LWE, QR and DCR. Our LWE based construction satisfies unconditional security against malicious authorities. In contrast, the construction by Ananth et al. supporting general constraints must rely (inherently) on strong assumptions like indistinguishability obfuscation. - Pre-Constrained Static Functional Encryption and Input Obfuscation. We provide a new definition for pre-constrained functional encryption in the so-called static setting (PCSFE) where the functions to be embedded in secret keys are specified during the setup phase. We provide constructions for PCSFE supporting general constraints, with security against malicious authorities. As in the case of PCE, our first construction can be instantiated from a variety of assumptions including DDH, LWE, QR and DCR. Our second, LWE based construction satisfies unconditional security against malicious authorities. We also study succinctness in PCSFE, where the public key is sublinear in the number of function keys. We provide the first construction from LWE in the random oracle model. We additionally provide a heuristic construction in the standard model using lattices together with groups. - Pre-Constrained Input Obfuscation. We define and provide the first construction of pre-constrained input obfuscation from the same assumptions as those used to instantiate PCSFE. - Pre-Constrained Group Signatures. For pre-constrained group signatures (PCGS), we provide the first construction supporting general constraints, achieving unconditional security 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 (and is therefore quantum insecure).

Note: We changed the title and rewrote the introduction section.