International Association
for Cryptologic Research

Witness Encryption (WE) is a powerful cryptographic primitive, enabling applications that would otherwise appear infeasible. While general-purpose WE requires strong cryptographic assumptions, and is highly inefficient, recent works have demonstrated that it is possible to design special-purpose WE schemes for targeted applications that can be built from weaker assumptions and can also be concretely efficient. Despite the plethora of constructions in the literature that (implicitly) use witness encryption schemes, there has been no systematic study of special purpose witness encryption schemes. In this work we make progress towards this goal by designing a modular and extensible framework, which allows us to better understand existing schemes and also enables us to construct new witness encryption schemes. The framework is designed around simple but powerful building blocks that we refer to as "gadgets". Gadgets can be thought of as witness encryption schemes for small targeted relations (induced by linearly verifiable arguments) but they can be composed with each other to build larger, more expressive relations that are useful in applications. To highlight the power of our framework we methodically recover past results, improve upon them and even provide new feasibility results. The first application of our framework is a Registered Attribute-Based Encryption Scheme [Hohenberger et al. (Eurocrypt 23)] with linear sized common reference string (CRS). Numerous Registered Attribute-Based Encryption (R-ABE) constructions have since emerged though a black-box R-ABE construction with a linear--in the number of users--CRS has been a persistent open problem, with the state-of-the-art concretely being $\approx N^{1.58}$ (Garg et al. [GLWW, Crypto 24]). Empowered by our Witness Encryption framework we provide the first construction of black-box R-ABE with linear-sized CRS. Our construction is based on a novel realization of encryption for DNF formulas that leverages encryption for set membership. Our second application is a feasibility result for Registered Threshold Encryption. This is an analogue of the recently introduced Silent Threshold Encryption (Garg et al. [GKPW, Crypto 24]) placed in the Registered Setting. We formalize Registered Threshold Encryption and provide an efficient construction, with constant-sized encryption key and ciphertexts, that makes use of our WE framework.

We revisit the alternating moduli paradigm for constructing symmetric key primitives with a focus on constructing highly efficient protocols to evaluate them using secure multi-party computation (MPC). The alternating moduli paradigm of Boneh et al. (TCC 2018) enables the construction of various symmetric key primitives with the common characteristic that the inputs are multiplied by two linear maps over different moduli, first over F_2 and then over F_3. The first contribution focuses on efficient two-party evaluation of alternating moduli PRFs, effectively building an oblivious pseudorandom function. We present a generalization of the PRF proposed by Boneh et al. (TCC 18) along with methods to lower the communication and computation. We then provide several variants of our protocols, with different computation and communication tradeoffs, for evaluating the PRF. Most are in the OT/VOLE hybrid model while one is based on specialized garbling. Our most efficient protocol effectively is about 3x faster and requires 1.3x lesser communication. Our next contribution is the efficient evaluation of the OWF f(x) = B *_3 (A *_2 x) proposed by Dinur et al. (CRYPTO 21) where A \in F^{m x n}_2, B \in F^{t x m}_3 and *_p is multiplication mod p. This surprisingly simple OWF can be evaluated within MPC by secret sharing [x] over F_2, locally computing [v] = A *_2 [x], performing a modulus switching protocol to F_3 shares, followed by locally computing the output shares [y] = B *_3 [v]. We design a bespoke MPC-in-the-Head (MPCitH) signature scheme that evaluates the OWF, achieving state of art performance. The resulting signature has a size ranging from 4.0-5.5 KB, achieving between 2-3x reduction compared to Dinur et al. To the best of our knowledge, this is only 5% larger than the smallest signature based on symmetric key primitives, including the latest NIST PQC competition submissions. We additionally show that our core techniques can be extended to build very small post-quantum ring signatures for small-medium sized rings that are competitive with state-of-the-art lattice based schemes. Our techniques are in fact more generally applicable to set membership in MPCitH.

We build a concretely efficient threshold encryption scheme where the joint public key of a set of parties is computed as a \emph{deterministic} function of their locally computed public keys, enabling a \emph{silent} setup phase. By eliminating interaction from the setup phase, our scheme immediately enjoys several highly desirable features such as asynchronous setup, multiverse support, and dynamic threshold. Prior to our work, the only known constructions of threshold encryption with silent setup relied on heavy cryptographic machinery such as indistinguishability Obfuscation or witness encryption for all of $\mathsf{NP}$. Our core technical innovation lies in building a special purpose witness encryption scheme for the statement ``at least $t$ parties have signed a given message''. Our construction relies on pairings and is proved secure in the Generic Group Model. Notably, our construction, restricted to the special case of threshold $\thres=1$, gives an alternative construction of the (flexible) distributed broadcast encryption from pairings, which has been the central focus of several recent works. We implement and evaluate our scheme to demonstrate its concrete efficiency. Both encryption and partial decryption are constant time, taking $<7\,$ms and $<1\,$ms, respectively. For a committee of $1024$ parties, the aggregation of partial decryptions takes $<200\,$ms, when all parties provide partial decryptions. The size of each ciphertext is $\approx 8\times$ larger than an ElGamal ciphertext.

Incoming regulation on AI such as the EU AI act, requires impact assessment and risk management to ensure fairness, accountability, and provide transparency for “high-risk” AI systems. This seems to require that companies provide unfettered access to a third party auditor who will provide a “seal of approval” before an AI system can be deployed. This often creates a tension between companies trying to protect trade secrets and auditors who need “white box” access to the data and models. In this talk, we examine how cryptography can, not only help resolve this tension, but additionally provide stronger transparency guarantees to the end user. The talk will consist of two parts: 1) An overview of the AI Policy landscape tailored to a cryptographers. The goal of which is to "distill" policy demands into research questions that cryptographers can tackle. 2) Next we will present our construction for "zero-knowledge proofs of training" and discuss challenges and lessons that were learned along the way. The technical paper "Experiment with Zero-Knowledge Proofs of Training" was accepted at CCS 2023.

As end-to-end encrypted messaging services become widely adopted, law enforcement agencies have increasingly expressed concern that such services interfere with their ability to maintain public safety. Indeed, there is a direct tension between preserving user privacy and enabling content moderation on these platforms. Recent research has begun to address this tension, proposing systems that purport to strike a balance between the privacy of ``honest’’ users and traceability of ``malicious’’ users. Unfortunately, these systems suffer from a lack of protection against malicious or coerced service providers. In this work, we address the privacy vs. content moderation question through the lens of pre-constrained cryptography [Ananth et al., ITCS 2022]. We introduce the notion of {\em set pre-constrained} (SPC) {\em group signatures} that guarantees security against \emph{malicious key generators}. SPC group signatures offer the ability to trace users in messaging systems who originate pre-defined illegal content (such as child sexual abuse material), while providing security against malicious service providers. We construct concretely efficient protocols for SPC group signatures, and demonstrate the real-world feasibility of our approach via an implementation. The starting point for our solution is the recently introduced Apple PSI system, which we significantly modify to improve security and expand functionality.