Constant Size Ciphertexts for Scalable Group Encryption

56 concepts26 papers2 proposals

In traditional public-key encryption, sending a secure message to multiple recipients usually requires the sender to "seal" the message once for every person. As the group grows, the encrypted package—the ciphertext—bloats linearly. For a system with millions of users, like a satellite broadcast or a massive corporate hierarchy, this linear scaling becomes a prohibitive bandwidth bottleneck.

The research direction of constant-size ciphertext aims to decouple the size of the encrypted data from the number of recipients or the complexity of the access policy. By leveraging advanced mathematical structures, these schemes ensure that whether you are encrypting for ten users or ten million, the communication overhead remains fixed.

The Scalability Bottleneck

The fundamental challenge in group communication is managing the "header" of an encrypted message. As Amos Fiat et al. established in the foundational work on traitor tracing, providing unique security parameters to every user often leads to significant transmission overhead. In early broadcast systems, the message length scaled poorly with the total system size or the number of excluded users, as noted by Dalit Naor et al..

To solve this, researchers moved toward schemes where the overhead is determined not by the total population, but by specific constraints like the maximum number of colluders the system can detect. Matthew Franklin et al. demonstrated that decoupling these costs allows systems to scale to millions of subscribers, making massive encrypted broadcasts viable.

Aggregating Identities into Fixed Elements

The "magic" of constant-size ciphertexts often lies in bilinear pairings and mathematical aggregation. Instead of creating $N$ separate encryptions, the system aggregates recipient information within mathematical exponents. Shengbao Wang et al. describe how multi-decrypter encryption can achieve a fixed ciphertext size by aggregating public key information, ensuring that communication costs do not scale with the size of the decryption group.

Michael Hamburg proposed a unifying framework that maps complex policies—such as those combining hierarchies and broadcast groups—into a small, fixed number of group elements. This approach ensures that the bandwidth required for a broadcast remains minimal even as the access policy becomes increasingly complex.

Flattening the Hierarchy

In Identity-Based Encryption (IBE), users are identified by strings like email addresses. In a Hierarchical IBE (HIBE), these identities form a tree (e.g., company/department/employee). Traditionally, the deeper you were in the tree, the larger your ciphertext and the harder it was to decrypt.

Tetsutaro Kobayashi et al. and Jae Hong Seo independently showed that HIBE can achieve constant ciphertext size regardless of the recipient's depth. This is achieved by using "subgroup blinding" to represent the entire identity path within a fixed number of group elements. Crucially, this also enables depth-independent decryption complexity. As Bai Qing-hai et al. argue, maintaining constant decryption time is essential for scalability, ensuring that users at the bottom of a large organizational tree don't suffer from increased latency.

The Trade-off: Shifting the Burden

Achieving constant-size ciphertexts often requires a trade-off: the complexity doesn't disappear; it moves. Adam Smith et al. describe this as "sender-compact" encryption, where the linear complexity burden is shifted from the message transmission to the public key infrastructure.

In this model, the public key might be large (scaling with the number of users), but it is distributed only once. The ciphertexts sent using that key remain small. This trade-off is highly efficient for systems where a single setup is used for thousands of subsequent transmissions, such as secure content distribution or multi-party computation.

Privacy and Revocation

Adding features like anonymity or revocation usually makes ciphertexts even larger. However, recent work has found ways to maintain efficiency even with these constraints:

  • Anonymity: Angelo De et al. showed that identities in a hierarchy can be hidden using composite-order bilinear groups while keeping ciphertexts short.
  • Revocation: Yinghui Zhang et al. integrated broadcast logic into attribute-based systems to allow for direct revocation of users without bloating the ciphertext or forcing everyone to update their keys.
  • Hardware Acceleration: Stefan Contiu et al. demonstrated that using Trusted Execution Environments (like Intel SGX) can reduce metadata storage by six orders of magnitude, effectively achieving constant-sized metadata for group access control.

While Bo Tang 0009 et al. have identified fundamental mathematical barriers to building these systems using only basic building blocks like one-way functions, the use of advanced primitives like multilinear maps (Brent Waters et al.) and indistinguishability obfuscation (Mark Zhandry) continues to push the boundaries of what is possible in constant-size secure communication.

Key Foundational Work

An Efficient Public Key Traitor Tracing Scheme (1999) — contributed 2 concept elements to this direction.
Tracing Traitors (1994) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_constant_size_ciphertext_85afb9bb,
  title = {constant-size ciphertext},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constant-size-ciphertext/rdr_85afb9bbc4ad4dd99ef7374ca3da70db},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_constant_size_ciphertext_85afb9bb_v1,
  title = {constant-size ciphertext},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constant-size-ciphertext/rdr_85afb9bbc4ad4dd99ef7374ca3da70db/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake