Paper 2024/1294

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

Abstract

The 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, without assuming any trusted setup. In this work we significantly expand this area by defining new primitives and providing constructions from simple, standard assumptions as follows. 1. 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 construct sPCE for general constraints with security against malicious authorities from a variety of assumptions, including DDH, LWE, QR, and DCR. In particular, our LWE-based construction achieves unconditional security against malicious authorities. 2. We also study succinctness in sPCE (laconic sPCE), where the public key is sublinear in the number of function keys. 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. 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 and reorganized several notions.