Towards Practical RBE

Registration-Based Encryption (RBE) (Garg et al., 2018) is a public-key encryption mechanism which allows users to register their identity (e.g. an email address) and a self-generated public key with a key curator (e.g. an organisation). The key curator aggregates all public keys into a small digest, called state. Using only this state and a recipient’s identity, anyone can encrypt a message to any registered user.

The task of the key curator is only to maintain a registry of public keys, which can be publicly audited. As the key curator is not entrusted with any secrets, RBE presents a solution to the key escrow problem, which impedes the adoption of Identity-Based Encryption (Shamir, 1984). This makes RBE an attractive solution for secure communication with and among members of an organisation while preserving user privacy.

Practical Applications

In practice, RBE could largely eliminate the key-management problem inherent in our current public-key infrastructure, as a state acts as a universal public key for all registered recipients. Consequently, this removes the requirement for individual certificates and their transmission. A practical deployment could therefore bypass the complex, error-prone infrastructure required for certificate generation and validation – a goal closely related to the study of certificateless public-key cryptography (Al-Riyami & Paterson, 2003).

Constructions

Early RBE constructions relied on obfuscation or recursive garbled circuits, rendering them purely theoretical even after extensive optimisation. Recent works proposed fully algebraic constructions with near-practical efficiency albeit with various limitations (Glaeser et al., 2023)(Döttling et al., 2023)(Fiore et al., 2023). These limitations include a small maximum number of registered users, a lack post-quantum security, ciphertext sizes scaling in the order of GB, or a combination thereof. The papers (Glaeser et al., 2023) and (Döttling et al., 2023) both construct an RBE from two primitives: a vector commitment and public-key encryption. (Fiore et al., 2023) provides a compiler from RBE with small identity space (e.g. $[N]$ for $N \in \mathsf{poly}(\lambda)$) to an RBE with arbitrary identity space (e.g. email addresses) using witness encryption for vector commitments and secret sharing.

In our work (Klooß et al., 2026), we build upon the blueprint from (Döttling et al., 2023) – the only post-quantum candidate that naturally extends to arbitrary identity spaces, albeit at the cost 7.2 GB ciphertexts. Furthermore, it provides transparent setup and its security is based on LWE. Our work improves on this construction in several ways, but the most notable differences are:

• We observe that a large portion of the ciphertext is dominated by multi-instances of the vector commitment. By sharing the randomness for this component across all public-key encryption instances, we avoid redundant transmissions and significantly reduce the ciphertext size.
• Instead of relying on a naive gadget matrix and bit decomposition, we choose a near-optimal base for these operations and utilise approximate gadgets rather than exact ones.
• We replace statistical arguments such as the leftover hash lemma by computational assumptions. More specifically, our security proof relies on Leaky LWE rather than error-leakage LWE, which also enables some leakage of the secret key and provides a tighter reduction from LWE.
• We pick parameters based on the hardness of LWE and utilise bit-dropping for the ciphertext.

These and several other optimisations reduce the ciphertext of our constructions to 7.0 MB for 128-bit secure parameters.

Our analysis essentially exhausts the known techniques for the optimisation of LWE-based encryption schemes. The only real optimisation factor not considered in our analysis is the deterministic LWR error introduced via bit-dropping of the ciphertext. Therefore, we claim that a structural change, namely a replacement of the underlying vector commitment scheme is required to significantly reduce the ciphertext size further.

This hypothesis was validated by independent work (Zhang et al., 2026), which achieves a size reductions by replacing the underlying vector commitment.